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.6.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 04:52:57,629 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 04:52:57,631 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 04:52:57,642 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 04:52:57,643 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 04:52:57,644 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 04:52:57,645 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 04:52:57,647 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 04:52:57,648 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 04:52:57,649 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 04:52:57,651 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 04:52:57,651 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 04:52:57,652 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 04:52:57,653 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 04:52:57,657 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 04:52:57,658 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 04:52:57,659 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 04:52:57,661 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 04:52:57,663 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 04:52:57,664 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 04:52:57,665 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 04:52:57,667 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 04:52:57,667 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 04:52:57,667 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 04:52:57,668 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 04:52:57,669 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 04:52:57,670 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 04:52:57,671 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 04:52:57,672 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 04:52:57,672 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 04:52:57,673 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 04:52:57,673 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 04:52:57,673 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 04:52:57,674 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 04:52:57,675 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 04:52:57,675 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:52:57,689 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 04:52:57,689 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 04:52:57,689 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 04:52:57,690 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 04:52:57,691 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 04:52:57,691 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 04:52:57,691 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 04:52:57,691 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 04:52:57,691 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:52:57,692 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 04:52:57,692 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 04:52:57,692 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 04:52:57,692 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 04:52:57,692 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 04:52:57,692 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 04:52:57,693 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 04:52:57,693 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 04:52:57,694 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 04:52:57,694 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 04:52:57,743 INFO ]: Repository-Root is: /tmp [2018-06-22 04:52:57,758 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 04:52:57,761 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 04:52:57,763 INFO ]: Initializing SmtParser... [2018-06-22 04:52:57,763 INFO ]: SmtParser initialized [2018-06-22 04:52:57,763 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.6.smt2 [2018-06-22 04:52:57,764 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:52:57,855 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.6.smt2 unknown [2018-06-22 04:52:59,939 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.6.smt2 [2018-06-22 04:52:59,945 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 04:52:59,952 INFO ]: Walking toolchain with 4 elements. [2018-06-22 04:52:59,953 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 04:52:59,953 INFO ]: Initializing ChcToBoogie... [2018-06-22 04:52:59,953 INFO ]: ChcToBoogie initialized [2018-06-22 04:52:59,957 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:52:59" (1/1) ... [2018-06-22 04:53:00,072 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00 Unit [2018-06-22 04:53:00,072 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 04:53:00,073 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 04:53:00,073 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 04:53:00,073 INFO ]: Boogie Preprocessor initialized [2018-06-22 04:53:00,094 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00" (1/1) ... [2018-06-22 04:53:00,094 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00" (1/1) ... [2018-06-22 04:53:00,133 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00" (1/1) ... [2018-06-22 04:53:00,133 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00" (1/1) ... [2018-06-22 04:53:00,184 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00" (1/1) ... [2018-06-22 04:53:00,192 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00" (1/1) ... [2018-06-22 04:53:00,207 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00" (1/1) ... [2018-06-22 04:53:00,222 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 04:53:00,222 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 04:53:00,223 INFO ]: Initializing RCFGBuilder... [2018-06-22 04:53:00,223 INFO ]: RCFGBuilder initialized [2018-06-22 04:53:00,223 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00" (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:53:00,257 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 04:53:00,257 INFO ]: Found specification of procedure gotoProc [2018-06-22 04:53:00,257 INFO ]: Found implementation of procedure gotoProc [2018-06-22 04:53:00,257 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 04:53:00,257 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 04:53:00,257 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 04:53:01,913 INFO ]: Using library mode [2018-06-22 04:53:01,913 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:53:01 BoogieIcfgContainer [2018-06-22 04:53:01,913 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 04:53:01,948 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 04:53:01,948 INFO ]: Initializing TraceAbstraction... [2018-06-22 04:53:01,954 INFO ]: TraceAbstraction initialized [2018-06-22 04:53:01,954 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:52:59" (1/3) ... [2018-06-22 04:53:01,955 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@511eb991 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:53:01, skipping insertion in model container [2018-06-22 04:53:01,955 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:53:00" (2/3) ... [2018-06-22 04:53:01,955 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@511eb991 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:53:01, skipping insertion in model container [2018-06-22 04:53:01,955 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:53:01" (3/3) ... [2018-06-22 04:53:01,957 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 04:53:01,966 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 04:53:01,975 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 04:53:02,018 INFO ]: Using default assertion order modulation [2018-06-22 04:53:02,018 INFO ]: Interprodecural is true [2018-06-22 04:53:02,018 INFO ]: Hoare is false [2018-06-22 04:53:02,018 INFO ]: Compute interpolants for FPandBP [2018-06-22 04:53:02,018 INFO ]: Backedges is TWOTRACK [2018-06-22 04:53:02,018 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 04:53:02,018 INFO ]: Difference is false [2018-06-22 04:53:02,018 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 04:53:02,018 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 04:53:02,030 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 04:53:02,039 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 04:53:02,040 INFO ]: Found error trace [2018-06-22 04:53:02,040 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:53:02,041 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:53:02,044 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-22 04:53:02,045 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:53:02,046 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:53:02,078 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:53:02,078 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:53:02,078 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:53:02,249 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:53:02,399 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:53:02,401 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 04:53:02,401 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 04:53:02,402 INFO ]: Interpolant automaton has 3 states [2018-06-22 04:53:02,412 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 04:53:02,413 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:53:02,415 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 04:53:02,597 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:53:02,597 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 04:53:02,598 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 04:53:02,600 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 04:53:02,600 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:53:02,612 INFO ]: With dead ends: 9 [2018-06-22 04:53:02,612 INFO ]: Without dead ends: 9 [2018-06-22 04:53:02,614 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:53:02,634 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 04:53:02,665 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 04:53:02,666 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 04:53:02,666 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 04:53:02,667 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 04:53:02,667 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:53:02,667 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 04:53:02,667 INFO ]: Interpolant automaton has 3 states. [2018-06-22 04:53:02,667 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 04:53:02,667 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 04:53:02,667 INFO ]: Found error trace [2018-06-22 04:53:02,668 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:53:02,668 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:53:02,668 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-22 04:53:02,668 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:53:02,668 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:53:02,669 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:53:02,669 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:53:02,669 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:53:03,049 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:53:03,675 WARN ]: Spent 122.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 04:53:03,688 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:53:03,688 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:53:03,688 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:53:03,695 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:53:04,129 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:53:04,163 INFO ]: Computing forward predicates... [2018-06-22 04:53:04,431 WARN ]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 04:53:06,154 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:53:06,177 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:53:06,178 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-22 04:53:06,178 INFO ]: Interpolant automaton has 6 states [2018-06-22 04:53:06,178 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 04:53:06,178 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 04:53:06,179 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-22 04:53:06,446 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:53:06,446 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 04:53:06,447 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 04:53:06,447 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-22 04:53:06,447 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:53:06,447 INFO ]: With dead ends: 10 [2018-06-22 04:53:06,447 INFO ]: Without dead ends: 10 [2018-06-22 04:53:06,448 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2018-06-22 04:53:06,448 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 04:53:06,449 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 04:53:06,449 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 04:53:06,450 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 04:53:06,450 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 04:53:06,450 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:53:06,450 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 04:53:06,450 INFO ]: Interpolant automaton has 6 states. [2018-06-22 04:53:06,450 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 04:53:06,450 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 04:53:06,450 INFO ]: Found error trace [2018-06-22 04:53:06,450 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:53:06,450 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:53:06,450 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-22 04:53:06,450 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:53:06,450 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:53:06,452 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:53:06,452 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:53:06,452 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:53:06,852 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:53:07,471 WARN ]: Spent 101.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 04:53:07,520 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:53:07,520 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:53:07,520 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:53:07,527 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 04:53:08,062 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 04:53:08,062 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:53:08,102 INFO ]: Computing forward predicates... [2018-06-22 04:53:09,743 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:53:09,768 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:53:09,768 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-22 04:53:09,768 INFO ]: Interpolant automaton has 8 states [2018-06-22 04:53:09,768 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 04:53:09,768 INFO ]: CoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-22 04:53:09,768 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 8 states. [2018-06-22 04:53:09,924 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:53:09,924 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 04:53:09,925 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 04:53:09,925 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-22 04:53:09,925 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:53:09,926 INFO ]: With dead ends: 12 [2018-06-22 04:53:09,926 INFO ]: Without dead ends: 12 [2018-06-22 04:53:09,926 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=31, Invalid=41, Unknown=0, NotChecked=0, Total=72 [2018-06-22 04:53:09,926 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 04:53:09,927 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 04:53:09,927 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 04:53:09,927 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 04:53:09,927 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 9 [2018-06-22 04:53:09,927 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:53:09,927 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 04:53:09,927 INFO ]: Interpolant automaton has 8 states. [2018-06-22 04:53:09,928 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 04:53:09,928 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 04:53:09,928 INFO ]: Found error trace [2018-06-22 04:53:09,928 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:53:09,928 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:53:09,928 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-22 04:53:09,928 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:53:09,928 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:53:09,929 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:53:09,929 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:53:09,929 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:53:10,504 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:53:11,582 WARN ]: Spent 138.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 04:53:11,879 WARN ]: Spent 161.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 04:53:12,127 WARN ]: Spent 155.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 04:53:12,389 WARN ]: Spent 142.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 04:53:12,390 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:53:12,391 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:53:12,391 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:53:12,410 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 04:53:13,347 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 04:53:13,347 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:53:13,437 INFO ]: Computing forward predicates... [2018-06-22 04:53:14,702 WARN ]: Spent 351.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 04:53:31,185 WARN ]: Simplifying disjunction of 8192 conjuctions. This might take some time... [2018-06-22 04:53:35,261 INFO ]: Simplified to disjunction of 8192 conjuctions. [2018-06-22 04:53:35,327 WARN ]: Simplifying disjunction of 8192 conjuctions. This might take some time... [2018-06-22 04:53:39,334 INFO ]: Simplified to disjunction of 8192 conjuctions. [2018-06-22 04:53:39,429 WARN ]: Simplifying disjunction of 16384 conjuctions. This might take some time... Received shutdown request... [2018-06-22 04:54:03,208 INFO ]: Timeout while computing interpolants [2018-06-22 04:54:03,408 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:54:03,409 WARN ]: Verification canceled [2018-06-22 04:54:03,413 WARN ]: Timeout [2018-06-22 04:54:03,414 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:54:03 BoogieIcfgContainer [2018-06-22 04:54:03,414 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 04:54:03,415 INFO ]: Toolchain (without parser) took 63468.98 ms. Allocated memory was 397.9 MB in the beginning and 1.5 GB in the end (delta: 1.1 GB). Free memory was 186.5 MB in the beginning and 409.7 MB in the end (delta: -223.2 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 04:54:03,416 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 303.6 MB. Free memory is still 267.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 04:54:03,416 INFO ]: ChcToBoogie took 119.72 ms. Allocated memory is still 397.9 MB. Free memory was 183.7 MB in the beginning and 178.0 MB in the end (delta: 5.7 MB). Peak memory consumption was 5.7 MB. Max. memory is 3.6 GB. [2018-06-22 04:54:03,417 INFO ]: Boogie Preprocessor took 148.92 ms. Allocated memory is still 397.9 MB. Free memory was 178.0 MB in the beginning and 173.5 MB in the end (delta: 4.5 MB). Peak memory consumption was 4.5 MB. Max. memory is 3.6 GB. [2018-06-22 04:54:03,417 INFO ]: RCFGBuilder took 1690.85 ms. Allocated memory was 397.9 MB in the beginning and 417.9 MB in the end (delta: 19.9 MB). Free memory was 173.5 MB in the beginning and 173.0 MB in the end (delta: 543.8 kB). Peak memory consumption was 20.5 MB. Max. memory is 3.6 GB. [2018-06-22 04:54:03,417 INFO ]: TraceAbstraction took 61465.87 ms. Allocated memory was 540.5 MB in the beginning and 1.5 GB in the end (delta: 955.8 MB). Free memory was 499.1 MB in the beginning and 409.7 MB in the end (delta: 89.4 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-22 04:54:03,420 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 303.6 MB. Free memory is still 267.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 119.72 ms. Allocated memory is still 397.9 MB. Free memory was 183.7 MB in the beginning and 178.0 MB in the end (delta: 5.7 MB). Peak memory consumption was 5.7 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 148.92 ms. Allocated memory is still 397.9 MB. Free memory was 178.0 MB in the beginning and 173.5 MB in the end (delta: 4.5 MB). Peak memory consumption was 4.5 MB. Max. memory is 3.6 GB. * RCFGBuilder took 1690.85 ms. Allocated memory was 397.9 MB in the beginning and 417.9 MB in the end (delta: 19.9 MB). Free memory was 173.5 MB in the beginning and 173.0 MB in the end (delta: 543.8 kB). Peak memory consumption was 20.5 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61465.87 ms. Allocated memory was 540.5 MB in the beginning and 1.5 GB in the end (delta: 955.8 MB). Free memory was 499.1 MB in the beginning and 409.7 MB in the end (delta: 89.4 MB). Peak memory consumption was 1.4 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 16384 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 61.4s OverallTime, 4 OverallIterations, 4 TraceHistogramMax, 0.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 21 SDtfs, 0 SDslu, 35 SDs, 0 SdLazy, 20 SolverSat, 6 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 29 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.7s 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.4s SsaConstructionTime, 1.4s SatisfiabilityAnalysisTime, 5.1s InterpolantComputationTime, 41 NumberOfCodeBlocks, 41 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 36 ConstructedInterpolants, 0 QuantifiedInterpolants, 746 SizeOfPredicates, 5 NumberOfNonLiveVariables, 3622 ConjunctsInSsa, 34 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 0/8 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.6.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_04-54-03-433.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/token_ring.6.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_04-54-03-433.csv Completed graceful shutdown