java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/lustre/cd.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 16:09:52,659 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 16:09:52,661 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 16:09:52,674 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 16:09:52,674 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 16:09:52,675 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 16:09:52,678 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 16:09:52,680 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 16:09:52,682 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 16:09:52,682 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 16:09:52,684 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 16:09:52,684 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 16:09:52,685 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 16:09:52,686 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 16:09:52,687 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 16:09:52,687 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 16:09:52,689 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 16:09:52,691 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 16:09:52,692 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 16:09:52,702 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 16:09:52,704 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 16:09:52,706 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 16:09:52,706 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 16:09:52,706 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 16:09:52,707 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 16:09:52,708 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 16:09:52,709 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 16:09:52,709 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 16:09:52,710 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 16:09:52,711 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 16:09:52,716 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 16:09:52,717 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 16:09:52,717 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 16:09:52,718 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 16:09:52,718 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 16:09:52,719 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 16:09:52,735 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 16:09:52,735 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 16:09:52,736 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 16:09:52,736 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 16:09:52,737 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 16:09:52,737 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 16:09:52,737 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 16:09:52,738 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 16:09:52,739 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 16:09:52,739 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 16:09:52,739 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 16:09:52,739 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 16:09:52,740 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 16:09:52,740 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 16:09:52,740 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 16:09:52,740 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 16:09:52,740 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 16:09:52,741 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 16:09:52,741 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 16:09:52,743 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 16:09:52,743 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 16:09:52,790 INFO ]: Repository-Root is: /tmp [2018-06-22 16:09:52,803 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 16:09:52,811 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 16:09:52,813 INFO ]: Initializing SmtParser... [2018-06-22 16:09:52,813 INFO ]: SmtParser initialized [2018-06-22 16:09:52,814 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/cd.smt2 [2018-06-22 16:09:52,815 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 16:09:52,907 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/cd.smt2 unknown [2018-06-22 16:09:53,200 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/cd.smt2 [2018-06-22 16:09:53,204 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 16:09:53,209 INFO ]: Walking toolchain with 4 elements. [2018-06-22 16:09:53,209 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 16:09:53,209 INFO ]: Initializing ChcToBoogie... [2018-06-22 16:09:53,209 INFO ]: ChcToBoogie initialized [2018-06-22 16:09:53,212 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:09:53" (1/1) ... [2018-06-22 16:09:53,260 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53 Unit [2018-06-22 16:09:53,260 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 16:09:53,260 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 16:09:53,260 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 16:09:53,260 INFO ]: Boogie Preprocessor initialized [2018-06-22 16:09:53,285 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53" (1/1) ... [2018-06-22 16:09:53,285 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53" (1/1) ... [2018-06-22 16:09:53,293 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53" (1/1) ... [2018-06-22 16:09:53,293 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53" (1/1) ... [2018-06-22 16:09:53,297 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53" (1/1) ... [2018-06-22 16:09:53,298 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53" (1/1) ... [2018-06-22 16:09:53,299 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53" (1/1) ... [2018-06-22 16:09:53,301 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 16:09:53,302 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 16:09:53,302 INFO ]: Initializing RCFGBuilder... [2018-06-22 16:09:53,302 INFO ]: RCFGBuilder initialized [2018-06-22 16:09:53,302 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 16:09:53,313 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 16:09:53,313 INFO ]: Found specification of procedure False [2018-06-22 16:09:53,313 INFO ]: Found implementation of procedure False [2018-06-22 16:09:53,313 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 16:09:53,313 INFO ]: Found specification of procedure state [2018-06-22 16:09:53,313 INFO ]: Found implementation of procedure state [2018-06-22 16:09:53,313 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 16:09:53,313 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 16:09:53,313 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 16:09:53,577 INFO ]: Using library mode [2018-06-22 16:09:53,578 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:09:53 BoogieIcfgContainer [2018-06-22 16:09:53,578 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 16:09:53,579 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 16:09:53,579 INFO ]: Initializing TraceAbstraction... [2018-06-22 16:09:53,589 INFO ]: TraceAbstraction initialized [2018-06-22 16:09:53,589 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:09:53" (1/3) ... [2018-06-22 16:09:53,590 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3b126d37 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:09:53, skipping insertion in model container [2018-06-22 16:09:53,590 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:09:53" (2/3) ... [2018-06-22 16:09:53,591 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3b126d37 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:09:53, skipping insertion in model container [2018-06-22 16:09:53,591 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:09:53" (3/3) ... [2018-06-22 16:09:53,592 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 16:09:53,600 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 16:09:53,608 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 16:09:53,651 INFO ]: Using default assertion order modulation [2018-06-22 16:09:53,651 INFO ]: Interprodecural is true [2018-06-22 16:09:53,651 INFO ]: Hoare is false [2018-06-22 16:09:53,652 INFO ]: Compute interpolants for FPandBP [2018-06-22 16:09:53,652 INFO ]: Backedges is TWOTRACK [2018-06-22 16:09:53,652 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 16:09:53,652 INFO ]: Difference is false [2018-06-22 16:09:53,652 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 16:09:53,652 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 16:09:53,665 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 16:09:53,673 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 16:09:53,673 INFO ]: Found error trace [2018-06-22 16:09:53,674 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:09:53,674 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:09:53,678 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 16:09:53,679 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:09:53,679 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:09:53,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:53,711 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 16:09:53,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:53,788 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:09:53,924 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 16:09:53,926 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 16:09:53,926 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 16:09:53,927 INFO ]: Interpolant automaton has 4 states [2018-06-22 16:09:53,937 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 16:09:53,937 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 16:09:53,939 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 16:09:54,040 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:09:54,041 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 16:09:54,041 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 16:09:54,042 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 16:09:54,042 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:09:54,051 INFO ]: With dead ends: 13 [2018-06-22 16:09:54,051 INFO ]: Without dead ends: 13 [2018-06-22 16:09:54,052 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 16:09:54,064 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 16:09:54,088 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 16:09:54,089 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 16:09:54,090 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 16:09:54,092 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 16:09:54,092 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:09:54,092 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 16:09:54,092 INFO ]: Interpolant automaton has 4 states. [2018-06-22 16:09:54,092 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 16:09:54,093 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 16:09:54,093 INFO ]: Found error trace [2018-06-22 16:09:54,093 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:09:54,093 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:09:54,094 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 16:09:54,094 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:09:54,094 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:09:54,095 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:54,095 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 16:09:54,095 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:54,152 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:09:54,367 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 16:09:54,367 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:09:54,367 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:09:54,375 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 16:09:54,442 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:09:54,452 INFO ]: Computing forward predicates... [2018-06-22 16:09:54,943 WARN ]: Spent 203.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 5 [2018-06-22 16:09:54,977 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 16:09:55,010 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:09:55,010 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 16:09:55,011 INFO ]: Interpolant automaton has 8 states [2018-06-22 16:09:55,011 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 16:09:55,011 INFO ]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-06-22 16:09:55,011 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 8 states. [2018-06-22 16:09:55,337 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:09:55,337 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 16:09:55,339 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 16:09:55,339 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-22 16:09:55,339 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:09:55,339 INFO ]: With dead ends: 15 [2018-06-22 16:09:55,339 INFO ]: Without dead ends: 15 [2018-06-22 16:09:55,340 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-06-22 16:09:55,340 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 16:09:55,343 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 16:09:55,343 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 16:09:55,344 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 16:09:55,344 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 16:09:55,347 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:09:55,347 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 16:09:55,347 INFO ]: Interpolant automaton has 8 states. [2018-06-22 16:09:55,347 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 16:09:55,348 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 16:09:55,348 INFO ]: Found error trace [2018-06-22 16:09:55,348 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:09:55,348 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:09:55,348 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 16:09:55,348 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:09:55,348 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:09:55,349 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:55,349 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 16:09:55,349 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:55,416 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:09:55,850 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 16:09:55,850 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:09:55,850 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:09:55,858 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 16:09:55,925 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 16:09:55,925 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:09:55,929 INFO ]: Computing forward predicates... [2018-06-22 16:09:56,367 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 16:09:56,399 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:09:56,400 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2018-06-22 16:09:56,400 INFO ]: Interpolant automaton has 12 states [2018-06-22 16:09:56,400 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 16:09:56,400 INFO ]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2018-06-22 16:09:56,400 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 12 states. [2018-06-22 16:09:56,758 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:09:56,758 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 16:09:56,758 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 16:09:56,758 INFO ]: Start accepts. Automaton has 12 states. Word has length 17 [2018-06-22 16:09:56,758 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:09:56,759 INFO ]: With dead ends: 17 [2018-06-22 16:09:56,759 INFO ]: Without dead ends: 17 [2018-06-22 16:09:56,760 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2018-06-22 16:09:56,760 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 16:09:56,764 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 16:09:56,764 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 16:09:56,764 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 16:09:56,764 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 16:09:56,764 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:09:56,764 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 16:09:56,764 INFO ]: Interpolant automaton has 12 states. [2018-06-22 16:09:56,764 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 16:09:56,765 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 16:09:56,765 INFO ]: Found error trace [2018-06-22 16:09:56,765 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:09:56,765 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:09:56,765 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 3 times [2018-06-22 16:09:56,765 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:09:56,765 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:09:56,766 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:56,766 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:09:56,766 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:56,818 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:09:57,098 WARN ]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 16:09:57,383 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 16:09:57,383 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:09:57,383 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:09:57,398 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 16:09:57,482 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 16:09:57,483 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:09:57,486 INFO ]: Computing forward predicates... [2018-06-22 16:09:58,349 WARN ]: Spent 208.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 15 [2018-06-22 16:09:58,443 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 16:09:58,472 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:09:58,472 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-06-22 16:09:58,473 INFO ]: Interpolant automaton has 15 states [2018-06-22 16:09:58,473 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 16:09:58,473 INFO ]: CoverageRelationStatistics Valid=31, Invalid=179, Unknown=0, NotChecked=0, Total=210 [2018-06-22 16:09:58,473 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 15 states. [2018-06-22 16:09:58,628 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 59 [2018-06-22 16:09:58,756 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 59 [2018-06-22 16:09:58,893 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 60 [2018-06-22 16:09:59,038 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:09:59,039 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 16:09:59,039 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 16:09:59,039 INFO ]: Start accepts. Automaton has 15 states. Word has length 21 [2018-06-22 16:09:59,039 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:09:59,040 INFO ]: With dead ends: 19 [2018-06-22 16:09:59,040 INFO ]: Without dead ends: 19 [2018-06-22 16:09:59,040 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=82, Invalid=298, Unknown=0, NotChecked=0, Total=380 [2018-06-22 16:09:59,040 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 16:09:59,044 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 16:09:59,044 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 16:09:59,045 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 16:09:59,045 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 16:09:59,045 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:09:59,045 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 16:09:59,045 INFO ]: Interpolant automaton has 15 states. [2018-06-22 16:09:59,045 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 16:09:59,046 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 16:09:59,046 INFO ]: Found error trace [2018-06-22 16:09:59,046 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:09:59,046 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:09:59,046 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 4 times [2018-06-22 16:09:59,046 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:09:59,046 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:09:59,047 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:59,047 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:09:59,047 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:09:59,096 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:09:59,397 INFO ]: Checked inductivity of 36 backedges. 1 proven. 25 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 16:09:59,397 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:09:59,397 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:09:59,403 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 16:09:59,472 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 16:09:59,472 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:09:59,476 INFO ]: Computing forward predicates... [2018-06-22 16:09:59,742 INFO ]: Checked inductivity of 36 backedges. 0 proven. 23 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-06-22 16:09:59,775 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:09:59,775 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 10] total 18 [2018-06-22 16:09:59,776 INFO ]: Interpolant automaton has 18 states [2018-06-22 16:09:59,776 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 16:09:59,776 INFO ]: CoverageRelationStatistics Valid=52, Invalid=254, Unknown=0, NotChecked=0, Total=306 [2018-06-22 16:09:59,776 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 18 states. [2018-06-22 16:10:00,150 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 39 [2018-06-22 16:10:00,314 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:10:00,314 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 16:10:00,321 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 16:10:00,321 INFO ]: Start accepts. Automaton has 18 states. Word has length 25 [2018-06-22 16:10:00,321 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:10:00,322 INFO ]: With dead ends: 21 [2018-06-22 16:10:00,322 INFO ]: Without dead ends: 21 [2018-06-22 16:10:00,322 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 51 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=129, Invalid=423, Unknown=0, NotChecked=0, Total=552 [2018-06-22 16:10:00,322 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 16:10:00,325 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 16:10:00,325 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 16:10:00,326 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 16:10:00,326 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 16:10:00,326 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:10:00,326 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 16:10:00,326 INFO ]: Interpolant automaton has 18 states. [2018-06-22 16:10:00,326 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 16:10:00,327 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 16:10:00,327 INFO ]: Found error trace [2018-06-22 16:10:00,327 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:10:00,327 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:10:00,327 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 5 times [2018-06-22 16:10:00,327 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:10:00,327 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:10:00,327 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:10:00,327 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:10:00,327 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:10:00,382 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:10:00,804 INFO ]: Checked inductivity of 55 backedges. 1 proven. 39 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 16:10:00,804 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:10:00,804 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 16:10:00,818 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:10:00,897 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 16:10:00,897 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:10:00,901 INFO ]: Computing forward predicates... [2018-06-22 16:10:01,219 INFO ]: Checked inductivity of 55 backedges. 0 proven. 39 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2018-06-22 16:10:01,239 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:10:01,239 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 23 [2018-06-22 16:10:01,239 INFO ]: Interpolant automaton has 23 states [2018-06-22 16:10:01,239 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-22 16:10:01,239 INFO ]: CoverageRelationStatistics Valid=60, Invalid=446, Unknown=0, NotChecked=0, Total=506 [2018-06-22 16:10:01,240 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 23 states. [2018-06-22 16:10:01,396 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 54 [2018-06-22 16:10:01,547 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 50 [2018-06-22 16:10:02,171 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:10:02,171 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 16:10:02,172 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 16:10:02,172 INFO ]: Start accepts. Automaton has 23 states. Word has length 29 [2018-06-22 16:10:02,172 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:10:02,173 INFO ]: With dead ends: 23 [2018-06-22 16:10:02,173 INFO ]: Without dead ends: 23 [2018-06-22 16:10:02,173 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 86 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=180, Invalid=690, Unknown=0, NotChecked=0, Total=870 [2018-06-22 16:10:02,173 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 16:10:02,176 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 16:10:02,176 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 16:10:02,177 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 16:10:02,177 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 16:10:02,177 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:10:02,177 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 16:10:02,177 INFO ]: Interpolant automaton has 23 states. [2018-06-22 16:10:02,177 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 16:10:02,178 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 16:10:02,178 INFO ]: Found error trace [2018-06-22 16:10:02,178 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:10:02,178 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:10:02,178 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 6 times [2018-06-22 16:10:02,178 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:10:02,178 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:10:02,179 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:10:02,179 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:10:02,179 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:10:02,229 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:10:02,741 INFO ]: Checked inductivity of 78 backedges. 2 proven. 55 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 16:10:02,741 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:10:02,741 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:10:02,749 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 16:10:02,847 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 16:10:02,847 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:10:02,854 INFO ]: Computing forward predicates... [2018-06-22 16:10:03,622 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 16:10:03,650 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:10:03,650 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 27 [2018-06-22 16:10:03,651 INFO ]: Interpolant automaton has 27 states [2018-06-22 16:10:03,652 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 16:10:03,653 INFO ]: CoverageRelationStatistics Valid=71, Invalid=631, Unknown=0, NotChecked=0, Total=702 [2018-06-22 16:10:03,653 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 27 states. [2018-06-22 16:10:03,980 WARN ]: Spent 266.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 66 [2018-06-22 16:10:04,404 WARN ]: Spent 365.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 68 [2018-06-22 16:10:04,862 WARN ]: Spent 435.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 69 [2018-06-22 16:10:05,208 WARN ]: Spent 321.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 67 [2018-06-22 16:10:05,530 WARN ]: Spent 292.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 67 [2018-06-22 16:10:06,162 WARN ]: Spent 481.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 65 [2018-06-22 16:10:06,471 WARN ]: Spent 277.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 65 [2018-06-22 16:10:06,766 WARN ]: Spent 261.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 65 [2018-06-22 16:10:07,072 WARN ]: Spent 247.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 62 [2018-06-22 16:10:07,105 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:10:07,105 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 16:10:07,107 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 16:10:07,107 INFO ]: Start accepts. Automaton has 27 states. Word has length 33 [2018-06-22 16:10:07,107 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:10:07,107 INFO ]: With dead ends: 29 [2018-06-22 16:10:07,107 INFO ]: Without dead ends: 29 [2018-06-22 16:10:07,108 INFO ]: 0 DeclaredPredicates, 58 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 167 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=277, Invalid=1055, Unknown=0, NotChecked=0, Total=1332 [2018-06-22 16:10:07,108 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 16:10:07,112 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 16:10:07,112 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 16:10:07,113 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 16:10:07,113 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 33 [2018-06-22 16:10:07,113 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:10:07,113 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 16:10:07,113 INFO ]: Interpolant automaton has 27 states. [2018-06-22 16:10:07,113 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 16:10:07,114 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 16:10:07,114 INFO ]: Found error trace [2018-06-22 16:10:07,114 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:10:07,114 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:10:07,114 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 7 times [2018-06-22 16:10:07,114 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:10:07,114 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:10:07,115 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:10:07,115 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:10:07,115 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:10:07,265 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:10:07,696 WARN ]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 16:10:09,225 WARN ]: Spent 1.45 s on a formula simplification. DAG size of input: 49 DAG size of output: 40 [2018-06-22 16:10:09,863 INFO ]: Checked inductivity of 171 backedges. 3 proven. 123 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 16:10:09,863 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:10:09,863 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:10:09,869 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 16:10:09,984 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:10:09,996 INFO ]: Computing forward predicates... [2018-06-22 16:10:11,181 WARN ]: Spent 659.00 ms on a formula simplification. DAG size of input: 138 DAG size of output: 44 [2018-06-22 16:10:34,526 WARN ]: Spent 18.44 s on a formula simplification. DAG size of input: 915 DAG size of output: 110 [2018-06-22 16:10:34,575 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 16:10:34,653 WARN ]: Simplifying disjunction of 9360 conjuctions. This might take some time... [2018-06-22 16:10:41,417 INFO ]: Simplified to disjunction of 9360 conjuctions. Received shutdown request... [2018-06-22 16:10:59,793 INFO ]: Timeout while computing interpolants [2018-06-22 16:10:59,994 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:10:59,994 WARN ]: Verification canceled [2018-06-22 16:10:59,998 WARN ]: Timeout [2018-06-22 16:10:59,998 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:10:59 BoogieIcfgContainer [2018-06-22 16:10:59,998 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 16:10:59,998 INFO ]: Toolchain (without parser) took 66794.38 ms. Allocated memory was 309.9 MB in the beginning and 1.1 GB in the end (delta: 793.8 MB). Free memory was 261.1 MB in the beginning and 436.8 MB in the end (delta: -175.7 MB). Peak memory consumption was 618.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:10:59,999 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 16:11:00,000 INFO ]: ChcToBoogie took 51.10 ms. Allocated memory is still 309.9 MB. Free memory was 261.1 MB in the beginning and 259.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:11:00,000 INFO ]: Boogie Preprocessor took 40.72 ms. Allocated memory is still 309.9 MB. Free memory was 259.1 MB in the beginning and 257.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:11:00,001 INFO ]: RCFGBuilder took 276.21 ms. Allocated memory is still 309.9 MB. Free memory was 257.1 MB in the beginning and 244.1 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:11:00,001 INFO ]: TraceAbstraction took 66418.58 ms. Allocated memory was 309.9 MB in the beginning and 1.1 GB in the end (delta: 793.8 MB). Free memory was 244.1 MB in the beginning and 436.8 MB in the end (delta: -192.7 MB). Peak memory consumption was 601.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:11:00,004 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 51.10 ms. Allocated memory is still 309.9 MB. Free memory was 261.1 MB in the beginning and 259.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 40.72 ms. Allocated memory is still 309.9 MB. Free memory was 259.1 MB in the beginning and 257.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 276.21 ms. Allocated memory is still 309.9 MB. Free memory was 257.1 MB in the beginning and 244.1 MB in the end (delta: 13.0 MB). Peak memory consumption was 13.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 66418.58 ms. Allocated memory was 309.9 MB in the beginning and 1.1 GB in the end (delta: 793.8 MB). Free memory was 244.1 MB in the beginning and 436.8 MB in the end (delta: -192.7 MB). Peak memory consumption was 601.0 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 46 with TraceHistMax 10, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 24 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 66.3s OverallTime, 8 OverallIterations, 10 TraceHistogramMax, 6.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 76 SDtfs, 203 SDslu, 483 SDs, 0 SdLazy, 375 SolverSat, 244 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 235 GetRequests, 107 SyntacticMatches, 2 SemanticMatches, 126 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 335 ImplicationChecksByTransitivity, 8.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=29occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 5.8s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 29 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 40160 SizeOfPredicates, 148 NumberOfNonLiveVariables, 2196 ConjunctsInSsa, 164 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 120/406 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cd.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_16-11-00-014.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cd.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_16-11-00-014.csv Completed graceful shutdown