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/ch-triangle-location-nr.3.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 08:18:16,464 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 08:18:16,467 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 08:18:16,482 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 08:18:16,482 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 08:18:16,483 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 08:18:16,486 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 08:18:16,488 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 08:18:16,490 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 08:18:16,491 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 08:18:16,493 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 08:18:16,493 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 08:18:16,494 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 08:18:16,495 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 08:18:16,495 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 08:18:16,498 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 08:18:16,500 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 08:18:16,502 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 08:18:16,511 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 08:18:16,512 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 08:18:16,513 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 08:18:16,515 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 08:18:16,515 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 08:18:16,515 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 08:18:16,520 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 08:18:16,521 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 08:18:16,522 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 08:18:16,522 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 08:18:16,523 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 08:18:16,523 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 08:18:16,526 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 08:18:16,527 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 08:18:16,527 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 08:18:16,527 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 08:18:16,528 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 08:18:16,528 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:18:16,550 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 08:18:16,550 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 08:18:16,551 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 08:18:16,551 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 08:18:16,553 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 08:18:16,553 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 08:18:16,553 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 08:18:16,553 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 08:18:16,553 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 08:18:16,554 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 08:18:16,554 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 08:18:16,554 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 08:18:16,554 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 08:18:16,554 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 08:18:16,555 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 08:18:16,555 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 08:18:16,555 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 08:18:16,555 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 08:18:16,555 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 08:18:16,555 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 08:18:16,556 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 08:18:16,560 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 08:18:16,560 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 08:18:16,597 INFO ]: Repository-Root is: /tmp [2018-06-25 08:18:16,612 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 08:18:16,616 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 08:18:16,617 INFO ]: Initializing SmtParser... [2018-06-25 08:18:16,617 INFO ]: SmtParser initialized [2018-06-25 08:18:16,618 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/Consistency/ch-triangle-location-nr.3.smt2 [2018-06-25 08:18:16,619 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:18:16,684 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/ch-triangle-location-nr.3.smt2 unknown [2018-06-25 08:18:17,051 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/Consistency/ch-triangle-location-nr.3.smt2 [2018-06-25 08:18:17,055 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 08:18:17,069 INFO ]: Walking toolchain with 4 elements. [2018-06-25 08:18:17,069 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 08:18:17,069 INFO ]: Initializing ChcToBoogie... [2018-06-25 08:18:17,069 INFO ]: ChcToBoogie initialized [2018-06-25 08:18:17,072 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 08:18:17" (1/1) ... [2018-06-25 08:18:17,158 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17 Unit [2018-06-25 08:18:17,158 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 08:18:17,159 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 08:18:17,159 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 08:18:17,159 INFO ]: Boogie Preprocessor initialized [2018-06-25 08:18:17,181 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17" (1/1) ... [2018-06-25 08:18:17,182 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17" (1/1) ... [2018-06-25 08:18:17,201 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17" (1/1) ... [2018-06-25 08:18:17,201 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17" (1/1) ... [2018-06-25 08:18:17,226 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17" (1/1) ... [2018-06-25 08:18:17,231 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17" (1/1) ... [2018-06-25 08:18:17,233 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17" (1/1) ... [2018-06-25 08:18:17,237 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 08:18:17,238 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 08:18:17,238 INFO ]: Initializing RCFGBuilder... [2018-06-25 08:18:17,238 INFO ]: RCFGBuilder initialized [2018-06-25 08:18:17,238 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17" (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-25 08:18:17,251 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 08:18:17,251 INFO ]: Found specification of procedure gotoProc [2018-06-25 08:18:17,251 INFO ]: Found implementation of procedure gotoProc [2018-06-25 08:18:17,251 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 08:18:17,251 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 08:18:17,251 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-25 08:18:18,738 INFO ]: Using library mode [2018-06-25 08:18:18,739 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 08:18:18 BoogieIcfgContainer [2018-06-25 08:18:18,739 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 08:18:18,740 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 08:18:18,740 INFO ]: Initializing TraceAbstraction... [2018-06-25 08:18:18,745 INFO ]: TraceAbstraction initialized [2018-06-25 08:18:18,746 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 08:18:17" (1/3) ... [2018-06-25 08:18:18,746 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@510585a9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 08:18:18, skipping insertion in model container [2018-06-25 08:18:18,746 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 08:18:17" (2/3) ... [2018-06-25 08:18:18,747 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@510585a9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 08:18:18, skipping insertion in model container [2018-06-25 08:18:18,747 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 08:18:18" (3/3) ... [2018-06-25 08:18:18,749 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 08:18:18,759 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 08:18:18,768 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 08:18:18,805 INFO ]: Using default assertion order modulation [2018-06-25 08:18:18,806 INFO ]: Interprodecural is true [2018-06-25 08:18:18,806 INFO ]: Hoare is false [2018-06-25 08:18:18,806 INFO ]: Compute interpolants for FPandBP [2018-06-25 08:18:18,806 INFO ]: Backedges is TWOTRACK [2018-06-25 08:18:18,806 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 08:18:18,806 INFO ]: Difference is false [2018-06-25 08:18:18,806 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 08:18:18,806 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 08:18:18,825 INFO ]: Start isEmpty. Operand 145 states. [2018-06-25 08:18:18,843 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 08:18:18,848 INFO ]: Found error trace [2018-06-25 08:18:18,848 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 08:18:18,849 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 08:18:18,852 INFO ]: Analyzing trace with hash -929610780, now seen corresponding path program 1 times [2018-06-25 08:18:18,854 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 08:18:18,854 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 08:18:18,886 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:18:18,886 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 08:18:18,886 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:18:18,936 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:18:19,079 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:18:19,081 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 08:18:19,081 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-25 08:18:19,082 INFO ]: Interpolant automaton has 4 states [2018-06-25 08:18:19,092 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-25 08:18:19,093 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-25 08:18:19,094 INFO ]: Start difference. First operand 145 states. Second operand 4 states. [2018-06-25 08:18:21,657 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 08:18:21,658 INFO ]: Finished difference Result 283 states and 557 transitions. [2018-06-25 08:18:21,688 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 08:18:21,690 INFO ]: Start accepts. Automaton has 4 states. Word has length 8 [2018-06-25 08:18:21,690 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 08:18:21,730 INFO ]: With dead ends: 283 [2018-06-25 08:18:21,730 INFO ]: Without dead ends: 277 [2018-06-25 08:18:21,732 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-25 08:18:21,751 INFO ]: Start minimizeSevpa. Operand 277 states. [2018-06-25 08:18:21,864 INFO ]: Finished minimizeSevpa. Reduced states from 277 to 277. [2018-06-25 08:18:21,866 INFO ]: Start removeUnreachable. Operand 277 states. [2018-06-25 08:18:21,891 INFO ]: Finished removeUnreachable. Reduced from 277 states to 277 states and 545 transitions. [2018-06-25 08:18:21,893 INFO ]: Start accepts. Automaton has 277 states and 545 transitions. Word has length 8 [2018-06-25 08:18:21,894 INFO ]: Finished accepts. word is rejected. [2018-06-25 08:18:21,894 INFO ]: Abstraction has 277 states and 545 transitions. [2018-06-25 08:18:21,894 INFO ]: Interpolant automaton has 4 states. [2018-06-25 08:18:21,894 INFO ]: Start isEmpty. Operand 277 states and 545 transitions. [2018-06-25 08:18:21,898 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 08:18:21,898 INFO ]: Found error trace [2018-06-25 08:18:21,898 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 08:18:21,898 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 08:18:21,898 INFO ]: Analyzing trace with hash -1066649380, now seen corresponding path program 1 times [2018-06-25 08:18:21,898 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 08:18:21,898 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 08:18:21,899 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:18:21,899 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 08:18:21,899 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:18:21,907 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:18:22,045 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:18:22,045 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 08:18:22,045 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-25 08:18:22,046 INFO ]: Interpolant automaton has 4 states [2018-06-25 08:18:22,047 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-25 08:18:22,047 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-25 08:18:22,047 INFO ]: Start difference. First operand 277 states and 545 transitions. Second operand 4 states. [2018-06-25 08:18:23,911 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 08:18:23,912 INFO ]: Finished difference Result 414 states and 816 transitions. [2018-06-25 08:18:23,912 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 08:18:23,912 INFO ]: Start accepts. Automaton has 4 states. Word has length 8 [2018-06-25 08:18:23,912 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 08:18:23,934 INFO ]: With dead ends: 414 [2018-06-25 08:18:23,934 INFO ]: Without dead ends: 414 [2018-06-25 08:18:23,935 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:18:23,935 INFO ]: Start minimizeSevpa. Operand 414 states. [2018-06-25 08:18:24,015 INFO ]: Finished minimizeSevpa. Reduced states from 414 to 414. [2018-06-25 08:18:24,015 INFO ]: Start removeUnreachable. Operand 414 states. [2018-06-25 08:18:24,032 INFO ]: Finished removeUnreachable. Reduced from 414 states to 414 states and 816 transitions. [2018-06-25 08:18:24,032 INFO ]: Start accepts. Automaton has 414 states and 816 transitions. Word has length 8 [2018-06-25 08:18:24,032 INFO ]: Finished accepts. word is rejected. [2018-06-25 08:18:24,032 INFO ]: Abstraction has 414 states and 816 transitions. [2018-06-25 08:18:24,032 INFO ]: Interpolant automaton has 4 states. [2018-06-25 08:18:24,032 INFO ]: Start isEmpty. Operand 414 states and 816 transitions. [2018-06-25 08:18:24,056 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-25 08:18:24,056 INFO ]: Found error trace [2018-06-25 08:18:24,056 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 08:18:24,056 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 08:18:24,056 INFO ]: Analyzing trace with hash 998931203, now seen corresponding path program 1 times [2018-06-25 08:18:24,056 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 08:18:24,056 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 08:18:24,057 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:18:24,057 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 08:18:24,057 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:18:24,086 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:18:24,310 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:18:24,310 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 08:18:24,310 INFO ]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-06-25 08:18:24,310 INFO ]: Interpolant automaton has 7 states [2018-06-25 08:18:24,310 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 08:18:24,310 INFO ]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-06-25 08:18:24,311 INFO ]: Start difference. First operand 414 states and 816 transitions. Second operand 7 states. [2018-06-25 08:18:32,809 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 08:18:32,810 INFO ]: Finished difference Result 1394 states and 8497 transitions. [2018-06-25 08:18:32,810 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-25 08:18:32,810 INFO ]: Start accepts. Automaton has 7 states. Word has length 19 [2018-06-25 08:18:32,810 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 08:18:33,282 INFO ]: With dead ends: 1394 [2018-06-25 08:18:33,282 INFO ]: Without dead ends: 1394 [2018-06-25 08:18:33,282 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2018-06-25 08:18:33,283 INFO ]: Start minimizeSevpa. Operand 1394 states. [2018-06-25 08:18:34,031 INFO ]: Finished minimizeSevpa. Reduced states from 1394 to 919. [2018-06-25 08:18:34,031 INFO ]: Start removeUnreachable. Operand 919 states. [2018-06-25 08:18:34,117 INFO ]: Finished removeUnreachable. Reduced from 919 states to 919 states and 2407 transitions. [2018-06-25 08:18:34,117 INFO ]: Start accepts. Automaton has 919 states and 2407 transitions. Word has length 19 [2018-06-25 08:18:34,117 INFO ]: Finished accepts. word is rejected. [2018-06-25 08:18:34,117 INFO ]: Abstraction has 919 states and 2407 transitions. [2018-06-25 08:18:34,117 INFO ]: Interpolant automaton has 7 states. [2018-06-25 08:18:34,117 INFO ]: Start isEmpty. Operand 919 states and 2407 transitions. [2018-06-25 08:18:34,146 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-25 08:18:34,146 INFO ]: Found error trace [2018-06-25 08:18:34,146 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 08:18:34,146 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 08:18:34,146 INFO ]: Analyzing trace with hash -927469170, now seen corresponding path program 1 times [2018-06-25 08:18:34,146 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 08:18:34,146 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 08:18:34,147 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:18:34,147 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 08:18:34,147 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 08:18:34,187 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:18:34,818 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:18:34,818 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 08:18:34,819 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) [2018-06-25 08:18:34,838 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 08:18:34,895 INFO ]: Conjunction of SSA is unsat [2018-06-25 08:18:34,908 INFO ]: Computing forward predicates... [2018-06-25 08:18:35,341 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:18:35,364 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 08:18:35,364 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-25 08:18:35,364 INFO ]: Interpolant automaton has 12 states [2018-06-25 08:18:35,364 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-25 08:18:35,364 INFO ]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-06-25 08:18:35,364 INFO ]: Start difference. First operand 919 states and 2407 transitions. Second operand 12 states. [2018-06-25 08:18:35,822 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 20 [2018-06-25 08:18:36,909 WARN ]: Spent 414.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 19 Received shutdown request... [2018-06-25 08:19:19,049 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2018-06-25 08:19:19,049 WARN ]: Verification canceled [2018-06-25 08:19:19,054 WARN ]: Timeout [2018-06-25 08:19:19,054 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 08:19:19 BoogieIcfgContainer [2018-06-25 08:19:19,054 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 08:19:19,055 INFO ]: Toolchain (without parser) took 61999.75 ms. Allocated memory was 304.1 MB in the beginning and 1.3 GB in the end (delta: 1.0 GB). Free memory was 248.7 MB in the beginning and 332.0 MB in the end (delta: -83.4 MB). Peak memory consumption was 954.7 MB. Max. memory is 3.6 GB. [2018-06-25 08:19:19,056 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 304.1 MB. Free memory is still 269.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 08:19:19,056 INFO ]: ChcToBoogie took 89.45 ms. Allocated memory is still 304.1 MB. Free memory was 248.7 MB in the beginning and 244.7 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-25 08:19:19,058 INFO ]: Boogie Preprocessor took 78.31 ms. Allocated memory is still 304.1 MB. Free memory was 244.7 MB in the beginning and 242.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 08:19:19,059 INFO ]: RCFGBuilder took 1501.45 ms. Allocated memory was 304.1 MB in the beginning and 324.0 MB in the end (delta: 19.9 MB). Free memory was 242.7 MB in the beginning and 290.1 MB in the end (delta: -47.4 MB). Peak memory consumption was 66.3 MB. Max. memory is 3.6 GB. [2018-06-25 08:19:19,059 INFO ]: TraceAbstraction took 60314.39 ms. Allocated memory was 324.0 MB in the beginning and 1.3 GB in the end (delta: 1.0 GB). Free memory was 288.6 MB in the beginning and 332.0 MB in the end (delta: -43.4 MB). Peak memory consumption was 974.7 MB. Max. memory is 3.6 GB. [2018-06-25 08:19:19,066 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 304.1 MB. Free memory is still 269.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 89.45 ms. Allocated memory is still 304.1 MB. Free memory was 248.7 MB in the beginning and 244.7 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 78.31 ms. Allocated memory is still 304.1 MB. Free memory was 244.7 MB in the beginning and 242.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 1501.45 ms. Allocated memory was 304.1 MB in the beginning and 324.0 MB in the end (delta: 19.9 MB). Free memory was 242.7 MB in the beginning and 290.1 MB in the end (delta: -47.4 MB). Peak memory consumption was 66.3 MB. Max. memory is 3.6 GB. * TraceAbstraction took 60314.39 ms. Allocated memory was 324.0 MB in the beginning and 1.3 GB in the end (delta: 1.0 GB). Free memory was 288.6 MB in the beginning and 332.0 MB in the end (delta: -43.4 MB). Peak memory consumption was 974.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 (919states) and interpolant automaton (currently 34 states, 12 states before enhancement), while ReachableStatesComputation was computing reachable states (4581 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 145 locations, 1 error locations. TIMEOUT Result, 60.2s OverallTime, 4 OverallIterations, 2 TraceHistogramMax, 57.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 3105 SDtfs, 1487 SDslu, 8194 SDs, 0 SdLazy, 43026 SolverSat, 12661 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 47.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 78 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 365 ImplicationChecksByTransitivity, 2.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=919occurred 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, 475 StatesRemovedByMinimization, 1 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.1s SatisfiabilityAnalysisTime, 1.5s InterpolantComputationTime, 73 NumberOfCodeBlocks, 73 NumberOfCodeBlocksAsserted, 5 NumberOfCheckSat, 68 ConstructedInterpolants, 0 QuantifiedInterpolants, 2722 SizeOfPredicates, 6 NumberOfNonLiveVariables, 198 ConjunctsInSsa, 10 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/ch-triangle-location-nr.3.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_08-19-19-079.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/ch-triangle-location-nr.3.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_08-19-19-079.csv Completed graceful shutdown