java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan-full.34.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 10:39:47,685 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 10:39:47,687 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 10:39:47,701 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 10:39:47,701 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 10:39:47,702 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 10:39:47,703 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 10:39:47,705 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 10:39:47,706 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 10:39:47,707 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 10:39:47,708 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 10:39:47,708 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 10:39:47,709 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 10:39:47,710 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 10:39:47,711 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 10:39:47,711 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 10:39:47,713 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 10:39:47,715 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 10:39:47,717 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 10:39:47,717 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 10:39:47,719 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 10:39:47,721 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 10:39:47,721 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 10:39:47,721 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 10:39:47,722 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 10:39:47,723 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 10:39:47,724 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 10:39:47,725 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 10:39:47,726 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 10:39:47,726 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 10:39:47,727 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 10:39:47,727 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 10:39:47,727 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 10:39:47,728 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 10:39:47,729 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 10:39:47,729 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 10:39:47,742 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 10:39:47,743 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 10:39:47,743 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 10:39:47,743 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 10:39:47,744 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 10:39:47,744 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 10:39:47,745 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 10:39:47,745 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 10:39:47,745 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 10:39:47,745 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 10:39:47,746 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 10:39:47,746 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 10:39:47,746 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 10:39:47,746 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 10:39:47,747 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 10:39:47,747 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 10:39:47,747 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 10:39:47,747 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 10:39:47,748 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 10:39:47,749 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 10:39:47,749 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 10:39:47,799 INFO ]: Repository-Root is: /tmp [2018-06-22 10:39:47,816 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 10:39:47,821 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 10:39:47,823 INFO ]: Initializing SmtParser... [2018-06-22 10:39:47,823 INFO ]: SmtParser initialized [2018-06-22 10:39:47,823 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan-full.34.smt2 [2018-06-22 10:39:47,824 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 10:39:47,919 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan-full.34.smt2 unknown [2018-06-22 10:39:48,445 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan-full.34.smt2 [2018-06-22 10:39:48,452 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 10:39:48,460 INFO ]: Walking toolchain with 4 elements. [2018-06-22 10:39:48,465 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 10:39:48,465 INFO ]: Initializing ChcToBoogie... [2018-06-22 10:39:48,465 INFO ]: ChcToBoogie initialized [2018-06-22 10:39:48,468 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 10:39:48" (1/1) ... [2018-06-22 10:39:48,551 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48 Unit [2018-06-22 10:39:48,551 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 10:39:48,552 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 10:39:48,552 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 10:39:48,552 INFO ]: Boogie Preprocessor initialized [2018-06-22 10:39:48,574 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48" (1/1) ... [2018-06-22 10:39:48,574 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48" (1/1) ... [2018-06-22 10:39:48,593 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48" (1/1) ... [2018-06-22 10:39:48,593 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48" (1/1) ... [2018-06-22 10:39:48,613 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48" (1/1) ... [2018-06-22 10:39:48,617 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48" (1/1) ... [2018-06-22 10:39:48,620 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48" (1/1) ... [2018-06-22 10:39:48,624 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 10:39:48,624 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 10:39:48,624 INFO ]: Initializing RCFGBuilder... [2018-06-22 10:39:48,624 INFO ]: RCFGBuilder initialized [2018-06-22 10:39:48,625 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48" (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 10:39:48,643 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 10:39:48,643 INFO ]: Found specification of procedure False [2018-06-22 10:39:48,643 INFO ]: Found implementation of procedure False [2018-06-22 10:39:48,643 INFO ]: Specification and implementation of procedure step_lturn__bar given in one single declaration [2018-06-22 10:39:48,643 INFO ]: Found specification of procedure step_lturn__bar [2018-06-22 10:39:48,643 INFO ]: Found implementation of procedure step_lturn__bar [2018-06-22 10:39:48,643 INFO ]: Specification and implementation of procedure combined_lturn__bar given in one single declaration [2018-06-22 10:39:48,643 INFO ]: Found specification of procedure combined_lturn__bar [2018-06-22 10:39:48,643 INFO ]: Found implementation of procedure combined_lturn__bar [2018-06-22 10:39:48,643 INFO ]: Specification and implementation of procedure lturn__bar given in one single declaration [2018-06-22 10:39:48,643 INFO ]: Found specification of procedure lturn__bar [2018-06-22 10:39:48,643 INFO ]: Found implementation of procedure lturn__bar [2018-06-22 10:39:48,643 INFO ]: Specification and implementation of procedure step_lturn given in one single declaration [2018-06-22 10:39:48,643 INFO ]: Found specification of procedure step_lturn [2018-06-22 10:39:48,643 INFO ]: Found implementation of procedure step_lturn [2018-06-22 10:39:48,643 INFO ]: Specification and implementation of procedure combined_lturn given in one single declaration [2018-06-22 10:39:48,643 INFO ]: Found specification of procedure combined_lturn [2018-06-22 10:39:48,643 INFO ]: Found implementation of procedure combined_lturn [2018-06-22 10:39:48,643 INFO ]: Specification and implementation of procedure lturn given in one single declaration [2018-06-22 10:39:48,643 INFO ]: Found specification of procedure lturn [2018-06-22 10:39:48,643 INFO ]: Found implementation of procedure lturn [2018-06-22 10:39:48,643 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 10:39:48,643 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 10:39:48,643 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 10:39:49,475 INFO ]: Using library mode [2018-06-22 10:39:49,475 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 10:39:49 BoogieIcfgContainer [2018-06-22 10:39:49,475 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 10:39:49,477 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 10:39:49,477 INFO ]: Initializing TraceAbstraction... [2018-06-22 10:39:49,480 INFO ]: TraceAbstraction initialized [2018-06-22 10:39:49,481 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 10:39:48" (1/3) ... [2018-06-22 10:39:49,482 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@49e4931b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 10:39:49, skipping insertion in model container [2018-06-22 10:39:49,482 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 10:39:48" (2/3) ... [2018-06-22 10:39:49,482 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@49e4931b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 10:39:49, skipping insertion in model container [2018-06-22 10:39:49,482 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 10:39:49" (3/3) ... [2018-06-22 10:39:49,484 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 10:39:49,494 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 10:39:49,505 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 10:39:49,551 INFO ]: Using default assertion order modulation [2018-06-22 10:39:49,551 INFO ]: Interprodecural is true [2018-06-22 10:39:49,551 INFO ]: Hoare is false [2018-06-22 10:39:49,551 INFO ]: Compute interpolants for FPandBP [2018-06-22 10:39:49,551 INFO ]: Backedges is TWOTRACK [2018-06-22 10:39:49,551 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 10:39:49,551 INFO ]: Difference is false [2018-06-22 10:39:49,551 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 10:39:49,551 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 10:39:49,576 INFO ]: Start isEmpty. Operand 162 states. [2018-06-22 10:39:49,612 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 10:39:49,612 INFO ]: Found error trace [2018-06-22 10:39:49,613 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 10:39:49,614 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 10:39:49,619 INFO ]: Analyzing trace with hash -137161682, now seen corresponding path program 1 times [2018-06-22 10:39:49,620 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 10:39:49,621 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 10:39:49,675 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:39:49,675 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:39:49,675 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:39:49,866 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:39:50,440 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 10:39:50,442 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 10:39:50,442 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-06-22 10:39:50,444 INFO ]: Interpolant automaton has 6 states [2018-06-22 10:39:50,459 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 10:39:50,459 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-22 10:39:50,462 INFO ]: Start difference. First operand 162 states. Second operand 6 states. [2018-06-22 10:39:53,290 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 10:39:53,290 INFO ]: Finished difference Result 244 states and 622 transitions. [2018-06-22 10:39:53,291 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 10:39:53,292 INFO ]: Start accepts. Automaton has 6 states. Word has length 17 [2018-06-22 10:39:53,292 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 10:39:53,317 INFO ]: With dead ends: 244 [2018-06-22 10:39:53,317 INFO ]: Without dead ends: 241 [2018-06-22 10:39:53,318 INFO ]: 0 DeclaredPredicates, 6 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-22 10:39:53,333 INFO ]: Start minimizeSevpa. Operand 241 states. [2018-06-22 10:39:53,463 INFO ]: Finished minimizeSevpa. Reduced states from 241 to 226. [2018-06-22 10:39:53,464 INFO ]: Start removeUnreachable. Operand 226 states. [2018-06-22 10:39:53,471 INFO ]: Finished removeUnreachable. Reduced from 226 states to 226 states and 581 transitions. [2018-06-22 10:39:53,472 INFO ]: Start accepts. Automaton has 226 states and 581 transitions. Word has length 17 [2018-06-22 10:39:53,473 INFO ]: Finished accepts. word is rejected. [2018-06-22 10:39:53,473 INFO ]: Abstraction has 226 states and 581 transitions. [2018-06-22 10:39:53,473 INFO ]: Interpolant automaton has 6 states. [2018-06-22 10:39:53,473 INFO ]: Start isEmpty. Operand 226 states and 581 transitions. [2018-06-22 10:39:53,483 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 10:39:53,483 INFO ]: Found error trace [2018-06-22 10:39:53,483 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 10:39:53,483 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 10:39:53,483 INFO ]: Analyzing trace with hash -1104709666, now seen corresponding path program 1 times [2018-06-22 10:39:53,483 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 10:39:53,483 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 10:39:53,484 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:39:53,484 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:39:53,484 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:39:53,529 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:39:53,806 INFO ]: Checked inductivity of 3 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 10:39:53,806 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 10:39:53,806 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-22 10:39:53,810 INFO ]: Interpolant automaton has 7 states [2018-06-22 10:39:53,810 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 10:39:53,810 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 10:39:53,810 INFO ]: Start difference. First operand 226 states and 581 transitions. Second operand 7 states. [2018-06-22 10:39:56,321 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 10:39:56,322 INFO ]: Finished difference Result 422 states and 1572 transitions. [2018-06-22 10:39:56,325 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 10:39:56,325 INFO ]: Start accepts. Automaton has 7 states. Word has length 25 [2018-06-22 10:39:56,325 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 10:39:56,342 INFO ]: With dead ends: 422 [2018-06-22 10:39:56,342 INFO ]: Without dead ends: 421 [2018-06-22 10:39:56,342 INFO ]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 10:39:56,344 INFO ]: Start minimizeSevpa. Operand 421 states. [2018-06-22 10:39:56,507 INFO ]: Finished minimizeSevpa. Reduced states from 421 to 400. [2018-06-22 10:39:56,507 INFO ]: Start removeUnreachable. Operand 400 states. [2018-06-22 10:39:56,516 INFO ]: Finished removeUnreachable. Reduced from 400 states to 400 states and 1499 transitions. [2018-06-22 10:39:56,516 INFO ]: Start accepts. Automaton has 400 states and 1499 transitions. Word has length 25 [2018-06-22 10:39:56,516 INFO ]: Finished accepts. word is rejected. [2018-06-22 10:39:56,516 INFO ]: Abstraction has 400 states and 1499 transitions. [2018-06-22 10:39:56,516 INFO ]: Interpolant automaton has 7 states. [2018-06-22 10:39:56,516 INFO ]: Start isEmpty. Operand 400 states and 1499 transitions. [2018-06-22 10:39:56,528 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 10:39:56,528 INFO ]: Found error trace [2018-06-22 10:39:56,529 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 10:39:56,529 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 10:39:56,529 INFO ]: Analyzing trace with hash -1674777436, now seen corresponding path program 1 times [2018-06-22 10:39:56,529 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 10:39:56,529 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 10:39:56,530 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:39:56,530 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:39:56,530 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:39:56,557 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:39:56,733 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 10:39:56,733 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 10:39:56,733 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-22 10:39:56,733 INFO ]: Interpolant automaton has 7 states [2018-06-22 10:39:56,733 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 10:39:56,733 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 10:39:56,734 INFO ]: Start difference. First operand 400 states and 1499 transitions. Second operand 7 states. [2018-06-22 10:39:58,170 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 10:39:58,170 INFO ]: Finished difference Result 505 states and 2023 transitions. [2018-06-22 10:39:58,170 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 10:39:58,170 INFO ]: Start accepts. Automaton has 7 states. Word has length 21 [2018-06-22 10:39:58,170 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 10:39:58,186 INFO ]: With dead ends: 505 [2018-06-22 10:39:58,186 INFO ]: Without dead ends: 505 [2018-06-22 10:39:58,187 INFO ]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 10:39:58,187 INFO ]: Start minimizeSevpa. Operand 505 states. [2018-06-22 10:39:58,396 INFO ]: Finished minimizeSevpa. Reduced states from 505 to 497. [2018-06-22 10:39:58,396 INFO ]: Start removeUnreachable. Operand 497 states. [2018-06-22 10:39:58,406 INFO ]: Finished removeUnreachable. Reduced from 497 states to 497 states and 1994 transitions. [2018-06-22 10:39:58,406 INFO ]: Start accepts. Automaton has 497 states and 1994 transitions. Word has length 21 [2018-06-22 10:39:58,406 INFO ]: Finished accepts. word is rejected. [2018-06-22 10:39:58,406 INFO ]: Abstraction has 497 states and 1994 transitions. [2018-06-22 10:39:58,406 INFO ]: Interpolant automaton has 7 states. [2018-06-22 10:39:58,406 INFO ]: Start isEmpty. Operand 497 states and 1994 transitions. [2018-06-22 10:39:58,417 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 10:39:58,417 INFO ]: Found error trace [2018-06-22 10:39:58,417 INFO ]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 10:39:58,417 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 10:39:58,417 INFO ]: Analyzing trace with hash -110673493, now seen corresponding path program 1 times [2018-06-22 10:39:58,417 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 10:39:58,417 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 10:39:58,418 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:39:58,418 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:39:58,418 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:39:58,446 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:39:58,626 INFO ]: Checked inductivity of 7 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 10:39:58,626 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 10:39:58,626 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-22 10:39:58,626 INFO ]: Interpolant automaton has 7 states [2018-06-22 10:39:58,626 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 10:39:58,626 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 10:39:58,626 INFO ]: Start difference. First operand 497 states and 1994 transitions. Second operand 7 states. [2018-06-22 10:39:59,539 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 10:39:59,539 INFO ]: Finished difference Result 548 states and 3416 transitions. [2018-06-22 10:39:59,540 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 10:39:59,540 INFO ]: Start accepts. Automaton has 7 states. Word has length 29 [2018-06-22 10:39:59,540 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 10:39:59,564 INFO ]: With dead ends: 548 [2018-06-22 10:39:59,564 INFO ]: Without dead ends: 548 [2018-06-22 10:39:59,565 INFO ]: 0 DeclaredPredicates, 9 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 10:39:59,565 INFO ]: Start minimizeSevpa. Operand 548 states. [2018-06-22 10:40:00,042 INFO ]: Finished minimizeSevpa. Reduced states from 548 to 514. [2018-06-22 10:40:00,042 INFO ]: Start removeUnreachable. Operand 514 states. [2018-06-22 10:40:00,056 INFO ]: Finished removeUnreachable. Reduced from 514 states to 514 states and 2601 transitions. [2018-06-22 10:40:00,056 INFO ]: Start accepts. Automaton has 514 states and 2601 transitions. Word has length 29 [2018-06-22 10:40:00,056 INFO ]: Finished accepts. word is rejected. [2018-06-22 10:40:00,056 INFO ]: Abstraction has 514 states and 2601 transitions. [2018-06-22 10:40:00,056 INFO ]: Interpolant automaton has 7 states. [2018-06-22 10:40:00,056 INFO ]: Start isEmpty. Operand 514 states and 2601 transitions. [2018-06-22 10:40:00,067 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 10:40:00,067 INFO ]: Found error trace [2018-06-22 10:40:00,067 INFO ]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 10:40:00,067 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 10:40:00,068 INFO ]: Analyzing trace with hash 155460298, now seen corresponding path program 1 times [2018-06-22 10:40:00,068 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 10:40:00,068 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 10:40:00,068 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:00,068 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:40:00,069 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:00,099 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:40:00,687 INFO ]: Checked inductivity of 13 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-22 10:40:00,687 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 10:40:00,687 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 10:40:00,760 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:40:00,840 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:40:00,855 INFO ]: Computing forward predicates... [2018-06-22 10:40:01,171 INFO ]: Checked inductivity of 13 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-22 10:40:01,193 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 10:40:01,194 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 9] total 14 [2018-06-22 10:40:01,194 INFO ]: Interpolant automaton has 14 states [2018-06-22 10:40:01,194 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 10:40:01,194 INFO ]: CoverageRelationStatistics Valid=25, Invalid=157, Unknown=0, NotChecked=0, Total=182 [2018-06-22 10:40:01,194 INFO ]: Start difference. First operand 514 states and 2601 transitions. Second operand 14 states. [2018-06-22 10:40:09,276 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 10:40:09,276 INFO ]: Finished difference Result 835 states and 7720 transitions. [2018-06-22 10:40:09,278 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 10:40:09,278 INFO ]: Start accepts. Automaton has 14 states. Word has length 29 [2018-06-22 10:40:09,278 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 10:40:09,351 INFO ]: With dead ends: 835 [2018-06-22 10:40:09,351 INFO ]: Without dead ends: 835 [2018-06-22 10:40:09,352 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=92, Invalid=508, Unknown=0, NotChecked=0, Total=600 [2018-06-22 10:40:09,352 INFO ]: Start minimizeSevpa. Operand 835 states. [2018-06-22 10:40:10,265 INFO ]: Finished minimizeSevpa. Reduced states from 835 to 809. [2018-06-22 10:40:10,265 INFO ]: Start removeUnreachable. Operand 809 states. [2018-06-22 10:40:10,314 INFO ]: Finished removeUnreachable. Reduced from 809 states to 809 states and 7472 transitions. [2018-06-22 10:40:10,314 INFO ]: Start accepts. Automaton has 809 states and 7472 transitions. Word has length 29 [2018-06-22 10:40:10,314 INFO ]: Finished accepts. word is rejected. [2018-06-22 10:40:10,314 INFO ]: Abstraction has 809 states and 7472 transitions. [2018-06-22 10:40:10,314 INFO ]: Interpolant automaton has 14 states. [2018-06-22 10:40:10,315 INFO ]: Start isEmpty. Operand 809 states and 7472 transitions. [2018-06-22 10:40:10,330 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 10:40:10,330 INFO ]: Found error trace [2018-06-22 10:40:10,330 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 10:40:10,330 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 10:40:10,331 INFO ]: Analyzing trace with hash 487356356, now seen corresponding path program 1 times [2018-06-22 10:40:10,331 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 10:40:10,331 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 10:40:10,332 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:10,332 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:40:10,332 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:10,364 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:40:10,538 INFO ]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-22 10:40:10,538 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 10:40:10,538 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 10:40:10,553 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:40:10,606 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:40:10,615 INFO ]: Computing forward predicates... [2018-06-22 10:40:10,828 INFO ]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-22 10:40:10,849 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 10:40:10,849 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-06-22 10:40:10,849 INFO ]: Interpolant automaton has 16 states [2018-06-22 10:40:10,849 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 10:40:10,849 INFO ]: CoverageRelationStatistics Valid=29, Invalid=211, Unknown=0, NotChecked=0, Total=240 [2018-06-22 10:40:10,850 INFO ]: Start difference. First operand 809 states and 7472 transitions. Second operand 16 states. [2018-06-22 10:40:18,291 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 10:40:18,291 INFO ]: Finished difference Result 1554 states and 24393 transitions. [2018-06-22 10:40:18,291 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 10:40:18,291 INFO ]: Start accepts. Automaton has 16 states. Word has length 29 [2018-06-22 10:40:18,291 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 10:40:18,539 INFO ]: With dead ends: 1554 [2018-06-22 10:40:18,539 INFO ]: Without dead ends: 1554 [2018-06-22 10:40:18,539 INFO ]: 0 DeclaredPredicates, 44 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=57, Invalid=449, Unknown=0, NotChecked=0, Total=506 [2018-06-22 10:40:18,540 INFO ]: Start minimizeSevpa. Operand 1554 states. [2018-06-22 10:40:20,624 INFO ]: Finished minimizeSevpa. Reduced states from 1554 to 1469. [2018-06-22 10:40:20,624 INFO ]: Start removeUnreachable. Operand 1469 states. [2018-06-22 10:40:20,735 INFO ]: Finished removeUnreachable. Reduced from 1469 states to 1469 states and 22926 transitions. [2018-06-22 10:40:20,736 INFO ]: Start accepts. Automaton has 1469 states and 22926 transitions. Word has length 29 [2018-06-22 10:40:20,736 INFO ]: Finished accepts. word is rejected. [2018-06-22 10:40:20,736 INFO ]: Abstraction has 1469 states and 22926 transitions. [2018-06-22 10:40:20,736 INFO ]: Interpolant automaton has 16 states. [2018-06-22 10:40:20,736 INFO ]: Start isEmpty. Operand 1469 states and 22926 transitions. [2018-06-22 10:40:20,755 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 10:40:20,755 INFO ]: Found error trace [2018-06-22 10:40:20,755 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 10:40:20,755 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 10:40:20,758 INFO ]: Analyzing trace with hash 203618877, now seen corresponding path program 2 times [2018-06-22 10:40:20,758 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 10:40:20,758 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 10:40:20,759 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:20,759 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:40:20,759 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:20,786 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:40:21,125 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 10:40:21,125 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 10:40:21,125 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) [2018-06-22 10:40:21,144 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 10:40:21,204 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 10:40:21,204 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:40:21,207 INFO ]: Computing forward predicates... [2018-06-22 10:40:21,295 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 10:40:21,315 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 10:40:21,315 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-22 10:40:21,315 INFO ]: Interpolant automaton has 14 states [2018-06-22 10:40:21,315 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 10:40:21,315 INFO ]: CoverageRelationStatistics Valid=25, Invalid=157, Unknown=0, NotChecked=0, Total=182 [2018-06-22 10:40:21,316 INFO ]: Start difference. First operand 1469 states and 22926 transitions. Second operand 14 states. [2018-06-22 10:40:27,987 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 10:40:27,988 INFO ]: Finished difference Result 3332 states and 56372 transitions. [2018-06-22 10:40:27,988 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-22 10:40:27,988 INFO ]: Start accepts. Automaton has 14 states. Word has length 25 [2018-06-22 10:40:27,988 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 10:40:28,369 INFO ]: With dead ends: 3332 [2018-06-22 10:40:28,369 INFO ]: Without dead ends: 3326 [2018-06-22 10:40:28,369 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=60, Invalid=402, Unknown=0, NotChecked=0, Total=462 [2018-06-22 10:40:28,372 INFO ]: Start minimizeSevpa. Operand 3326 states. [2018-06-22 10:40:32,683 INFO ]: Finished minimizeSevpa. Reduced states from 3326 to 2675. [2018-06-22 10:40:32,683 INFO ]: Start removeUnreachable. Operand 2675 states. [2018-06-22 10:40:32,931 INFO ]: Finished removeUnreachable. Reduced from 2675 states to 2675 states and 45767 transitions. [2018-06-22 10:40:32,931 INFO ]: Start accepts. Automaton has 2675 states and 45767 transitions. Word has length 25 [2018-06-22 10:40:32,931 INFO ]: Finished accepts. word is rejected. [2018-06-22 10:40:32,931 INFO ]: Abstraction has 2675 states and 45767 transitions. [2018-06-22 10:40:32,931 INFO ]: Interpolant automaton has 14 states. [2018-06-22 10:40:32,931 INFO ]: Start isEmpty. Operand 2675 states and 45767 transitions. [2018-06-22 10:40:32,954 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 10:40:32,954 INFO ]: Found error trace [2018-06-22 10:40:32,954 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 10:40:32,954 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 10:40:32,954 INFO ]: Analyzing trace with hash -1717180170, now seen corresponding path program 1 times [2018-06-22 10:40:32,954 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 10:40:32,954 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 10:40:32,956 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:32,956 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 10:40:32,956 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:32,979 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:40:33,199 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 10:40:33,199 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 10:40:33,199 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-22 10:40:33,200 INFO ]: Interpolant automaton has 7 states [2018-06-22 10:40:33,200 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 10:40:33,200 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 10:40:33,200 INFO ]: Start difference. First operand 2675 states and 45767 transitions. Second operand 7 states. [2018-06-22 10:40:34,379 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 10:40:34,380 INFO ]: Finished difference Result 2868 states and 51085 transitions. [2018-06-22 10:40:34,380 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 10:40:34,380 INFO ]: Start accepts. Automaton has 7 states. Word has length 21 [2018-06-22 10:40:34,380 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 10:40:34,824 INFO ]: With dead ends: 2868 [2018-06-22 10:40:34,824 INFO ]: Without dead ends: 2868 [2018-06-22 10:40:34,824 INFO ]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 10:40:34,825 INFO ]: Start minimizeSevpa. Operand 2868 states. [2018-06-22 10:40:39,541 INFO ]: Finished minimizeSevpa. Reduced states from 2868 to 2846. [2018-06-22 10:40:39,541 INFO ]: Start removeUnreachable. Operand 2846 states. [2018-06-22 10:40:39,772 INFO ]: Finished removeUnreachable. Reduced from 2846 states to 2846 states and 50844 transitions. [2018-06-22 10:40:39,772 INFO ]: Start accepts. Automaton has 2846 states and 50844 transitions. Word has length 21 [2018-06-22 10:40:39,772 INFO ]: Finished accepts. word is rejected. [2018-06-22 10:40:39,772 INFO ]: Abstraction has 2846 states and 50844 transitions. [2018-06-22 10:40:39,772 INFO ]: Interpolant automaton has 7 states. [2018-06-22 10:40:39,772 INFO ]: Start isEmpty. Operand 2846 states and 50844 transitions. [2018-06-22 10:40:39,792 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 10:40:39,792 INFO ]: Found error trace [2018-06-22 10:40:39,792 INFO ]: trace histogram [5, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 10:40:39,792 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 10:40:39,792 INFO ]: Analyzing trace with hash -1714641878, now seen corresponding path program 1 times [2018-06-22 10:40:39,793 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 10:40:39,793 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 10:40:39,794 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:39,794 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:40:39,794 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 10:40:39,812 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:40:40,123 INFO ]: Checked inductivity of 37 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2018-06-22 10:40:40,123 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 10:40:40,123 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 10:40:40,129 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 10:40:40,187 INFO ]: Conjunction of SSA is unsat [2018-06-22 10:40:40,194 INFO ]: Computing forward predicates... [2018-06-22 10:40:40,295 INFO ]: Checked inductivity of 37 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-22 10:40:40,316 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 10:40:40,316 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 10] total 16 [2018-06-22 10:40:40,316 INFO ]: Interpolant automaton has 16 states [2018-06-22 10:40:40,316 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 10:40:40,316 INFO ]: CoverageRelationStatistics Valid=29, Invalid=211, Unknown=0, NotChecked=0, Total=240 [2018-06-22 10:40:40,317 INFO ]: Start difference. First operand 2846 states and 50844 transitions. Second operand 16 states. Received shutdown request... [2018-06-22 10:40:47,816 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-06-22 10:40:47,816 WARN ]: Verification canceled [2018-06-22 10:40:47,822 WARN ]: Timeout [2018-06-22 10:40:47,822 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 10:40:47 BoogieIcfgContainer [2018-06-22 10:40:47,822 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 10:40:47,823 INFO ]: Toolchain (without parser) took 59370.78 ms. Allocated memory was 309.3 MB in the beginning and 1.6 GB in the end (delta: 1.3 GB). Free memory was 251.8 MB in the beginning and 938.4 MB in the end (delta: -686.7 MB). Peak memory consumption was 591.6 MB. Max. memory is 3.6 GB. [2018-06-22 10:40:47,825 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 309.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 10:40:47,825 INFO ]: ChcToBoogie took 86.46 ms. Allocated memory is still 309.3 MB. Free memory was 249.8 MB in the beginning and 247.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 10:40:47,826 INFO ]: Boogie Preprocessor took 71.95 ms. Allocated memory is still 309.3 MB. Free memory was 247.8 MB in the beginning and 245.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 10:40:47,826 INFO ]: RCFGBuilder took 851.44 ms. Allocated memory is still 309.3 MB. Free memory was 245.8 MB in the beginning and 197.9 MB in the end (delta: 47.9 MB). Peak memory consumption was 47.9 MB. Max. memory is 3.6 GB. [2018-06-22 10:40:47,827 INFO ]: TraceAbstraction took 58345.15 ms. Allocated memory was 309.3 MB in the beginning and 1.6 GB in the end (delta: 1.3 GB). Free memory was 197.9 MB in the beginning and 938.4 MB in the end (delta: -740.5 MB). Peak memory consumption was 537.7 MB. Max. memory is 3.6 GB. [2018-06-22 10:40:47,831 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 309.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 86.46 ms. Allocated memory is still 309.3 MB. Free memory was 249.8 MB in the beginning and 247.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 71.95 ms. Allocated memory is still 309.3 MB. Free memory was 247.8 MB in the beginning and 245.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 851.44 ms. Allocated memory is still 309.3 MB. Free memory was 245.8 MB in the beginning and 197.9 MB in the end (delta: 47.9 MB). Peak memory consumption was 47.9 MB. Max. memory is 3.6 GB. * TraceAbstraction took 58345.15 ms. Allocated memory was 309.3 MB in the beginning and 1.6 GB in the end (delta: 1.3 GB). Free memory was 197.9 MB in the beginning and 938.4 MB in the end (delta: -740.5 MB). Peak memory consumption was 537.7 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 constructing difference of abstraction (2846states) and interpolant automaton (currently 60 states, 16 states before enhancement), while ReachableStatesComputation was computing reachable states (2477 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 8 procedures, 162 locations, 1 error locations. TIMEOUT Result, 58.2s OverallTime, 9 OverallIterations, 5 TraceHistogramMax, 39.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 4233 SDtfs, 312 SDslu, 32278 SDs, 0 SdLazy, 37855 SolverSat, 2983 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 31.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 294 GetRequests, 148 SyntacticMatches, 0 SemanticMatches, 146 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 973 ImplicationChecksByTransitivity, 3.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=2846occurred in iteration=8, 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: 13.6s AutomataMinimizationTime, 8 MinimizatonAttempts, 862 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 3.5s InterpolantComputationTime, 353 NumberOfCodeBlocks, 353 NumberOfCodeBlocksAsserted, 14 NumberOfCheckSat, 340 ConstructedInterpolants, 0 QuantifiedInterpolants, 27000 SizeOfPredicates, 25 NumberOfNonLiveVariables, 1853 ConjunctsInSsa, 87 ConjunctsInUnsatCore, 13 InterpolantComputations, 5 PerfectInterpolantSequences, 74/136 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/graham-scan-full.34.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_10-40-47-849.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/graham-scan-full.34.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_10-40-47-849.csv Completed graceful shutdown