java -Xss4m -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-full.31.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 08:29:24,130 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 08:29:24,132 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 08:29:24,144 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 08:29:24,145 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 08:29:24,146 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 08:29:24,147 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 08:29:24,149 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 08:29:24,150 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 08:29:24,151 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 08:29:24,152 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 08:29:24,152 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 08:29:24,153 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 08:29:24,154 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 08:29:24,155 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 08:29:24,156 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 08:29:24,158 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 08:29:24,160 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 08:29:24,162 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 08:29:24,163 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 08:29:24,164 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 08:29:24,167 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 08:29:24,167 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 08:29:24,167 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 08:29:24,168 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 08:29:24,169 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 08:29:24,170 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 08:29:24,171 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 08:29:24,172 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 08:29:24,172 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 08:29:24,173 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 08:29:24,173 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 08:29:24,174 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 08:29:24,175 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 08:29:24,175 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 08:29:24,176 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 08:29:24,190 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 08:29:24,190 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 08:29:24,191 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 08:29:24,191 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 08:29:24,192 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 08:29:24,192 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 08:29:24,192 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 08:29:24,192 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 08:29:24,193 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 08:29:24,193 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 08:29:24,193 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 08:29:24,193 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 08:29:24,194 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 08:29:24,194 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 08:29:24,194 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 08:29:24,194 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 08:29:24,194 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 08:29:24,195 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 08:29:24,195 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 08:29:24,195 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 08:29:24,195 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 08:29:24,197 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 08:29:24,197 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 08:29:24,247 INFO ]: Repository-Root is: /tmp [2018-06-25 08:29:24,264 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 08:29:24,269 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 08:29:24,270 INFO ]: Initializing SmtParser... [2018-06-25 08:29:24,271 INFO ]: SmtParser initialized [2018-06-25 08:29:24,271 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan-full.31.smt2 [2018-06-25 08:29:24,273 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-25 08:29:24,366 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan-full.31.smt2 unknown [2018-06-25 08:29:24,909 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/graham-scan-full.31.smt2 [2018-06-25 08:29:24,913 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 08:29:24,920 INFO ]: Walking toolchain with 4 elements. [2018-06-25 08:29:24,920 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 08:29:24,920 INFO ]: Initializing ChcToBoogie... [2018-06-25 08:29:24,921 INFO ]: ChcToBoogie initialized [2018-06-25 08:29:24,924 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 08:29:24" (1/1) ... [2018-06-25 08:29:25,036 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25 Unit [2018-06-25 08:29:25,036 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 08:29:25,037 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 08:29:25,037 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 08:29:25,037 INFO ]: Boogie Preprocessor initialized [2018-06-25 08:29:25,059 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25" (1/1) ... [2018-06-25 08:29:25,059 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25" (1/1) ... [2018-06-25 08:29:25,072 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25" (1/1) ... [2018-06-25 08:29:25,072 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25" (1/1) ... [2018-06-25 08:29:25,095 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25" (1/1) ... [2018-06-25 08:29:25,105 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25" (1/1) ... [2018-06-25 08:29:25,110 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25" (1/1) ... [2018-06-25 08:29:25,115 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 08:29:25,116 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 08:29:25,116 INFO ]: Initializing RCFGBuilder... [2018-06-25 08:29:25,116 INFO ]: RCFGBuilder initialized [2018-06-25 08:29:25,123 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25" (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) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 08:29:25,139 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 08:29:25,139 INFO ]: Found specification of procedure gotoProc [2018-06-25 08:29:25,139 INFO ]: Found implementation of procedure gotoProc [2018-06-25 08:29:25,139 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 08:29:25,139 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 08:29:25,139 INFO ]: Found implementation of procedure Ultimate.START [2018-06-25 08:29:26,633 INFO ]: Using library mode [2018-06-25 08:29:26,634 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 08:29:26 BoogieIcfgContainer [2018-06-25 08:29:26,634 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 08:29:26,635 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 08:29:26,635 INFO ]: Initializing TraceAbstraction... [2018-06-25 08:29:26,642 INFO ]: TraceAbstraction initialized [2018-06-25 08:29:26,642 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 08:29:24" (1/3) ... [2018-06-25 08:29:26,643 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@806ff8d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 08:29:26, skipping insertion in model container [2018-06-25 08:29:26,643 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:29:25" (2/3) ... [2018-06-25 08:29:26,643 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@806ff8d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 08:29:26, skipping insertion in model container [2018-06-25 08:29:26,643 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 08:29:26" (3/3) ... [2018-06-25 08:29:26,645 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 08:29:26,654 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 08:29:26,664 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 08:29:26,720 INFO ]: Using default assertion order modulation [2018-06-25 08:29:26,721 INFO ]: Interprodecural is true [2018-06-25 08:29:26,721 INFO ]: Hoare is false [2018-06-25 08:29:26,721 INFO ]: Compute interpolants for FPandBP [2018-06-25 08:29:26,721 INFO ]: Backedges is TWOTRACK [2018-06-25 08:29:26,721 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 08:29:26,721 INFO ]: Difference is false [2018-06-25 08:29:26,721 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 08:29:26,721 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 08:29:26,741 INFO ]: Start isEmpty. Operand 145 states. [2018-06-25 08:29:26,769 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 08:29:26,769 INFO ]: Found error trace [2018-06-25 08:29:26,770 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 08:29:26,770 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 08:29:26,777 INFO ]: Analyzing trace with hash 2092586353, now seen corresponding path program 1 times [2018-06-25 08:29:26,779 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 08:29:26,779 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 08:29:26,815 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:29:26,815 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 08:29:26,815 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:29:26,912 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:29:27,160 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 08:29:27,163 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 08:29:27,163 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-25 08:29:27,165 INFO ]: Interpolant automaton has 4 states [2018-06-25 08:29:27,180 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-25 08:29:27,181 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-25 08:29:27,184 INFO ]: Start difference. First operand 145 states. Second operand 4 states. [2018-06-25 08:29:30,314 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 08:29:30,314 INFO ]: Finished difference Result 283 states and 549 transitions. [2018-06-25 08:29:30,315 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 08:29:30,315 INFO ]: Start accepts. Automaton has 4 states. Word has length 7 [2018-06-25 08:29:30,316 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 08:29:30,361 INFO ]: With dead ends: 283 [2018-06-25 08:29:30,361 INFO ]: Without dead ends: 269 [2018-06-25 08:29:30,363 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 08:29:30,382 INFO ]: Start minimizeSevpa. Operand 269 states. [2018-06-25 08:29:30,538 INFO ]: Finished minimizeSevpa. Reduced states from 269 to 269. [2018-06-25 08:29:30,539 INFO ]: Start removeUnreachable. Operand 269 states. [2018-06-25 08:29:30,569 INFO ]: Finished removeUnreachable. Reduced from 269 states to 269 states and 525 transitions. [2018-06-25 08:29:30,570 INFO ]: Start accepts. Automaton has 269 states and 525 transitions. Word has length 7 [2018-06-25 08:29:30,571 INFO ]: Finished accepts. word is rejected. [2018-06-25 08:29:30,571 INFO ]: Abstraction has 269 states and 525 transitions. [2018-06-25 08:29:30,572 INFO ]: Interpolant automaton has 4 states. [2018-06-25 08:29:30,572 INFO ]: Start isEmpty. Operand 269 states and 525 transitions. [2018-06-25 08:29:30,583 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 08:29:30,583 INFO ]: Found error trace [2018-06-25 08:29:30,583 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 08:29:30,583 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 08:29:30,583 INFO ]: Analyzing trace with hash 777081689, now seen corresponding path program 1 times [2018-06-25 08:29:30,583 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 08:29:30,583 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 08:29:30,584 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:29:30,584 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 08:29:30,584 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:29:30,590 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:29:30,774 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 08:29:30,774 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 08:29:30,774 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-25 08:29:30,775 INFO ]: Interpolant automaton has 4 states [2018-06-25 08:29:30,775 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-25 08:29:30,775 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-25 08:29:30,776 INFO ]: Start difference. First operand 269 states and 525 transitions. Second operand 4 states. [2018-06-25 08:29:32,141 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 08:29:32,141 INFO ]: Finished difference Result 402 states and 786 transitions. [2018-06-25 08:29:32,142 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 08:29:32,142 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-25 08:29:32,142 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 08:29:32,169 INFO ]: With dead ends: 402 [2018-06-25 08:29:32,169 INFO ]: Without dead ends: 402 [2018-06-25 08:29:32,170 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 08:29:32,170 INFO ]: Start minimizeSevpa. Operand 402 states. [2018-06-25 08:29:32,236 INFO ]: Finished minimizeSevpa. Reduced states from 402 to 402. [2018-06-25 08:29:32,236 INFO ]: Start removeUnreachable. Operand 402 states. [2018-06-25 08:29:32,253 INFO ]: Finished removeUnreachable. Reduced from 402 states to 402 states and 786 transitions. [2018-06-25 08:29:32,253 INFO ]: Start accepts. Automaton has 402 states and 786 transitions. Word has length 9 [2018-06-25 08:29:32,253 INFO ]: Finished accepts. word is rejected. [2018-06-25 08:29:32,253 INFO ]: Abstraction has 402 states and 786 transitions. [2018-06-25 08:29:32,253 INFO ]: Interpolant automaton has 4 states. [2018-06-25 08:29:32,253 INFO ]: Start isEmpty. Operand 402 states and 786 transitions. [2018-06-25 08:29:32,273 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-25 08:29:32,274 INFO ]: Found error trace [2018-06-25 08:29:32,274 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 08:29:32,274 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 08:29:32,274 INFO ]: Analyzing trace with hash -257177526, now seen corresponding path program 1 times [2018-06-25 08:29:32,274 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 08:29:32,274 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 08:29:32,275 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:29:32,275 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 08:29:32,275 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:29:32,326 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:29:32,576 INFO ]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-25 08:29:32,576 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 08:29:32,576 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-25 08:29:32,576 INFO ]: Interpolant automaton has 7 states [2018-06-25 08:29:32,576 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 08:29:32,576 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-25 08:29:32,577 INFO ]: Start difference. First operand 402 states and 786 transitions. Second operand 7 states. [2018-06-25 08:29:36,146 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-25 08:29:40,368 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 08:29:40,368 INFO ]: Finished difference Result 1646 states and 7928 transitions. [2018-06-25 08:29:40,369 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-25 08:29:40,369 INFO ]: Start accepts. Automaton has 7 states. Word has length 17 [2018-06-25 08:29:40,369 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 08:29:40,923 INFO ]: With dead ends: 1646 [2018-06-25 08:29:40,923 INFO ]: Without dead ends: 1646 [2018-06-25 08:29:40,923 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=72, Invalid=200, Unknown=0, NotChecked=0, Total=272 [2018-06-25 08:29:40,924 INFO ]: Start minimizeSevpa. Operand 1646 states. [2018-06-25 08:29:41,636 INFO ]: Finished minimizeSevpa. Reduced states from 1646 to 814. [2018-06-25 08:29:41,636 INFO ]: Start removeUnreachable. Operand 814 states. [2018-06-25 08:29:41,682 INFO ]: Finished removeUnreachable. Reduced from 814 states to 814 states and 1807 transitions. [2018-06-25 08:29:41,682 INFO ]: Start accepts. Automaton has 814 states and 1807 transitions. Word has length 17 [2018-06-25 08:29:41,683 INFO ]: Finished accepts. word is rejected. [2018-06-25 08:29:41,683 INFO ]: Abstraction has 814 states and 1807 transitions. [2018-06-25 08:29:41,683 INFO ]: Interpolant automaton has 7 states. [2018-06-25 08:29:41,683 INFO ]: Start isEmpty. Operand 814 states and 1807 transitions. [2018-06-25 08:29:41,734 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-25 08:29:41,734 INFO ]: Found error trace [2018-06-25 08:29:41,734 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 08:29:41,735 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 08:29:41,736 INFO ]: Analyzing trace with hash -254198426, now seen corresponding path program 1 times [2018-06-25 08:29:41,736 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 08:29:41,736 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 08:29:41,736 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:29:41,736 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 08:29:41,736 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:29:41,791 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:29:42,361 INFO ]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-25 08:29:42,361 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 08:29:42,361 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-25 08:29:42,371 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 08:29:42,436 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:29:42,446 INFO ]: Computing forward predicates... [2018-06-25 08:29:42,656 INFO ]: Checked inductivity of 5 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-25 08:29:42,682 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 08:29:42,682 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-25 08:29:42,682 INFO ]: Interpolant automaton has 12 states [2018-06-25 08:29:42,682 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-25 08:29:42,682 INFO ]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-06-25 08:29:42,683 INFO ]: Start difference. First operand 814 states and 1807 transitions. Second operand 12 states. Received shutdown request... [2018-06-25 08:30:27,717 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-06-25 08:30:27,717 WARN ]: Verification canceled [2018-06-25 08:30:27,723 WARN ]: Timeout [2018-06-25 08:30:27,723 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 08:30:27 BoogieIcfgContainer [2018-06-25 08:30:27,723 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 08:30:27,724 INFO ]: Toolchain (without parser) took 62810.46 ms. Allocated memory was 305.1 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 244.4 MB in the beginning and 1.1 GB in the end (delta: -830.0 MB). Peak memory consumption was 541.6 MB. Max. memory is 3.6 GB. [2018-06-25 08:30:27,725 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 305.1 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 08:30:27,726 INFO ]: ChcToBoogie took 116.11 ms. Allocated memory is still 305.1 MB. Free memory was 244.4 MB in the beginning and 239.5 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. [2018-06-25 08:30:27,726 INFO ]: Boogie Preprocessor took 77.75 ms. Allocated memory is still 305.1 MB. Free memory was 239.5 MB in the beginning and 237.4 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 3.6 GB. [2018-06-25 08:30:27,727 INFO ]: RCFGBuilder took 1518.44 ms. Allocated memory was 305.1 MB in the beginning and 323.0 MB in the end (delta: 17.8 MB). Free memory was 237.4 MB in the beginning and 273.8 MB in the end (delta: -36.4 MB). Peak memory consumption was 59.4 MB. Max. memory is 3.6 GB. [2018-06-25 08:30:27,727 INFO ]: TraceAbstraction took 61088.07 ms. Allocated memory was 323.0 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 273.8 MB in the beginning and 1.1 GB in the end (delta: -800.6 MB). Peak memory consumption was 553.1 MB. Max. memory is 3.6 GB. [2018-06-25 08:30:27,741 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 305.1 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 116.11 ms. Allocated memory is still 305.1 MB. Free memory was 244.4 MB in the beginning and 239.5 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 77.75 ms. Allocated memory is still 305.1 MB. Free memory was 239.5 MB in the beginning and 237.4 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 1518.44 ms. Allocated memory was 305.1 MB in the beginning and 323.0 MB in the end (delta: 17.8 MB). Free memory was 237.4 MB in the beginning and 273.8 MB in the end (delta: -36.4 MB). Peak memory consumption was 59.4 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61088.07 ms. Allocated memory was 323.0 MB in the beginning and 1.7 GB in the end (delta: 1.4 GB). Free memory was 273.8 MB in the beginning and 1.1 GB in the end (delta: -800.6 MB). Peak memory consumption was 553.1 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 (814states) and interpolant automaton (currently 53 states, 12 states before enhancement), while ReachableStatesComputation was computing reachable states (6522 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 145 locations, 1 error locations. TIMEOUT Result, 61.0s OverallTime, 4 OverallIterations, 2 TraceHistogramMax, 57.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 8831 SDtfs, 1314 SDslu, 35369 SDs, 0 SdLazy, 42857 SolverSat, 7632 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 47.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 97 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 966 ImplicationChecksByTransitivity, 2.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=814occurred in iteration=3, 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: 1.0s AutomataMinimizationTime, 3 MinimizatonAttempts, 832 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 1.4s InterpolantComputationTime, 67 NumberOfCodeBlocks, 67 NumberOfCodeBlocksAsserted, 5 NumberOfCheckSat, 62 ConstructedInterpolants, 0 QuantifiedInterpolants, 2036 SizeOfPredicates, 7 NumberOfNonLiveVariables, 440 ConjunctsInSsa, 11 ConjunctsInUnsatCore, 5 InterpolantComputations, 3 PerfectInterpolantSequences, 12/14 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.31.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_08-30-27-758.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/graham-scan-full.31.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_08-30-27-758.csv Completed graceful shutdown