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_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/cav12/simple_array_inversion-3.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 04:44:01,611 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 04:44:01,614 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 04:44:01,628 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 04:44:01,628 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 04:44:01,629 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 04:44:01,630 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 04:44:01,632 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 04:44:01,633 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 04:44:01,635 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 04:44:01,636 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 04:44:01,636 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 04:44:01,637 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 04:44:01,638 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 04:44:01,641 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 04:44:01,642 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 04:44:01,643 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 04:44:01,653 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 04:44:01,655 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 04:44:01,655 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 04:44:01,656 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 04:44:01,662 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 04:44:01,662 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 04:44:01,662 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 04:44:01,663 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 04:44:01,664 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 04:44:01,664 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 04:44:01,667 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 04:44:01,668 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 04:44:01,668 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 04:44:01,669 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 04:44:01,669 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 04:44:01,669 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 04:44:01,674 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 04:44:01,675 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 04:44:01,675 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 04:44:01,693 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 04:44:01,694 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 04:44:01,694 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 04:44:01,694 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 04:44:01,695 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 04:44:01,695 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 04:44:01,696 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 04:44:01,696 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 04:44:01,696 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:44:01,696 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 04:44:01,696 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 04:44:01,697 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 04:44:01,697 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 04:44:01,697 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 04:44:01,697 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 04:44:01,697 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 04:44:01,698 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 04:44:01,699 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 04:44:01,699 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 04:44:01,744 INFO ]: Repository-Root is: /tmp [2018-06-22 04:44:01,760 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 04:44:01,764 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 04:44:01,766 INFO ]: Initializing SmtParser... [2018-06-22 04:44:01,766 INFO ]: SmtParser initialized [2018-06-22 04:44:01,767 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/simple_array_inversion-3.smt2 [2018-06-22 04:44:01,768 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 04:44:01,858 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/simple_array_inversion-3.smt2 unknown [2018-06-22 04:44:02,443 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/simple_array_inversion-3.smt2 [2018-06-22 04:44:02,447 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 04:44:02,453 INFO ]: Walking toolchain with 4 elements. [2018-06-22 04:44:02,453 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 04:44:02,453 INFO ]: Initializing ChcToBoogie... [2018-06-22 04:44:02,453 INFO ]: ChcToBoogie initialized [2018-06-22 04:44:02,456 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:44:02" (1/1) ... [2018-06-22 04:44:02,517 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02 Unit [2018-06-22 04:44:02,517 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 04:44:02,518 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 04:44:02,518 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 04:44:02,518 INFO ]: Boogie Preprocessor initialized [2018-06-22 04:44:02,543 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02" (1/1) ... [2018-06-22 04:44:02,543 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02" (1/1) ... [2018-06-22 04:44:02,570 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02" (1/1) ... [2018-06-22 04:44:02,570 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02" (1/1) ... [2018-06-22 04:44:02,589 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02" (1/1) ... [2018-06-22 04:44:02,590 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02" (1/1) ... [2018-06-22 04:44:02,594 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02" (1/1) ... [2018-06-22 04:44:02,599 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 04:44:02,600 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 04:44:02,600 INFO ]: Initializing RCFGBuilder... [2018-06-22 04:44:02,600 INFO ]: RCFGBuilder initialized [2018-06-22 04:44:02,601 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02" (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 04:44:02,612 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 04:44:02,612 INFO ]: Found specification of procedure gotoProc [2018-06-22 04:44:02,612 INFO ]: Found implementation of procedure gotoProc [2018-06-22 04:44:02,612 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 04:44:02,612 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 04:44:02,612 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 04:44:03,044 INFO ]: Using library mode [2018-06-22 04:44:03,044 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:44:03 BoogieIcfgContainer [2018-06-22 04:44:03,044 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 04:44:03,046 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 04:44:03,046 INFO ]: Initializing TraceAbstraction... [2018-06-22 04:44:03,052 INFO ]: TraceAbstraction initialized [2018-06-22 04:44:03,052 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:44:02" (1/3) ... [2018-06-22 04:44:03,053 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c563229 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:44:03, skipping insertion in model container [2018-06-22 04:44:03,053 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:02" (2/3) ... [2018-06-22 04:44:03,053 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c563229 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:44:03, skipping insertion in model container [2018-06-22 04:44:03,054 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:44:03" (3/3) ... [2018-06-22 04:44:03,058 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 04:44:03,067 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 04:44:03,076 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 04:44:03,126 INFO ]: Using default assertion order modulation [2018-06-22 04:44:03,127 INFO ]: Interprodecural is true [2018-06-22 04:44:03,127 INFO ]: Hoare is false [2018-06-22 04:44:03,127 INFO ]: Compute interpolants for FPandBP [2018-06-22 04:44:03,127 INFO ]: Backedges is TWOTRACK [2018-06-22 04:44:03,127 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 04:44:03,127 INFO ]: Difference is false [2018-06-22 04:44:03,127 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 04:44:03,127 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 04:44:03,140 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 04:44:03,151 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 04:44:03,152 INFO ]: Found error trace [2018-06-22 04:44:03,152 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:44:03,152 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:44:03,156 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 04:44:03,157 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:44:03,157 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:44:03,193 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:03,193 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:44:03,193 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:03,260 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:03,370 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:44:03,372 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 04:44:03,372 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 04:44:03,374 INFO ]: Interpolant automaton has 3 states [2018-06-22 04:44:03,384 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 04:44:03,384 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:44:03,387 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 04:44:03,466 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:44:03,467 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 04:44:03,467 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 04:44:03,468 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 04:44:03,469 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:44:03,476 INFO ]: With dead ends: 9 [2018-06-22 04:44:03,476 INFO ]: Without dead ends: 9 [2018-06-22 04:44:03,479 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:44:03,511 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 04:44:03,539 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 04:44:03,540 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 04:44:03,541 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 04:44:03,545 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 04:44:03,545 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:44:03,545 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 04:44:03,545 INFO ]: Interpolant automaton has 3 states. [2018-06-22 04:44:03,545 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 04:44:03,545 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 04:44:03,545 INFO ]: Found error trace [2018-06-22 04:44:03,545 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:44:03,545 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:44:03,546 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 04:44:03,546 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:44:03,546 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:44:03,547 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:03,547 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:44:03,547 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:03,693 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:04,014 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:44:04,014 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:44:04,015 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 04:44:04,028 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:44:04,154 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:04,166 INFO ]: Computing forward predicates... [2018-06-22 04:44:05,010 WARN ]: Spent 324.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 14 [2018-06-22 04:44:05,014 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:44:05,042 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:44:05,042 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 04:44:05,042 INFO ]: Interpolant automaton has 5 states [2018-06-22 04:44:05,042 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 04:44:05,042 INFO ]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 04:44:05,043 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 04:44:05,159 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:44:05,160 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 04:44:05,161 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 04:44:05,161 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 04:44:05,161 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:44:05,161 INFO ]: With dead ends: 11 [2018-06-22 04:44:05,161 INFO ]: Without dead ends: 11 [2018-06-22 04:44:05,162 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 04:44:05,162 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 04:44:05,163 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 04:44:05,163 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 04:44:05,163 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 04:44:05,164 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-22 04:44:05,164 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:44:05,164 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 04:44:05,164 INFO ]: Interpolant automaton has 5 states. [2018-06-22 04:44:05,164 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 04:44:05,164 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 04:44:05,164 INFO ]: Found error trace [2018-06-22 04:44:05,164 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:44:05,164 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:44:05,164 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 2 times [2018-06-22 04:44:05,164 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:44:05,164 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:44:05,168 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:05,168 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:44:05,168 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:05,439 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:06,253 WARN ]: Spent 351.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 7 [2018-06-22 04:44:06,380 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:44:06,380 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:44:06,380 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 04:44:06,394 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 04:44:06,573 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 04:44:06,573 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:06,584 INFO ]: Computing forward predicates... [2018-06-22 04:44:07,715 WARN ]: Spent 492.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 14 [2018-06-22 04:44:10,742 WARN ]: Spent 303.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 25 [2018-06-22 04:44:12,920 WARN ]: Spent 1.03 s on a formula simplification. DAG size of input: 22 DAG size of output: 12 [2018-06-22 04:44:12,931 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:44:12,965 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:44:12,966 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 04:44:12,966 INFO ]: Interpolant automaton has 9 states [2018-06-22 04:44:12,966 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 04:44:12,966 INFO ]: CoverageRelationStatistics Valid=31, Invalid=41, Unknown=0, NotChecked=0, Total=72 [2018-06-22 04:44:12,966 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 9 states. [2018-06-22 04:44:13,666 WARN ]: Spent 508.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-22 04:44:13,766 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:44:13,766 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 04:44:13,768 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 04:44:13,769 INFO ]: Start accepts. Automaton has 9 states. Word has length 10 [2018-06-22 04:44:13,769 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:44:13,769 INFO ]: With dead ends: 13 [2018-06-22 04:44:13,769 INFO ]: Without dead ends: 13 [2018-06-22 04:44:13,769 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2018-06-22 04:44:13,769 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 04:44:13,771 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 04:44:13,771 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 04:44:13,771 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 04:44:13,771 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 10 [2018-06-22 04:44:13,771 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:44:13,771 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 04:44:13,771 INFO ]: Interpolant automaton has 9 states. [2018-06-22 04:44:13,771 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 04:44:13,772 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 04:44:13,772 INFO ]: Found error trace [2018-06-22 04:44:13,772 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:44:13,772 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:44:13,772 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 3 times [2018-06-22 04:44:13,772 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:44:13,772 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:44:13,773 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:13,773 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:44:13,773 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:14,128 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:14,869 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:44:14,869 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:44:14,869 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 04:44:14,878 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 04:44:15,097 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 04:44:15,097 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:15,114 INFO ]: Computing forward predicates... [2018-06-22 04:44:15,574 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 14 [2018-06-22 04:44:18,167 WARN ]: Spent 281.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 25 [2018-06-22 04:44:21,059 WARN ]: Spent 622.00 ms on a formula simplification. DAG size of input: 170 DAG size of output: 22 [2018-06-22 04:44:23,450 WARN ]: Spent 674.00 ms on a formula simplification. DAG size of input: 168 DAG size of output: 19 [2018-06-22 04:44:24,107 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:44:24,141 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:44:24,141 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 04:44:24,141 INFO ]: Interpolant automaton has 13 states [2018-06-22 04:44:24,142 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 04:44:24,142 INFO ]: CoverageRelationStatistics Valid=61, Invalid=95, Unknown=0, NotChecked=0, Total=156 [2018-06-22 04:44:24,142 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 13 states. [2018-06-22 04:44:24,180 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:44:24,180 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 04:44:24,181 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 04:44:24,181 INFO ]: Start accepts. Automaton has 13 states. Word has length 12 [2018-06-22 04:44:24,182 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:44:24,182 INFO ]: With dead ends: 14 [2018-06-22 04:44:24,182 INFO ]: Without dead ends: 14 [2018-06-22 04:44:24,182 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=61, Invalid=95, Unknown=0, NotChecked=0, Total=156 [2018-06-22 04:44:24,182 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 04:44:24,184 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 04:44:24,184 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 04:44:24,184 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 04:44:24,184 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-22 04:44:24,184 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:44:24,184 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 04:44:24,184 INFO ]: Interpolant automaton has 13 states. [2018-06-22 04:44:24,185 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 04:44:24,185 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 04:44:24,185 INFO ]: Found error trace [2018-06-22 04:44:24,185 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:44:24,185 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:44:24,185 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 4 times [2018-06-22 04:44:24,185 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:44:24,185 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:44:24,186 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:24,186 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:44:24,186 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:24,488 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:24,999 WARN ]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 04:44:25,411 WARN ]: Spent 360.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 11 [2018-06-22 04:44:25,583 WARN ]: Spent 160.00 ms on a formula simplification. DAG size of input: 92 DAG size of output: 46 [2018-06-22 04:44:25,765 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 44 [2018-06-22 04:44:25,935 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:44:25,935 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:44:25,935 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) [2018-06-22 04:44:25,951 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:44:26,185 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 04:44:26,185 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:26,203 INFO ]: Computing forward predicates... [2018-06-22 04:44:26,585 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 14 [2018-06-22 04:44:31,363 WARN ]: Spent 3.69 s on a formula simplification. DAG size of input: 499 DAG size of output: 100 Received shutdown request... [2018-06-22 04:45:00,750 WARN ]: Removed 924 from assertion stack [2018-06-22 04:45:00,750 INFO ]: Timeout while computing interpolants [2018-06-22 04:45:00,950 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:45:00,951 WARN ]: Verification canceled [2018-06-22 04:45:00,955 WARN ]: Timeout [2018-06-22 04:45:00,955 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:45:00 BoogieIcfgContainer [2018-06-22 04:45:00,955 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 04:45:00,956 INFO ]: Toolchain (without parser) took 58508.74 ms. Allocated memory was 304.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 239.5 MB in the beginning and 368.4 MB in the end (delta: -128.9 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 04:45:00,958 INFO ]: SmtParser took 0.09 ms. Allocated memory is still 304.1 MB. Free memory is still 269.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 04:45:00,959 INFO ]: ChcToBoogie took 64.04 ms. Allocated memory is still 304.1 MB. Free memory was 238.5 MB in the beginning and 236.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:45:00,959 INFO ]: Boogie Preprocessor took 81.99 ms. Allocated memory is still 304.1 MB. Free memory was 236.6 MB in the beginning and 234.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:45:00,959 INFO ]: RCFGBuilder took 444.34 ms. Allocated memory is still 304.1 MB. Free memory was 234.6 MB in the beginning and 202.5 MB in the end (delta: 32.0 MB). Peak memory consumption was 32.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:45:00,960 INFO ]: TraceAbstraction took 57909.51 ms. Allocated memory was 304.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 202.5 MB in the beginning and 368.4 MB in the end (delta: -165.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 04:45:00,962 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.09 ms. Allocated memory is still 304.1 MB. Free memory is still 269.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 64.04 ms. Allocated memory is still 304.1 MB. Free memory was 238.5 MB in the beginning and 236.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 81.99 ms. Allocated memory is still 304.1 MB. Free memory was 236.6 MB in the beginning and 234.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 444.34 ms. Allocated memory is still 304.1 MB. Free memory was 234.6 MB in the beginning and 202.5 MB in the end (delta: 32.0 MB). Peak memory consumption was 32.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 57909.51 ms. Allocated memory was 304.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 202.5 MB in the beginning and 368.4 MB in the end (delta: -165.9 MB). Peak memory consumption was 1.2 GB. 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 14 with TraceHistMax 6, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 2089. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 57.8s OverallTime, 5 OverallIterations, 6 TraceHistogramMax, 1.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 28 SDtfs, 2 SDslu, 69 SDs, 0 SdLazy, 31 SolverSat, 10 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 49 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 6.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=14occurred in iteration=4, 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, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.1s SatisfiabilityAnalysisTime, 18.3s InterpolantComputationTime, 67 NumberOfCodeBlocks, 67 NumberOfCodeBlocksAsserted, 11 NumberOfCheckSat, 60 ConstructedInterpolants, 0 QuantifiedInterpolants, 4073 SizeOfPredicates, 12 NumberOfNonLiveVariables, 1386 ConjunctsInSsa, 95 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 0/44 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/simple_array_inversion-3.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_04-45-00-974.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/simple_array_inversion-3.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_04-45-00-974.csv Completed graceful shutdown