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/ctigar/gulwani_cegar2.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 05:27:02,660 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 05:27:02,662 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 05:27:02,678 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 05:27:02,678 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 05:27:02,679 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 05:27:02,683 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 05:27:02,689 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 05:27:02,691 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 05:27:02,694 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 05:27:02,695 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 05:27:02,695 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 05:27:02,696 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 05:27:02,701 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 05:27:02,702 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 05:27:02,702 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 05:27:02,715 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 05:27:02,717 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 05:27:02,718 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 05:27:02,719 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 05:27:02,720 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 05:27:02,725 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 05:27:02,726 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 05:27:02,726 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 05:27:02,727 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 05:27:02,729 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 05:27:02,730 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 05:27:02,730 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 05:27:02,731 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 05:27:02,732 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 05:27:02,732 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 05:27:02,733 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 05:27:02,733 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 05:27:02,734 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 05:27:02,734 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 05:27:02,740 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 05:27:02,803 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 05:27:02,803 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 05:27:02,803 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 05:27:02,804 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 05:27:02,805 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 05:27:02,805 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 05:27:02,805 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 05:27:02,805 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 05:27:02,805 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 05:27:02,806 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 05:27:02,806 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 05:27:02,806 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 05:27:02,806 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 05:27:02,806 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 05:27:02,807 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 05:27:02,807 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 05:27:02,807 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 05:27:02,808 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 05:27:02,809 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 05:27:02,865 INFO ]: Repository-Root is: /tmp [2018-06-22 05:27:02,916 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 05:27:02,921 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 05:27:02,923 INFO ]: Initializing SmtParser... [2018-06-22 05:27:02,923 INFO ]: SmtParser initialized [2018-06-22 05:27:02,924 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/gulwani_cegar2.c.smt2 [2018-06-22 05:27:02,949 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 05:27:03,125 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/gulwani_cegar2.c.smt2 unknown [2018-06-22 05:27:03,548 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/gulwani_cegar2.c.smt2 [2018-06-22 05:27:03,553 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 05:27:03,561 INFO ]: Walking toolchain with 4 elements. [2018-06-22 05:27:03,562 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 05:27:03,562 INFO ]: Initializing ChcToBoogie... [2018-06-22 05:27:03,562 INFO ]: ChcToBoogie initialized [2018-06-22 05:27:03,653 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:27:03" (1/1) ... [2018-06-22 05:27:03,709 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03 Unit [2018-06-22 05:27:03,710 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 05:27:03,710 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 05:27:03,711 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 05:27:03,711 INFO ]: Boogie Preprocessor initialized [2018-06-22 05:27:03,736 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03" (1/1) ... [2018-06-22 05:27:03,736 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03" (1/1) ... [2018-06-22 05:27:03,743 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03" (1/1) ... [2018-06-22 05:27:03,754 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03" (1/1) ... [2018-06-22 05:27:03,758 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03" (1/1) ... [2018-06-22 05:27:03,762 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03" (1/1) ... [2018-06-22 05:27:03,764 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03" (1/1) ... [2018-06-22 05:27:03,766 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 05:27:03,766 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 05:27:03,766 INFO ]: Initializing RCFGBuilder... [2018-06-22 05:27:03,766 INFO ]: RCFGBuilder initialized [2018-06-22 05:27:03,767 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03" (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 05:27:03,791 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 05:27:03,791 INFO ]: Found specification of procedure gotoProc [2018-06-22 05:27:03,791 INFO ]: Found implementation of procedure gotoProc [2018-06-22 05:27:03,791 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 05:27:03,792 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 05:27:03,792 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 05:27:04,032 INFO ]: Using library mode [2018-06-22 05:27:04,032 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:27:04 BoogieIcfgContainer [2018-06-22 05:27:04,033 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 05:27:04,034 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 05:27:04,034 INFO ]: Initializing TraceAbstraction... [2018-06-22 05:27:04,037 INFO ]: TraceAbstraction initialized [2018-06-22 05:27:04,037 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 05:27:03" (1/3) ... [2018-06-22 05:27:04,038 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@608bb053 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 05:27:04, skipping insertion in model container [2018-06-22 05:27:04,039 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 05:27:03" (2/3) ... [2018-06-22 05:27:04,039 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@608bb053 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 05:27:04, skipping insertion in model container [2018-06-22 05:27:04,039 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 05:27:04" (3/3) ... [2018-06-22 05:27:04,042 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 05:27:04,052 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 05:27:04,061 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 05:27:04,119 INFO ]: Using default assertion order modulation [2018-06-22 05:27:04,120 INFO ]: Interprodecural is true [2018-06-22 05:27:04,120 INFO ]: Hoare is false [2018-06-22 05:27:04,120 INFO ]: Compute interpolants for FPandBP [2018-06-22 05:27:04,120 INFO ]: Backedges is TWOTRACK [2018-06-22 05:27:04,120 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 05:27:04,120 INFO ]: Difference is false [2018-06-22 05:27:04,120 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 05:27:04,120 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 05:27:04,137 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 05:27:04,148 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 05:27:04,149 INFO ]: Found error trace [2018-06-22 05:27:04,152 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:27:04,153 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:27:04,159 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 05:27:04,163 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:27:04,164 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:27:04,198 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:04,198 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:27:04,199 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:04,240 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:04,348 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:04,351 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 05:27:04,351 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 05:27:04,354 INFO ]: Interpolant automaton has 3 states [2018-06-22 05:27:04,371 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 05:27:04,372 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 05:27:04,384 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 05:27:04,470 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:27:04,470 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 05:27:04,471 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 05:27:04,472 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 05:27:04,473 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:27:04,486 INFO ]: With dead ends: 9 [2018-06-22 05:27:04,486 INFO ]: Without dead ends: 9 [2018-06-22 05:27:04,489 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 05:27:04,502 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 05:27:04,522 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 05:27:04,523 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 05:27:04,523 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 05:27:04,525 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 05:27:04,525 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:27:04,526 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 05:27:04,526 INFO ]: Interpolant automaton has 3 states. [2018-06-22 05:27:04,526 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 05:27:04,526 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 05:27:04,526 INFO ]: Found error trace [2018-06-22 05:27:04,526 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:27:04,526 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:27:04,526 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 05:27:04,526 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:27:04,527 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:27:04,528 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:04,528 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:27:04,528 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:04,575 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:04,721 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:04,721 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:27:04,721 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 05:27:04,733 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:27:04,771 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:04,779 INFO ]: Computing forward predicates... [2018-06-22 05:27:05,103 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:05,126 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:27:05,126 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 05:27:05,126 INFO ]: Interpolant automaton has 5 states [2018-06-22 05:27:05,126 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 05:27:05,127 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-22 05:27:05,127 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 05:27:05,267 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:27:05,267 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 05:27:05,268 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 05:27:05,268 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 05:27:05,268 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:27:05,268 INFO ]: With dead ends: 10 [2018-06-22 05:27:05,268 INFO ]: Without dead ends: 10 [2018-06-22 05:27:05,269 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:27:05,269 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 05:27:05,270 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 05:27:05,270 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 05:27:05,271 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 05:27:05,271 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 05:27:05,271 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:27:05,271 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 05:27:05,271 INFO ]: Interpolant automaton has 5 states. [2018-06-22 05:27:05,271 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 05:27:05,271 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 05:27:05,271 INFO ]: Found error trace [2018-06-22 05:27:05,271 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:27:05,272 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:27:05,272 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-22 05:27:05,273 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:27:05,273 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:27:05,273 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:05,273 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:27:05,273 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:05,346 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:05,555 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:05,555 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:27:05,555 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 05:27:05,562 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 05:27:05,607 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 05:27:05,607 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:05,610 INFO ]: Computing forward predicates... [2018-06-22 05:27:05,919 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 2 [2018-06-22 05:27:06,843 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:06,866 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:27:06,866 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-22 05:27:06,867 INFO ]: Interpolant automaton has 6 states [2018-06-22 05:27:06,867 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 05:27:06,867 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 05:27:06,867 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-22 05:27:07,084 WARN ]: Spent 193.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 05:27:07,153 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:27:07,153 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 05:27:07,154 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 05:27:07,154 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-22 05:27:07,154 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:27:07,155 INFO ]: With dead ends: 11 [2018-06-22 05:27:07,155 INFO ]: Without dead ends: 11 [2018-06-22 05:27:07,155 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:27:07,155 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 05:27:07,156 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 05:27:07,156 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 05:27:07,157 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 05:27:07,157 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-22 05:27:07,157 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:27:07,157 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 05:27:07,157 INFO ]: Interpolant automaton has 6 states. [2018-06-22 05:27:07,157 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 05:27:07,157 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 05:27:07,157 INFO ]: Found error trace [2018-06-22 05:27:07,157 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:27:07,157 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:27:07,158 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 3 times [2018-06-22 05:27:07,158 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:27:07,158 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:27:07,158 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:07,158 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:27:07,158 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:07,208 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:07,419 WARN ]: Spent 143.00 ms on a formula simplification. DAG size of input: 6 DAG size of output: 1 [2018-06-22 05:27:07,454 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:07,454 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:27:07,454 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 05:27:07,460 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 05:27:07,541 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 05:27:07,541 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:07,544 INFO ]: Computing forward predicates... [2018-06-22 05:27:08,572 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:08,595 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:27:08,595 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-22 05:27:08,595 INFO ]: Interpolant automaton has 7 states [2018-06-22 05:27:08,595 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 05:27:08,596 INFO ]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-22 05:27:08,596 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-22 05:27:08,782 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:27:08,782 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 05:27:08,782 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 05:27:08,782 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-22 05:27:08,782 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:27:08,782 INFO ]: With dead ends: 12 [2018-06-22 05:27:08,782 INFO ]: Without dead ends: 12 [2018-06-22 05:27:08,783 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=41, Invalid=69, Unknown=0, NotChecked=0, Total=110 [2018-06-22 05:27:08,783 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 05:27:08,784 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 05:27:08,784 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 05:27:08,784 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 05:27:08,784 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-22 05:27:08,784 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:27:08,785 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 05:27:08,785 INFO ]: Interpolant automaton has 7 states. [2018-06-22 05:27:08,785 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 05:27:08,785 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 05:27:08,785 INFO ]: Found error trace [2018-06-22 05:27:08,785 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:27:08,785 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:27:08,785 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 4 times [2018-06-22 05:27:08,785 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:27:08,785 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:27:08,786 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:08,786 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:27:08,786 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:08,819 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:09,018 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:09,018 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:27:09,018 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 05:27:09,028 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 05:27:09,060 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 05:27:09,060 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:09,063 INFO ]: Computing forward predicates... [2018-06-22 05:27:15,034 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:15,057 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:27:15,057 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-22 05:27:15,057 INFO ]: Interpolant automaton has 8 states [2018-06-22 05:27:15,057 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 05:27:15,057 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 05:27:15,058 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 8 states. [2018-06-22 05:27:15,380 WARN ]: Spent 273.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 15 [2018-06-22 05:27:15,535 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:27:15,535 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 05:27:15,535 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 05:27:15,535 INFO ]: Start accepts. Automaton has 8 states. Word has length 11 [2018-06-22 05:27:15,535 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:27:15,535 INFO ]: With dead ends: 13 [2018-06-22 05:27:15,535 INFO ]: Without dead ends: 13 [2018-06-22 05:27:15,537 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=58, Invalid=98, Unknown=0, NotChecked=0, Total=156 [2018-06-22 05:27:15,537 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 05:27:15,538 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 05:27:15,538 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 05:27:15,539 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 05:27:15,539 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-22 05:27:15,539 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:27:15,539 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 05:27:15,539 INFO ]: Interpolant automaton has 8 states. [2018-06-22 05:27:15,539 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 05:27:15,539 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 05:27:15,539 INFO ]: Found error trace [2018-06-22 05:27:15,539 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:27:15,539 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:27:15,540 INFO ]: Analyzing trace with hash -1502133097, now seen corresponding path program 5 times [2018-06-22 05:27:15,540 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:27:15,540 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:27:15,541 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:15,541 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:27:15,541 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:15,601 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:16,367 WARN ]: Spent 603.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 11 [2018-06-22 05:27:16,526 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:16,526 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:27:16,526 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) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:27:16,537 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 05:27:16,626 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-22 05:27:16,626 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:16,630 INFO ]: Computing forward predicates... [2018-06-22 05:27:19,522 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:19,578 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:27:19,578 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 05:27:19,579 INFO ]: Interpolant automaton has 13 states [2018-06-22 05:27:19,579 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 05:27:19,579 INFO ]: CoverageRelationStatistics Valid=43, Invalid=113, Unknown=0, NotChecked=0, Total=156 [2018-06-22 05:27:19,579 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 13 states. [2018-06-22 05:27:19,792 WARN ]: Spent 173.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 30 [2018-06-22 05:27:20,106 WARN ]: Spent 193.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 31 [2018-06-22 05:27:20,227 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:27:20,228 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 05:27:20,228 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 05:27:20,228 INFO ]: Start accepts. Automaton has 13 states. Word has length 12 [2018-06-22 05:27:20,228 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:27:20,228 INFO ]: With dead ends: 14 [2018-06-22 05:27:20,228 INFO ]: Without dead ends: 14 [2018-06-22 05:27:20,229 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 58 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=113, Invalid=229, Unknown=0, NotChecked=0, Total=342 [2018-06-22 05:27:20,229 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 05:27:20,230 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 05:27:20,230 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 05:27:20,230 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 05:27:20,230 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 12 [2018-06-22 05:27:20,231 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:27:20,231 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 05:27:20,231 INFO ]: Interpolant automaton has 13 states. [2018-06-22 05:27:20,231 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 05:27:20,232 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 05:27:20,232 INFO ]: Found error trace [2018-06-22 05:27:20,232 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:27:20,232 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:27:20,232 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 6 times [2018-06-22 05:27:20,232 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:27:20,232 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:27:20,233 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:20,233 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:27:20,233 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:20,268 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:20,527 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:20,527 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:27:20,527 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) [2018-06-22 05:27:20,542 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:27:20,618 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-22 05:27:20,618 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:20,631 INFO ]: Computing forward predicates... [2018-06-22 05:27:20,676 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 05:27:21,043 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 11 [2018-06-22 05:27:21,297 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 05:27:23,382 WARN ]: Spent 161.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 10 [2018-06-22 05:27:24,973 WARN ]: expecting exponential blowup for input size 7 [2018-06-22 05:27:41,601 WARN ]: Spent 558.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 16 [2018-06-22 05:27:43,577 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:43,605 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 05:27:43,605 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2018-06-22 05:27:43,606 INFO ]: Interpolant automaton has 15 states [2018-06-22 05:27:43,606 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 05:27:43,606 INFO ]: CoverageRelationStatistics Valid=53, Invalid=157, Unknown=0, NotChecked=0, Total=210 [2018-06-22 05:27:43,607 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 15 states. [2018-06-22 05:27:43,723 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 33 [2018-06-22 05:27:43,839 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 35 [2018-06-22 05:27:44,168 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 30 [2018-06-22 05:27:44,170 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 05:27:44,170 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-22 05:27:44,170 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 05:27:44,170 INFO ]: Start accepts. Automaton has 15 states. Word has length 13 [2018-06-22 05:27:44,170 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 05:27:44,170 INFO ]: With dead ends: 15 [2018-06-22 05:27:44,170 INFO ]: Without dead ends: 15 [2018-06-22 05:27:44,171 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 61 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=133, Invalid=287, Unknown=0, NotChecked=0, Total=420 [2018-06-22 05:27:44,171 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 05:27:44,172 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 05:27:44,172 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 05:27:44,172 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-22 05:27:44,172 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-06-22 05:27:44,173 INFO ]: Finished accepts. word is rejected. [2018-06-22 05:27:44,173 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-22 05:27:44,173 INFO ]: Interpolant automaton has 15 states. [2018-06-22 05:27:44,173 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-22 05:27:44,173 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-22 05:27:44,173 INFO ]: Found error trace [2018-06-22 05:27:44,173 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 05:27:44,173 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 05:27:44,173 INFO ]: Analyzing trace with hash -414382217, now seen corresponding path program 7 times [2018-06-22 05:27:44,173 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 05:27:44,173 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 05:27:44,174 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:44,174 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 05:27:44,174 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 05:27:44,242 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:44,993 WARN ]: Spent 571.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 9 [2018-06-22 05:27:45,436 WARN ]: Spent 393.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 18 [2018-06-22 05:27:45,678 WARN ]: Spent 134.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 25 [2018-06-22 05:27:45,929 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 05:27:45,929 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 05:27:45,929 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 05:27:45,937 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 05:27:45,977 INFO ]: Conjunction of SSA is unsat [2018-06-22 05:27:45,982 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 05:28:07,766 INFO ]: Timeout while computing interpolants [2018-06-22 05:28:07,967 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 05:28:07,967 WARN ]: Verification canceled [2018-06-22 05:28:07,994 WARN ]: Timeout [2018-06-22 05:28:07,994 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 05:28:07 BoogieIcfgContainer [2018-06-22 05:28:07,995 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 05:28:08,004 INFO ]: Toolchain (without parser) took 64450.30 ms. Allocated memory was 302.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 255.9 MB in the beginning and 517.2 MB in the end (delta: -261.3 MB). Peak memory consumption was 942.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:28:08,005 INFO ]: SmtParser took 0.12 ms. Allocated memory is still 302.5 MB. Free memory is still 268.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 05:28:08,005 INFO ]: ChcToBoogie took 148.12 ms. Allocated memory is still 302.5 MB. Free memory was 255.9 MB in the beginning and 253.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:28:08,006 INFO ]: Boogie Preprocessor took 55.16 ms. Allocated memory is still 302.5 MB. Free memory was 253.9 MB in the beginning and 251.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 05:28:08,006 INFO ]: RCFGBuilder took 266.51 ms. Allocated memory is still 302.5 MB. Free memory was 251.9 MB in the beginning and 242.8 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 3.6 GB. [2018-06-22 05:28:08,007 INFO ]: TraceAbstraction took 63960.60 ms. Allocated memory was 302.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 241.8 MB in the beginning and 517.2 MB in the end (delta: -275.3 MB). Peak memory consumption was 927.9 MB. Max. memory is 3.6 GB. [2018-06-22 05:28:08,009 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.12 ms. Allocated memory is still 302.5 MB. Free memory is still 268.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 148.12 ms. Allocated memory is still 302.5 MB. Free memory was 255.9 MB in the beginning and 253.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 55.16 ms. Allocated memory is still 302.5 MB. Free memory was 253.9 MB in the beginning and 251.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 266.51 ms. Allocated memory is still 302.5 MB. Free memory was 251.9 MB in the beginning and 242.8 MB in the end (delta: 9.1 MB). Peak memory consumption was 9.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 63960.60 ms. Allocated memory was 302.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 241.8 MB in the beginning and 517.2 MB in the end (delta: -275.3 MB). Peak memory consumption was 927.9 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 15 with TraceHistMax 7, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 11 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 63.8s OverallTime, 8 OverallIterations, 7 TraceHistogramMax, 2.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 49 SDtfs, 23 SDslu, 141 SDs, 0 SdLazy, 58 SolverSat, 50 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 123 GetRequests, 44 SyntacticMatches, 12 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 168 ImplicationChecksByTransitivity, 5.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=15occurred 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.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 36.5s InterpolantComputationTime, 133 NumberOfCodeBlocks, 133 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 120 ConstructedInterpolants, 0 QuantifiedInterpolants, 6303 SizeOfPredicates, 30 NumberOfNonLiveVariables, 948 ConjunctsInSsa, 203 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 0/112 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/gulwani_cegar2.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_05-28-08-021.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/gulwani_cegar2.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_05-28-08-021.csv Completed graceful shutdown