java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.9.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 04:54:49,457 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 04:54:49,460 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 04:54:49,473 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 04:54:49,473 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 04:54:49,474 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 04:54:49,478 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 04:54:49,481 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 04:54:49,482 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 04:54:49,484 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 04:54:49,485 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 04:54:49,485 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 04:54:49,486 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 04:54:49,490 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 04:54:49,491 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 04:54:49,492 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 04:54:49,504 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 04:54:49,507 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 04:54:49,508 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 04:54:49,509 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 04:54:49,513 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 04:54:49,515 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 04:54:49,516 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 04:54:49,516 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 04:54:49,518 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 04:54:49,519 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 04:54:49,520 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 04:54:49,521 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 04:54:49,527 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 04:54:49,528 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 04:54:49,528 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 04:54:49,529 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 04:54:49,529 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 04:54:49,530 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 04:54:49,532 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 04:54:49,532 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 04:54:49,553 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 04:54:49,553 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 04:54:49,553 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 04:54:49,554 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 04:54:49,555 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 04:54:49,555 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 04:54:49,555 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 04:54:49,555 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 04:54:49,556 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:54:49,556 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 04:54:49,556 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 04:54:49,556 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 04:54:49,556 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 04:54:49,559 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 04:54:49,559 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 04:54:49,560 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 04:54:49,560 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 04:54:49,561 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 04:54:49,562 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 04:54:49,614 INFO ]: Repository-Root is: /tmp [2018-06-22 04:54:49,630 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 04:54:49,636 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 04:54:49,638 INFO ]: Initializing SmtParser... [2018-06-22 04:54:49,638 INFO ]: SmtParser initialized [2018-06-22 04:54:49,639 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.9.smt2 [2018-06-22 04:54:49,640 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 04:54:49,733 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.9.smt2 unknown [2018-06-22 04:54:53,905 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.9.smt2 [2018-06-22 04:54:53,910 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 04:54:53,917 INFO ]: Walking toolchain with 4 elements. [2018-06-22 04:54:53,918 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 04:54:53,918 INFO ]: Initializing ChcToBoogie... [2018-06-22 04:54:53,918 INFO ]: ChcToBoogie initialized [2018-06-22 04:54:53,922 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:54:53" (1/1) ... [2018-06-22 04:54:54,053 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54 Unit [2018-06-22 04:54:54,053 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 04:54:54,054 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 04:54:54,054 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 04:54:54,054 INFO ]: Boogie Preprocessor initialized [2018-06-22 04:54:54,075 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54" (1/1) ... [2018-06-22 04:54:54,075 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54" (1/1) ... [2018-06-22 04:54:54,139 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54" (1/1) ... [2018-06-22 04:54:54,140 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54" (1/1) ... [2018-06-22 04:54:54,207 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54" (1/1) ... [2018-06-22 04:54:54,209 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54" (1/1) ... [2018-06-22 04:54:54,232 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54" (1/1) ... [2018-06-22 04:54:54,256 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 04:54:54,257 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 04:54:54,257 INFO ]: Initializing RCFGBuilder... [2018-06-22 04:54:54,257 INFO ]: RCFGBuilder initialized [2018-06-22 04:54:54,258 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54" (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-22 04:54:54,342 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 04:54:54,342 INFO ]: Found specification of procedure gotoProc [2018-06-22 04:54:54,342 INFO ]: Found implementation of procedure gotoProc [2018-06-22 04:54:54,342 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 04:54:54,342 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 04:54:54,342 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 04:54:57,697 INFO ]: Using library mode [2018-06-22 04:54:57,698 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:54:57 BoogieIcfgContainer [2018-06-22 04:54:57,698 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 04:54:57,699 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 04:54:57,699 INFO ]: Initializing TraceAbstraction... [2018-06-22 04:54:57,702 INFO ]: TraceAbstraction initialized [2018-06-22 04:54:57,702 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:54:53" (1/3) ... [2018-06-22 04:54:57,703 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6af33228 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:54:57, skipping insertion in model container [2018-06-22 04:54:57,703 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:54:54" (2/3) ... [2018-06-22 04:54:57,703 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6af33228 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:54:57, skipping insertion in model container [2018-06-22 04:54:57,703 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:54:57" (3/3) ... [2018-06-22 04:54:57,705 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 04:54:57,714 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 04:54:57,721 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 04:54:57,782 INFO ]: Using default assertion order modulation [2018-06-22 04:54:57,782 INFO ]: Interprodecural is true [2018-06-22 04:54:57,782 INFO ]: Hoare is false [2018-06-22 04:54:57,782 INFO ]: Compute interpolants for FPandBP [2018-06-22 04:54:57,783 INFO ]: Backedges is TWOTRACK [2018-06-22 04:54:57,783 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 04:54:57,783 INFO ]: Difference is false [2018-06-22 04:54:57,783 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 04:54:57,785 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 04:54:57,805 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 04:54:57,819 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 04:54:57,819 INFO ]: Found error trace [2018-06-22 04:54:57,820 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:54:57,820 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:54:57,825 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-22 04:54:57,827 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:54:57,827 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:54:57,859 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:54:57,859 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:54:57,859 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:54:58,138 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:54:58,329 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:54:58,332 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 04:54:58,332 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 04:54:58,334 INFO ]: Interpolant automaton has 3 states [2018-06-22 04:54:58,344 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 04:54:58,344 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:54:58,346 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 04:54:58,617 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:54:58,617 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 04:54:58,618 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 04:54:58,619 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 04:54:58,620 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:54:58,628 INFO ]: With dead ends: 9 [2018-06-22 04:54:58,628 INFO ]: Without dead ends: 9 [2018-06-22 04:54:58,629 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:54:58,643 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 04:54:58,657 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 04:54:58,658 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 04:54:58,658 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 04:54:58,659 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 04:54:58,660 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:54:58,660 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 04:54:58,660 INFO ]: Interpolant automaton has 3 states. [2018-06-22 04:54:58,660 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 04:54:58,660 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 04:54:58,660 INFO ]: Found error trace [2018-06-22 04:54:58,660 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:54:58,660 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:54:58,660 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-22 04:54:58,660 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:54:58,660 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:54:58,661 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:54:58,661 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:54:58,661 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:54:59,307 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:55:00,253 WARN ]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 04:55:00,331 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:55:00,331 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:55:00,331 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-22 04:55:00,342 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-22 04:55:01,300 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:55:01,361 INFO ]: Computing forward predicates... [2018-06-22 04:55:01,675 WARN ]: Spent 140.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 04:55:03,504 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:55:03,608 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:55:03,608 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-22 04:55:03,609 INFO ]: Interpolant automaton has 6 states [2018-06-22 04:55:03,609 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 04:55:03,609 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 04:55:03,609 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-22 04:55:04,058 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:55:04,058 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 04:55:04,059 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 04:55:04,059 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-22 04:55:04,059 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:55:04,059 INFO ]: With dead ends: 11 [2018-06-22 04:55:04,059 INFO ]: Without dead ends: 11 [2018-06-22 04:55:04,060 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2018-06-22 04:55:04,060 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 04:55:04,061 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 04:55:04,061 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 04:55:04,061 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 04:55:04,062 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-22 04:55:04,062 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:55:04,062 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 04:55:04,062 INFO ]: Interpolant automaton has 6 states. [2018-06-22 04:55:04,062 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 04:55:04,062 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 04:55:04,062 INFO ]: Found error trace [2018-06-22 04:55:04,062 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:55:04,062 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:55:04,062 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 2 times [2018-06-22 04:55:04,062 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:55:04,063 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:55:04,063 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:55:04,063 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:55:04,063 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:55:04,990 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:55:06,619 WARN ]: Spent 146.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 04:55:06,778 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:55:06,778 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:55:06,778 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:55:06,787 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 04:55:07,967 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 04:55:07,967 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:55:08,071 INFO ]: Computing forward predicates... [2018-06-22 04:55:19,948 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 19 [2018-06-22 04:55:19,978 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:55:20,028 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:55:20,028 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 04:55:20,029 INFO ]: Interpolant automaton has 9 states [2018-06-22 04:55:20,029 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 04:55:20,029 INFO ]: CoverageRelationStatistics Valid=29, Invalid=43, Unknown=0, NotChecked=0, Total=72 [2018-06-22 04:55:20,029 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 9 states. [2018-06-22 04:55:20,492 WARN ]: Spent 138.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 18 [2018-06-22 04:55:20,644 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:55:20,644 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 04:55:20,644 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 04:55:20,644 INFO ]: Start accepts. Automaton has 9 states. Word has length 10 [2018-06-22 04:55:20,645 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:55:20,645 INFO ]: With dead ends: 12 [2018-06-22 04:55:20,645 INFO ]: Without dead ends: 12 [2018-06-22 04:55:20,645 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=45, Invalid=65, Unknown=0, NotChecked=0, Total=110 [2018-06-22 04:55:20,645 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 04:55:20,647 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 04:55:20,647 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 04:55:20,647 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 04:55:20,647 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-22 04:55:20,647 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:55:20,647 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 04:55:20,647 INFO ]: Interpolant automaton has 9 states. [2018-06-22 04:55:20,647 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 04:55:20,648 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 04:55:20,648 INFO ]: Found error trace [2018-06-22 04:55:20,648 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:55:20,648 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:55:20,648 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-22 04:55:20,648 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:55:20,648 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:55:20,649 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:55:20,649 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:55:20,649 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:55:21,899 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:55:23,567 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:55:23,567 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:55:23,567 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:55:23,574 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 04:55:25,211 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 04:55:25,212 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:55:25,330 INFO ]: Computing forward predicates... [2018-06-22 04:55:37,725 WARN ]: Simplifying disjunction of 7776 conjuctions. This might take some time... [2018-06-22 04:55:44,225 INFO ]: Simplified to disjunction of 7776 conjuctions. [2018-06-22 04:55:44,302 WARN ]: Simplifying disjunction of 7776 conjuctions. This might take some time... [2018-06-22 04:55:48,057 INFO ]: Simplified to disjunction of 7776 conjuctions. [2018-06-22 04:55:48,103 WARN ]: Simplifying disjunction of 7776 conjuctions. This might take some time... Received shutdown request... [2018-06-22 04:55:49,543 INFO ]: Timeout while computing interpolants [2018-06-22 04:55:49,743 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:55:49,744 WARN ]: Verification canceled [2018-06-22 04:55:49,747 WARN ]: Timeout [2018-06-22 04:55:49,747 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:55:49 BoogieIcfgContainer [2018-06-22 04:55:49,747 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 04:55:49,748 INFO ]: Toolchain (without parser) took 55836.95 ms. Allocated memory was 610.3 MB in the beginning and 1.6 GB in the end (delta: 1.0 GB). Free memory was 189.2 MB in the beginning and 1.4 GB in the end (delta: -1.2 GB). Peak memory consumption was 1.0 GB. Max. memory is 3.6 GB. [2018-06-22 04:55:49,748 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 305.7 MB. Free memory is still 271.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 04:55:49,748 INFO ]: ChcToBoogie took 135.98 ms. Allocated memory is still 610.3 MB. Free memory was 189.2 MB in the beginning and 181.9 MB in the end (delta: 7.3 MB). Peak memory consumption was 7.3 MB. Max. memory is 3.6 GB. [2018-06-22 04:55:49,748 INFO ]: Boogie Preprocessor took 202.23 ms. Allocated memory is still 610.3 MB. Free memory was 181.9 MB in the beginning and 167.2 MB in the end (delta: 14.7 MB). Peak memory consumption was 14.7 MB. Max. memory is 3.6 GB. [2018-06-22 04:55:49,749 INFO ]: RCFGBuilder took 3440.85 ms. Allocated memory was 610.3 MB in the beginning and 895.5 MB in the end (delta: 285.2 MB). Free memory was 167.2 MB in the beginning and 459.7 MB in the end (delta: -292.4 MB). Peak memory consumption was 325.9 MB. Max. memory is 3.6 GB. [2018-06-22 04:55:49,749 INFO ]: TraceAbstraction took 52048.00 ms. Allocated memory was 895.5 MB in the beginning and 1.6 GB in the end (delta: 748.2 MB). Free memory was 459.7 MB in the beginning and 1.4 GB in the end (delta: -957.3 MB). Peak memory consumption was 1.0 GB. Max. memory is 3.6 GB. [2018-06-22 04:55:49,751 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.7 MB. Free memory is still 271.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 135.98 ms. Allocated memory is still 610.3 MB. Free memory was 189.2 MB in the beginning and 181.9 MB in the end (delta: 7.3 MB). Peak memory consumption was 7.3 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 202.23 ms. Allocated memory is still 610.3 MB. Free memory was 181.9 MB in the beginning and 167.2 MB in the end (delta: 14.7 MB). Peak memory consumption was 14.7 MB. Max. memory is 3.6 GB. * RCFGBuilder took 3440.85 ms. Allocated memory was 610.3 MB in the beginning and 895.5 MB in the end (delta: 285.2 MB). Free memory was 167.2 MB in the beginning and 459.7 MB in the end (delta: -292.4 MB). Peak memory consumption was 325.9 MB. Max. memory is 3.6 GB. * TraceAbstraction took 52048.00 ms. Allocated memory was 895.5 MB in the beginning and 1.6 GB in the end (delta: 748.2 MB). Free memory was 459.7 MB in the beginning and 1.4 GB in the end (delta: -957.3 MB). Peak memory consumption was 1.0 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 analyzing trace of length 12 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was XNF transformer was simplifying 7776 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 51.9s OverallTime, 4 OverallIterations, 4 TraceHistogramMax, 1.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 21 SDtfs, 1 SDslu, 39 SDs, 0 SdLazy, 19 SolverSat, 7 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 32 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 1.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=12occurred 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: 0.0s AutomataMinimizationTime, 3 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.9s SsaConstructionTime, 2.9s SatisfiabilityAnalysisTime, 17.2s InterpolantComputationTime, 43 NumberOfCodeBlocks, 43 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 38 ConstructedInterpolants, 0 QuantifiedInterpolants, 1434 SizeOfPredicates, 6 NumberOfNonLiveVariables, 7218 ConjunctsInSsa, 50 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 0/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/token_ring.9.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_04-55-49-760.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/token_ring.9.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_04-55-49-760.csv Completed graceful shutdown