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/eldarica-misc/LIA/Consistency/graham-scan.30.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 00:43:02,543 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 00:43:02,546 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 00:43:02,557 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 00:43:02,558 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 00:43:02,558 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 00:43:02,559 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 00:43:02,563 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 00:43:02,565 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 00:43:02,565 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 00:43:02,567 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 00:43:02,567 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 00:43:02,568 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 00:43:02,569 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 00:43:02,570 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 00:43:02,572 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 00:43:02,574 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 00:43:02,583 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 00:43:02,585 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 00:43:02,585 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 00:43:02,586 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 00:43:02,591 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 00:43:02,592 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 00:43:02,592 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 00:43:02,593 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 00:43:02,593 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 00:43:02,598 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 00:43:02,598 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 00:43:02,599 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 00:43:02,599 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 00:43:02,600 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 00:43:02,600 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 00:43:02,601 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 00:43:02,605 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 00:43:02,606 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 00:43:02,606 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 00:43:02,624 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 00:43:02,624 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 00:43:02,624 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 00:43:02,625 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 00:43:02,626 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 00:43:02,626 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 00:43:02,626 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 00:43:02,626 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 00:43:02,626 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 00:43:02,627 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 00:43:02,627 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 00:43:02,627 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 00:43:02,627 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 00:43:02,627 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 00:43:02,627 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 00:43:02,628 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 00:43:02,628 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 00:43:02,629 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 00:43:02,629 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 00:43:02,676 INFO ]: Repository-Root is: /tmp [2018-06-22 00:43:02,691 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 00:43:02,696 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 00:43:02,697 INFO ]: Initializing SmtParser... [2018-06-22 00:43:02,698 INFO ]: SmtParser initialized [2018-06-22 00:43:02,698 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan.30.smt2 [2018-06-22 00:43:02,700 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 00:43:02,784 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan.30.smt2 unknown [2018-06-22 00:43:03,223 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan.30.smt2 [2018-06-22 00:43:03,229 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 00:43:03,234 INFO ]: Walking toolchain with 4 elements. [2018-06-22 00:43:03,235 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 00:43:03,235 INFO ]: Initializing ChcToBoogie... [2018-06-22 00:43:03,235 INFO ]: ChcToBoogie initialized [2018-06-22 00:43:03,238 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 12:43:03" (1/1) ... [2018-06-22 00:43:03,349 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43:03 Unit [2018-06-22 00:43:03,349 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 00:43:03,350 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 00:43:03,350 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 00:43:03,350 INFO ]: Boogie Preprocessor initialized [2018-06-22 00:43:03,367 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43:03" (1/1) ... [2018-06-22 00:43:03,367 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43:03" (1/1) ... [2018-06-22 00:43:03,378 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43:03" (1/1) ... [2018-06-22 00:43:03,378 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43:03" (1/1) ... [2018-06-22 00:43:03,396 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43:03" (1/1) ... [2018-06-22 00:43:03,404 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43:03" (1/1) ... [2018-06-22 00:43:03,407 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43:03" (1/1) ... [2018-06-22 00:43:03,417 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 00:43:03,418 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 00:43:03,418 INFO ]: Initializing RCFGBuilder... [2018-06-22 00:43:03,418 INFO ]: RCFGBuilder initialized [2018-06-22 00:43:03,419 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43: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 00:43:03,443 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 00:43:03,443 INFO ]: Found specification of procedure gotoProc [2018-06-22 00:43:03,443 INFO ]: Found implementation of procedure gotoProc [2018-06-22 00:43:03,443 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 00:43:03,443 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 00:43:03,443 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 00:43:04,667 INFO ]: Using library mode [2018-06-22 00:43:04,667 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 12:43:04 BoogieIcfgContainer [2018-06-22 00:43:04,667 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 00:43:04,669 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 00:43:04,669 INFO ]: Initializing TraceAbstraction... [2018-06-22 00:43:04,672 INFO ]: TraceAbstraction initialized [2018-06-22 00:43:04,672 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 12:43:03" (1/3) ... [2018-06-22 00:43:04,673 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@58a34180 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 12:43:04, skipping insertion in model container [2018-06-22 00:43:04,673 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 12:43:03" (2/3) ... [2018-06-22 00:43:04,673 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@58a34180 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 12:43:04, skipping insertion in model container [2018-06-22 00:43:04,673 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 12:43:04" (3/3) ... [2018-06-22 00:43:04,675 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 00:43:04,684 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 00:43:04,693 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 00:43:04,731 INFO ]: Using default assertion order modulation [2018-06-22 00:43:04,732 INFO ]: Interprodecural is true [2018-06-22 00:43:04,732 INFO ]: Hoare is false [2018-06-22 00:43:04,732 INFO ]: Compute interpolants for FPandBP [2018-06-22 00:43:04,732 INFO ]: Backedges is TWOTRACK [2018-06-22 00:43:04,732 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 00:43:04,732 INFO ]: Difference is false [2018-06-22 00:43:04,732 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 00:43:04,732 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 00:43:04,750 INFO ]: Start isEmpty. Operand 145 states. [2018-06-22 00:43:04,778 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 00:43:04,778 INFO ]: Found error trace [2018-06-22 00:43:04,779 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:43:04,779 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:43:04,783 INFO ]: Analyzing trace with hash -1432744289, now seen corresponding path program 1 times [2018-06-22 00:43:04,785 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:43:04,785 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:43:04,819 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:04,820 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:43:04,820 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:04,871 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:43:05,037 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 00:43:05,039 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 00:43:05,039 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 00:43:05,041 INFO ]: Interpolant automaton has 4 states [2018-06-22 00:43:05,051 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 00:43:05,051 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 00:43:05,053 INFO ]: Start difference. First operand 145 states. Second operand 4 states. [2018-06-22 00:43:07,661 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 00:43:07,662 INFO ]: Finished difference Result 283 states and 547 transitions. [2018-06-22 00:43:07,688 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 00:43:07,689 INFO ]: Start accepts. Automaton has 4 states. Word has length 8 [2018-06-22 00:43:07,689 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 00:43:07,733 INFO ]: With dead ends: 283 [2018-06-22 00:43:07,733 INFO ]: Without dead ends: 281 [2018-06-22 00:43:07,735 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 00:43:07,754 INFO ]: Start minimizeSevpa. Operand 281 states. [2018-06-22 00:43:07,868 INFO ]: Finished minimizeSevpa. Reduced states from 281 to 281. [2018-06-22 00:43:07,869 INFO ]: Start removeUnreachable. Operand 281 states. [2018-06-22 00:43:07,900 INFO ]: Finished removeUnreachable. Reduced from 281 states to 281 states and 545 transitions. [2018-06-22 00:43:07,903 INFO ]: Start accepts. Automaton has 281 states and 545 transitions. Word has length 8 [2018-06-22 00:43:07,904 INFO ]: Finished accepts. word is rejected. [2018-06-22 00:43:07,904 INFO ]: Abstraction has 281 states and 545 transitions. [2018-06-22 00:43:07,904 INFO ]: Interpolant automaton has 4 states. [2018-06-22 00:43:07,904 INFO ]: Start isEmpty. Operand 281 states and 545 transitions. [2018-06-22 00:43:07,918 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 00:43:07,918 INFO ]: Found error trace [2018-06-22 00:43:07,918 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:43:07,918 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:43:07,918 INFO ]: Analyzing trace with hash -1201968247, now seen corresponding path program 1 times [2018-06-22 00:43:07,918 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:43:07,918 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:43:07,920 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:07,921 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:43:07,921 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:07,938 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:43:08,065 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 00:43:08,065 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 00:43:08,065 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 00:43:08,067 INFO ]: Interpolant automaton has 4 states [2018-06-22 00:43:08,067 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 00:43:08,067 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 00:43:08,067 INFO ]: Start difference. First operand 281 states and 545 transitions. Second operand 4 states. [2018-06-22 00:43:09,927 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 00:43:09,927 INFO ]: Finished difference Result 420 states and 816 transitions. [2018-06-22 00:43:09,927 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 00:43:09,927 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 00:43:09,928 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 00:43:09,955 INFO ]: With dead ends: 420 [2018-06-22 00:43:09,955 INFO ]: Without dead ends: 420 [2018-06-22 00:43:09,956 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 00:43:09,956 INFO ]: Start minimizeSevpa. Operand 420 states. [2018-06-22 00:43:10,058 INFO ]: Finished minimizeSevpa. Reduced states from 420 to 420. [2018-06-22 00:43:10,058 INFO ]: Start removeUnreachable. Operand 420 states. [2018-06-22 00:43:10,076 INFO ]: Finished removeUnreachable. Reduced from 420 states to 420 states and 816 transitions. [2018-06-22 00:43:10,076 INFO ]: Start accepts. Automaton has 420 states and 816 transitions. Word has length 9 [2018-06-22 00:43:10,076 INFO ]: Finished accepts. word is rejected. [2018-06-22 00:43:10,076 INFO ]: Abstraction has 420 states and 816 transitions. [2018-06-22 00:43:10,076 INFO ]: Interpolant automaton has 4 states. [2018-06-22 00:43:10,076 INFO ]: Start isEmpty. Operand 420 states and 816 transitions. [2018-06-22 00:43:10,099 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 00:43:10,099 INFO ]: Found error trace [2018-06-22 00:43:10,099 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:43:10,099 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:43:10,100 INFO ]: Analyzing trace with hash -1822608226, now seen corresponding path program 1 times [2018-06-22 00:43:10,100 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:43:10,100 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:43:10,101 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:10,101 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:43:10,101 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:10,153 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:43:10,766 INFO ]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 00:43:10,766 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 00:43:10,766 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-22 00:43:10,766 INFO ]: Interpolant automaton has 7 states [2018-06-22 00:43:10,766 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-22 00:43:10,767 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-22 00:43:10,767 INFO ]: Start difference. First operand 420 states and 816 transitions. Second operand 7 states. [2018-06-22 00:43:17,236 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 00:43:17,236 INFO ]: Finished difference Result 1207 states and 5749 transitions. [2018-06-22 00:43:17,242 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 00:43:17,242 INFO ]: Start accepts. Automaton has 7 states. Word has length 17 [2018-06-22 00:43:17,242 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 00:43:17,620 INFO ]: With dead ends: 1207 [2018-06-22 00:43:17,620 INFO ]: Without dead ends: 1197 [2018-06-22 00:43:17,620 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2018-06-22 00:43:17,621 INFO ]: Start minimizeSevpa. Operand 1197 states. [2018-06-22 00:43:18,176 INFO ]: Finished minimizeSevpa. Reduced states from 1197 to 862. [2018-06-22 00:43:18,176 INFO ]: Start removeUnreachable. Operand 862 states. [2018-06-22 00:43:18,225 INFO ]: Finished removeUnreachable. Reduced from 862 states to 862 states and 2171 transitions. [2018-06-22 00:43:18,225 INFO ]: Start accepts. Automaton has 862 states and 2171 transitions. Word has length 17 [2018-06-22 00:43:18,225 INFO ]: Finished accepts. word is rejected. [2018-06-22 00:43:18,225 INFO ]: Abstraction has 862 states and 2171 transitions. [2018-06-22 00:43:18,225 INFO ]: Interpolant automaton has 7 states. [2018-06-22 00:43:18,225 INFO ]: Start isEmpty. Operand 862 states and 2171 transitions. [2018-06-22 00:43:18,270 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-22 00:43:18,271 INFO ]: Found error trace [2018-06-22 00:43:18,271 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:43:18,271 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:43:18,271 INFO ]: Analyzing trace with hash -513291236, now seen corresponding path program 1 times [2018-06-22 00:43:18,271 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:43:18,271 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:43:18,272 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:18,272 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:43:18,272 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:18,321 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:43:18,563 INFO ]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 00:43:18,564 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 00:43:18,564 INFO ]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-06-22 00:43:18,564 INFO ]: Interpolant automaton has 8 states [2018-06-22 00:43:18,564 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 00:43:18,564 INFO ]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-06-22 00:43:18,564 INFO ]: Start difference. First operand 862 states and 2171 transitions. Second operand 8 states. [2018-06-22 00:43:30,187 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 00:43:30,187 INFO ]: Finished difference Result 3501 states and 34166 transitions. [2018-06-22 00:43:30,188 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-06-22 00:43:30,188 INFO ]: Start accepts. Automaton has 8 states. Word has length 18 [2018-06-22 00:43:30,188 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 00:43:32,544 INFO ]: With dead ends: 3501 [2018-06-22 00:43:32,544 INFO ]: Without dead ends: 3468 [2018-06-22 00:43:32,544 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 138 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=152, Invalid=498, Unknown=0, NotChecked=0, Total=650 [2018-06-22 00:43:32,546 INFO ]: Start minimizeSevpa. Operand 3468 states. [2018-06-22 00:43:37,653 INFO ]: Finished minimizeSevpa. Reduced states from 3468 to 1775. [2018-06-22 00:43:37,653 INFO ]: Start removeUnreachable. Operand 1775 states. [2018-06-22 00:43:37,788 INFO ]: Finished removeUnreachable. Reduced from 1775 states to 1775 states and 6365 transitions. [2018-06-22 00:43:37,788 INFO ]: Start accepts. Automaton has 1775 states and 6365 transitions. Word has length 18 [2018-06-22 00:43:37,788 INFO ]: Finished accepts. word is rejected. [2018-06-22 00:43:37,788 INFO ]: Abstraction has 1775 states and 6365 transitions. [2018-06-22 00:43:37,788 INFO ]: Interpolant automaton has 8 states. [2018-06-22 00:43:37,788 INFO ]: Start isEmpty. Operand 1775 states and 6365 transitions. [2018-06-22 00:43:37,834 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-22 00:43:37,834 INFO ]: Found error trace [2018-06-22 00:43:37,834 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 00:43:37,834 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 00:43:37,836 INFO ]: Analyzing trace with hash -267246776, now seen corresponding path program 1 times [2018-06-22 00:43:37,836 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 00:43:37,836 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 00:43:37,837 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:37,837 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:43:37,837 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 00:43:37,870 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:43:38,061 INFO ]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 00:43:38,062 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 00:43:38,062 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 00:43:38,071 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 00:43:38,143 INFO ]: Conjunction of SSA is unsat [2018-06-22 00:43:38,157 INFO ]: Computing forward predicates... [2018-06-22 00:43:38,444 INFO ]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 00:43:38,464 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 00:43:38,464 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-22 00:43:38,464 INFO ]: Interpolant automaton has 14 states [2018-06-22 00:43:38,465 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 00:43:38,465 INFO ]: CoverageRelationStatistics Valid=25, Invalid=157, Unknown=0, NotChecked=0, Total=182 [2018-06-22 00:43:38,465 INFO ]: Start difference. First operand 1775 states and 6365 transitions. Second operand 14 states. [2018-06-22 00:43:39,420 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 27 Received shutdown request... [2018-06-22 00:44:02,318 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-06-22 00:44:02,318 WARN ]: Verification canceled [2018-06-22 00:44:02,323 WARN ]: Timeout [2018-06-22 00:44:02,323 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 12:44:02 BoogieIcfgContainer [2018-06-22 00:44:02,323 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 00:44:02,325 INFO ]: Toolchain (without parser) took 59095.16 ms. Allocated memory was 306.2 MB in the beginning and 1.6 GB in the end (delta: 1.3 GB). Free memory was 246.6 MB in the beginning and 242.3 MB in the end (delta: 4.4 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 00:44:02,327 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 306.2 MB. Free memory is still 270.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 00:44:02,327 INFO ]: ChcToBoogie took 114.75 ms. Allocated memory is still 306.2 MB. Free memory was 246.6 MB in the beginning and 242.6 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-22 00:44:02,327 INFO ]: Boogie Preprocessor took 67.58 ms. Allocated memory is still 306.2 MB. Free memory was 242.6 MB in the beginning and 240.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 00:44:02,328 INFO ]: RCFGBuilder took 1249.11 ms. Allocated memory was 306.2 MB in the beginning and 324.0 MB in the end (delta: 17.8 MB). Free memory was 240.6 MB in the beginning and 283.0 MB in the end (delta: -42.4 MB). Peak memory consumption was 61.7 MB. Max. memory is 3.6 GB. [2018-06-22 00:44:02,330 INFO ]: TraceAbstraction took 57654.89 ms. Allocated memory was 324.0 MB in the beginning and 1.6 GB in the end (delta: 1.3 GB). Free memory was 280.8 MB in the beginning and 242.3 MB in the end (delta: 38.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 00:44:02,334 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 306.2 MB. Free memory is still 270.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 114.75 ms. Allocated memory is still 306.2 MB. Free memory was 246.6 MB in the beginning and 242.6 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 67.58 ms. Allocated memory is still 306.2 MB. Free memory was 242.6 MB in the beginning and 240.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 1249.11 ms. Allocated memory was 306.2 MB in the beginning and 324.0 MB in the end (delta: 17.8 MB). Free memory was 240.6 MB in the beginning and 283.0 MB in the end (delta: -42.4 MB). Peak memory consumption was 61.7 MB. Max. memory is 3.6 GB. * TraceAbstraction took 57654.89 ms. Allocated memory was 324.0 MB in the beginning and 1.6 GB in the end (delta: 1.3 GB). Free memory was 280.8 MB in the beginning and 242.3 MB in the end (delta: 38.6 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (1775states) and interpolant automaton (currently 41 states, 14 states before enhancement), while ReachableStatesComputation was computing reachable states (6624 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 145 locations, 1 error locations. TIMEOUT Result, 57.5s OverallTime, 5 OverallIterations, 2 TraceHistogramMax, 49.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 3205 SDtfs, 1709 SDslu, 8871 SDs, 0 SdLazy, 33594 SolverSat, 9967 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 36.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 111 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 746 ImplicationChecksByTransitivity, 2.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=1775occurred in iteration=4, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 6.1s AutomataMinimizationTime, 4 MinimizatonAttempts, 2028 StatesRemovedByMinimization, 2 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 1.6s InterpolantComputationTime, 88 NumberOfCodeBlocks, 88 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 82 ConstructedInterpolants, 0 QuantifiedInterpolants, 3252 SizeOfPredicates, 10 NumberOfNonLiveVariables, 428 ConjunctsInSsa, 14 ConjunctsInUnsatCore, 6 InterpolantComputations, 4 PerfectInterpolantSequences, 16/18 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.30.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_00-44-02-344.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/graham-scan.30.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_00-44-02-344.csv Completed graceful shutdown