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-4.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 04:44:46,637 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 04:44:46,639 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 04:44:46,650 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 04:44:46,650 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 04:44:46,651 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 04:44:46,652 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 04:44:46,654 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 04:44:46,656 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 04:44:46,656 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 04:44:46,657 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 04:44:46,658 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 04:44:46,658 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 04:44:46,659 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 04:44:46,660 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 04:44:46,661 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 04:44:46,663 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 04:44:46,665 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 04:44:46,666 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 04:44:46,667 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 04:44:46,669 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 04:44:46,671 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 04:44:46,671 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 04:44:46,671 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 04:44:46,672 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 04:44:46,673 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 04:44:46,674 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 04:44:46,675 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 04:44:46,676 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 04:44:46,676 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 04:44:46,677 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 04:44:46,678 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 04:44:46,678 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 04:44:46,679 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 04:44:46,679 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 04:44:46,680 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:46,696 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 04:44:46,696 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 04:44:46,696 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 04:44:46,697 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 04:44:46,698 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 04:44:46,698 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 04:44:46,698 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 04:44:46,699 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 04:44:46,699 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:44:46,699 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 04:44:46,699 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 04:44:46,700 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 04:44:46,700 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 04:44:46,700 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 04:44:46,700 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 04:44:46,701 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 04:44:46,701 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 04:44:46,702 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 04:44:46,702 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 04:44:46,746 INFO ]: Repository-Root is: /tmp [2018-06-22 04:44:46,760 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 04:44:46,767 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 04:44:46,768 INFO ]: Initializing SmtParser... [2018-06-22 04:44:46,768 INFO ]: SmtParser initialized [2018-06-22 04:44:46,769 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/simple_array_inversion-4.smt2 [2018-06-22 04:44:46,770 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:46,860 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/simple_array_inversion-4.smt2 unknown [2018-06-22 04:44:47,518 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/simple_array_inversion-4.smt2 [2018-06-22 04:44:47,522 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 04:44:47,528 INFO ]: Walking toolchain with 4 elements. [2018-06-22 04:44:47,528 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 04:44:47,528 INFO ]: Initializing ChcToBoogie... [2018-06-22 04:44:47,528 INFO ]: ChcToBoogie initialized [2018-06-22 04:44:47,532 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:44:47" (1/1) ... [2018-06-22 04:44:47,599 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47 Unit [2018-06-22 04:44:47,600 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 04:44:47,600 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 04:44:47,600 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 04:44:47,600 INFO ]: Boogie Preprocessor initialized [2018-06-22 04:44:47,630 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47" (1/1) ... [2018-06-22 04:44:47,630 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47" (1/1) ... [2018-06-22 04:44:47,648 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47" (1/1) ... [2018-06-22 04:44:47,648 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47" (1/1) ... [2018-06-22 04:44:47,665 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47" (1/1) ... [2018-06-22 04:44:47,667 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47" (1/1) ... [2018-06-22 04:44:47,671 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47" (1/1) ... [2018-06-22 04:44:47,678 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 04:44:47,678 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 04:44:47,678 INFO ]: Initializing RCFGBuilder... [2018-06-22 04:44:47,678 INFO ]: RCFGBuilder initialized [2018-06-22 04:44:47,679 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47" (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:47,689 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 04:44:47,689 INFO ]: Found specification of procedure gotoProc [2018-06-22 04:44:47,689 INFO ]: Found implementation of procedure gotoProc [2018-06-22 04:44:47,689 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 04:44:47,689 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 04:44:47,690 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:48,142 INFO ]: Using library mode [2018-06-22 04:44:48,143 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:44:48 BoogieIcfgContainer [2018-06-22 04:44:48,143 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 04:44:48,144 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 04:44:48,145 INFO ]: Initializing TraceAbstraction... [2018-06-22 04:44:48,150 INFO ]: TraceAbstraction initialized [2018-06-22 04:44:48,150 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:44:47" (1/3) ... [2018-06-22 04:44:48,151 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61bf4ff1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:44:48, skipping insertion in model container [2018-06-22 04:44:48,151 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:44:47" (2/3) ... [2018-06-22 04:44:48,151 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@61bf4ff1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:44:48, skipping insertion in model container [2018-06-22 04:44:48,151 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:44:48" (3/3) ... [2018-06-22 04:44:48,153 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 04:44:48,162 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 04:44:48,170 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 04:44:48,223 INFO ]: Using default assertion order modulation [2018-06-22 04:44:48,224 INFO ]: Interprodecural is true [2018-06-22 04:44:48,224 INFO ]: Hoare is false [2018-06-22 04:44:48,224 INFO ]: Compute interpolants for FPandBP [2018-06-22 04:44:48,224 INFO ]: Backedges is TWOTRACK [2018-06-22 04:44:48,224 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 04:44:48,224 INFO ]: Difference is false [2018-06-22 04:44:48,224 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 04:44:48,224 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 04:44:48,255 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 04:44:48,270 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 04:44:48,270 INFO ]: Found error trace [2018-06-22 04:44:48,271 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:44:48,271 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:44:48,275 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 04:44:48,278 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:44:48,278 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:44:48,313 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:48,313 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:44:48,313 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:48,389 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:48,510 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:48,512 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 04:44:48,513 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 04:44:48,515 INFO ]: Interpolant automaton has 3 states [2018-06-22 04:44:48,525 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 04:44:48,526 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:44:48,529 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 04:44:48,613 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:44:48,614 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 04:44:48,615 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 04:44:48,616 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 04:44:48,616 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:44:48,625 INFO ]: With dead ends: 9 [2018-06-22 04:44:48,626 INFO ]: Without dead ends: 9 [2018-06-22 04:44:48,630 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:48,648 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 04:44:48,675 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 04:44:48,676 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 04:44:48,677 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 04:44:48,678 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 04:44:48,678 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:44:48,678 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 04:44:48,678 INFO ]: Interpolant automaton has 3 states. [2018-06-22 04:44:48,678 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 04:44:48,679 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 04:44:48,679 INFO ]: Found error trace [2018-06-22 04:44:48,679 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:44:48,679 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:44:48,680 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 04:44:48,680 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:44:48,680 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:44:48,681 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:48,681 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:44:48,681 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:48,820 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:49,016 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:49,017 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:44:49,017 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:49,023 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:44:49,184 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:49,199 INFO ]: Computing forward predicates... [2018-06-22 04:44:50,496 WARN ]: Spent 267.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 9 [2018-06-22 04:44:50,508 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:50,543 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:44:50,543 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 04:44:50,544 INFO ]: Interpolant automaton has 5 states [2018-06-22 04:44:50,544 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 04:44:50,544 INFO ]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 04:44:50,544 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 04:44:50,604 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:44:50,604 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 04:44:50,604 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 04:44:50,604 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 04:44:50,604 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:44:50,605 INFO ]: With dead ends: 11 [2018-06-22 04:44:50,605 INFO ]: Without dead ends: 11 [2018-06-22 04:44:50,606 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 04:44:50,606 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 04:44:50,607 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 04:44:50,607 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 04:44:50,607 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 04:44:50,607 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-22 04:44:50,607 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:44:50,607 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 04:44:50,607 INFO ]: Interpolant automaton has 5 states. [2018-06-22 04:44:50,607 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 04:44:50,608 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 04:44:50,608 INFO ]: Found error trace [2018-06-22 04:44:50,608 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:44:50,608 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:44:50,608 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 2 times [2018-06-22 04:44:50,608 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:44:50,608 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:44:50,609 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:50,609 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:44:50,609 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:44:50,856 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:51,577 WARN ]: Spent 250.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 7 [2018-06-22 04:44:51,670 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:51,670 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:44:51,670 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:51,676 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 04:44:51,864 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 04:44:51,864 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:44:51,875 INFO ]: Computing forward predicates... [2018-06-22 04:44:52,471 WARN ]: Spent 285.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 9 [2018-06-22 04:44:57,830 WARN ]: Spent 638.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 20 [2018-06-22 04:44:59,847 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:59,869 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:44:59,869 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 04:44:59,869 INFO ]: Interpolant automaton has 8 states [2018-06-22 04:44:59,869 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 04:44:59,869 INFO ]: CoverageRelationStatistics Valid=25, Invalid=31, Unknown=0, NotChecked=0, Total=56 [2018-06-22 04:44:59,869 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 8 states. [2018-06-22 04:45:00,031 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:45:00,031 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 04:45:00,033 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 04:45:00,033 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-22 04:45:00,033 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:45:00,033 INFO ]: With dead ends: 13 [2018-06-22 04:45:00,033 INFO ]: Without dead ends: 13 [2018-06-22 04:45:00,034 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=32, Invalid=40, Unknown=0, NotChecked=0, Total=72 [2018-06-22 04:45:00,034 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 04:45:00,035 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 04:45:00,035 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 04:45:00,035 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 04:45:00,035 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 10 [2018-06-22 04:45:00,035 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:45:00,035 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 04:45:00,035 INFO ]: Interpolant automaton has 8 states. [2018-06-22 04:45:00,035 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 04:45:00,036 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 04:45:00,036 INFO ]: Found error trace [2018-06-22 04:45:00,036 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:45:00,036 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:45:00,036 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 3 times [2018-06-22 04:45:00,036 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:45:00,036 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:45:00,037 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:45:00,037 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:45:00,037 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:45:00,308 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:45:00,900 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 04:45:01,581 WARN ]: Spent 628.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 14 [2018-06-22 04:45:01,735 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 14 [2018-06-22 04:45:01,804 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:45:01,804 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:45:01,804 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:45:01,820 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 04:45:02,060 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 04:45:02,060 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:45:02,076 INFO ]: Computing forward predicates... [2018-06-22 04:45:05,675 WARN ]: Spent 312.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 20 [2018-06-22 04:45:08,905 WARN ]: Spent 1.06 s on a formula simplification. DAG size of input: 251 DAG size of output: 17 [2018-06-22 04:45:11,927 WARN ]: Spent 1.16 s on a formula simplification. DAG size of input: 268 DAG size of output: 14 [2018-06-22 04:45:12,547 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:45:12,570 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:45:12,571 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2018-06-22 04:45:12,571 INFO ]: Interpolant automaton has 12 states [2018-06-22 04:45:12,571 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 04:45:12,572 INFO ]: CoverageRelationStatistics Valid=50, Invalid=82, Unknown=0, NotChecked=0, Total=132 [2018-06-22 04:45:12,572 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 12 states. [2018-06-22 04:45:12,630 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:45:12,630 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 04:45:12,630 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 04:45:12,630 INFO ]: Start accepts. Automaton has 12 states. Word has length 12 [2018-06-22 04:45:12,630 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:45:12,630 INFO ]: With dead ends: 14 [2018-06-22 04:45:12,630 INFO ]: Without dead ends: 14 [2018-06-22 04:45:12,631 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=58, Invalid=98, Unknown=0, NotChecked=0, Total=156 [2018-06-22 04:45:12,631 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 04:45:12,632 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 04:45:12,632 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 04:45:12,633 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 04:45:12,633 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-22 04:45:12,633 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:45:12,633 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 04:45:12,633 INFO ]: Interpolant automaton has 12 states. [2018-06-22 04:45:12,633 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 04:45:12,633 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 04:45:12,633 INFO ]: Found error trace [2018-06-22 04:45:12,633 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:45:12,634 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:45:12,634 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 4 times [2018-06-22 04:45:12,634 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:45:12,634 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:45:12,634 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:45:12,634 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:45:12,634 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:45:12,983 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:45:13,743 WARN ]: Spent 290.00 ms on a formula simplification. DAG size of input: 97 DAG size of output: 56 [2018-06-22 04:45:13,908 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 129 DAG size of output: 52 [2018-06-22 04:45:14,195 WARN ]: Spent 267.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 53 [2018-06-22 04:45:14,270 INFO ]: Checked inductivity of 21 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 04:45:14,270 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:45:14,270 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 04:45:14,277 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 04:45:14,740 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 04:45:14,740 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:45:14,756 INFO ]: Computing forward predicates... [2018-06-22 04:45:24,914 WARN ]: Spent 7.48 s on a formula simplification. DAG size of input: 729 DAG size of output: 114 [2018-06-22 04:45:29,573 WARN ]: Simplifying disjunction of 5148 conjuctions. This might take some time... [2018-06-22 04:45:31,511 INFO ]: Simplified to disjunction of 5148 conjuctions. Received shutdown request... [2018-06-22 04:45:54,049 INFO ]: Timeout while computing interpolants [2018-06-22 04:45:54,250 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:45:54,250 WARN ]: Verification canceled [2018-06-22 04:45:54,254 WARN ]: Timeout [2018-06-22 04:45:54,254 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:45:54 BoogieIcfgContainer [2018-06-22 04:45:54,254 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 04:45:54,255 INFO ]: Toolchain (without parser) took 66731.91 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 237.3 MB in the beginning and 698.0 MB in the end (delta: -460.7 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 04:45:54,255 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 308.8 MB. Free memory is still 272.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 04:45:54,260 INFO ]: ChcToBoogie took 71.67 ms. Allocated memory is still 308.8 MB. Free memory was 237.3 MB in the beginning and 234.3 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:45:54,260 INFO ]: Boogie Preprocessor took 77.48 ms. Allocated memory is still 308.8 MB. Free memory was 234.3 MB in the beginning and 232.3 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:54,261 INFO ]: RCFGBuilder took 464.57 ms. Allocated memory is still 308.8 MB. Free memory was 232.3 MB in the beginning and 194.6 MB in the end (delta: 37.7 MB). Peak memory consumption was 37.7 MB. Max. memory is 3.6 GB. [2018-06-22 04:45:54,261 INFO ]: TraceAbstraction took 66109.52 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 194.6 MB in the beginning and 698.0 MB in the end (delta: -503.4 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 04:45:54,263 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 308.8 MB. Free memory is still 272.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 71.67 ms. Allocated memory is still 308.8 MB. Free memory was 237.3 MB in the beginning and 234.3 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 77.48 ms. Allocated memory is still 308.8 MB. Free memory was 234.3 MB in the beginning and 232.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 464.57 ms. Allocated memory is still 308.8 MB. Free memory was 232.3 MB in the beginning and 194.6 MB in the end (delta: 37.7 MB). Peak memory consumption was 37.7 MB. Max. memory is 3.6 GB. * TraceAbstraction took 66109.52 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 194.6 MB in the beginning and 698.0 MB in the end (delta: -503.4 MB). Peak memory consumption was 1.3 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 PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was transforming 0 conjuction. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 66.0s OverallTime, 5 OverallIterations, 6 TraceHistogramMax, 0.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 28 SDtfs, 4 SDslu, 66 SDs, 0 SdLazy, 31 SolverSat, 12 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 50 GetRequests, 26 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 5.9s 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.2s SsaConstructionTime, 1.1s SatisfiabilityAnalysisTime, 22.4s InterpolantComputationTime, 67 NumberOfCodeBlocks, 67 NumberOfCodeBlocksAsserted, 11 NumberOfCheckSat, 60 ConstructedInterpolants, 0 QuantifiedInterpolants, 2803 SizeOfPredicates, 12 NumberOfNonLiveVariables, 1527 ConjunctsInSsa, 94 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-4.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_04-45-54-272.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/simple_array_inversion-4.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_04-45-54-272.csv Completed graceful shutdown