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/vmt-chc-benchmarks/cav12/token_ring.4.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 12:28:48,686 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 12:28:48,688 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 12:28:48,704 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 12:28:48,705 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 12:28:48,706 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 12:28:48,708 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 12:28:48,710 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 12:28:48,712 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 12:28:48,712 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 12:28:48,714 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 12:28:48,714 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 12:28:48,715 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 12:28:48,716 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 12:28:48,717 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 12:28:48,720 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 12:28:48,722 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 12:28:48,723 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 12:28:48,737 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 12:28:48,738 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 12:28:48,739 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 12:28:48,741 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 12:28:48,741 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 12:28:48,741 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 12:28:48,742 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 12:28:48,743 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 12:28:48,744 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 12:28:48,749 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 12:28:48,750 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 12:28:48,750 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 12:28:48,751 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 12:28:48,751 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 12:28:48,751 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 12:28:48,752 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 12:28:48,759 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 12:28:48,760 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 12:28:48,782 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 12:28:48,782 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 12:28:48,782 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 12:28:48,782 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 12:28:48,786 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 12:28:48,786 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 12:28:48,786 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 12:28:48,786 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 12:28:48,787 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 12:28:48,787 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 12:28:48,787 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 12:28:48,787 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 12:28:48,787 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:28:48,787 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 12:28:48,788 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 12:28:48,788 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 12:28:48,788 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 12:28:48,788 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 12:28:48,788 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 12:28:48,788 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 12:28:48,792 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 12:28:48,793 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 12:28:48,793 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 12:28:48,835 INFO ]: Repository-Root is: /tmp [2018-06-25 12:28:48,851 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 12:28:48,857 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 12:28:48,858 INFO ]: Initializing SmtParser... [2018-06-25 12:28:48,859 INFO ]: SmtParser initialized [2018-06-25 12:28:48,859 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.4.smt2 [2018-06-25 12:28:48,861 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 12:28:48,946 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.4.smt2 unknown [2018-06-25 12:28:50,277 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.4.smt2 [2018-06-25 12:28:50,281 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 12:28:50,290 INFO ]: Walking toolchain with 4 elements. [2018-06-25 12:28:50,291 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 12:28:50,291 INFO ]: Initializing ChcToBoogie... [2018-06-25 12:28:50,291 INFO ]: ChcToBoogie initialized [2018-06-25 12:28:50,294 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:28:50" (1/1) ... [2018-06-25 12:28:50,390 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50 Unit [2018-06-25 12:28:50,390 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 12:28:50,391 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 12:28:50,391 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 12:28:50,391 INFO ]: Boogie Preprocessor initialized [2018-06-25 12:28:50,411 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50" (1/1) ... [2018-06-25 12:28:50,411 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50" (1/1) ... [2018-06-25 12:28:50,443 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50" (1/1) ... [2018-06-25 12:28:50,443 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50" (1/1) ... [2018-06-25 12:28:50,486 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50" (1/1) ... [2018-06-25 12:28:50,487 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50" (1/1) ... [2018-06-25 12:28:50,500 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50" (1/1) ... [2018-06-25 12:28:50,516 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 12:28:50,517 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 12:28:50,517 INFO ]: Initializing RCFGBuilder... [2018-06-25 12:28:50,517 INFO ]: RCFGBuilder initialized [2018-06-25 12:28:50,518 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50" (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 12:28:50,534 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 12:28:50,534 INFO ]: Found specification of procedure gotoProc [2018-06-25 12:28:50,534 INFO ]: Found implementation of procedure gotoProc [2018-06-25 12:28:50,534 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 12:28:50,534 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 12:28:50,534 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 12:28:51,448 INFO ]: Using library mode [2018-06-25 12:28:51,449 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:28:51 BoogieIcfgContainer [2018-06-25 12:28:51,449 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 12:28:51,450 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 12:28:51,451 INFO ]: Initializing TraceAbstraction... [2018-06-25 12:28:51,454 INFO ]: TraceAbstraction initialized [2018-06-25 12:28:51,455 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:28:50" (1/3) ... [2018-06-25 12:28:51,456 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10d4e878 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 12:28:51, skipping insertion in model container [2018-06-25 12:28:51,456 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:28:50" (2/3) ... [2018-06-25 12:28:51,456 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10d4e878 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 12:28:51, skipping insertion in model container [2018-06-25 12:28:51,456 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:28:51" (3/3) ... [2018-06-25 12:28:51,458 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 12:28:51,468 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 12:28:51,476 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 12:28:51,531 INFO ]: Using default assertion order modulation [2018-06-25 12:28:51,532 INFO ]: Interprodecural is true [2018-06-25 12:28:51,532 INFO ]: Hoare is false [2018-06-25 12:28:51,532 INFO ]: Compute interpolants for FPandBP [2018-06-25 12:28:51,532 INFO ]: Backedges is TWOTRACK [2018-06-25 12:28:51,532 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 12:28:51,532 INFO ]: Difference is false [2018-06-25 12:28:51,532 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 12:28:51,532 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 12:28:51,550 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 12:28:51,562 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 12:28:51,562 INFO ]: Found error trace [2018-06-25 12:28:51,563 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:28:51,563 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:28:51,569 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 12:28:51,571 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:28:51,571 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:28:51,608 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:28:51,608 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:28:51,608 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:28:51,751 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:28:51,931 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:28:51,933 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 12:28:51,933 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 12:28:51,934 INFO ]: Interpolant automaton has 3 states [2018-06-25 12:28:51,945 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 12:28:51,945 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:28:51,947 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 12:28:52,073 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:28:52,073 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 12:28:52,075 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 12:28:52,076 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 12:28:52,076 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:28:52,087 INFO ]: With dead ends: 9 [2018-06-25 12:28:52,087 INFO ]: Without dead ends: 9 [2018-06-25 12:28:52,089 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-25 12:28:52,108 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 12:28:52,139 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 12:28:52,140 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 12:28:52,141 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 12:28:52,142 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 12:28:52,142 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:28:52,142 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 12:28:52,142 INFO ]: Interpolant automaton has 3 states. [2018-06-25 12:28:52,142 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 12:28:52,142 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 12:28:52,143 INFO ]: Found error trace [2018-06-25 12:28:52,143 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:28:52,143 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:28:52,143 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 12:28:52,143 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:28:52,143 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:28:52,144 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:28:52,144 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:28:52,144 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:28:52,407 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:28:52,813 WARN ]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-25 12:28:52,937 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:28:52,937 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:28:52,937 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:28:52,952 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:28:53,248 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:28:53,274 INFO ]: Computing forward predicates... [2018-06-25 12:28:53,530 WARN ]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-25 12:28:54,387 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:28:54,409 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:28:54,409 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-25 12:28:54,409 INFO ]: Interpolant automaton has 6 states [2018-06-25 12:28:54,409 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 12:28:54,409 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:28:54,410 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-25 12:28:54,523 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:28:54,523 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 12:28:54,523 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 12:28:54,523 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-25 12:28:54,523 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:28:54,523 INFO ]: With dead ends: 10 [2018-06-25 12:28:54,523 INFO ]: Without dead ends: 10 [2018-06-25 12:28:54,524 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-25 12:28:54,524 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 12:28:54,525 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 12:28:54,525 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 12:28:54,525 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 12:28:54,525 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 12:28:54,525 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:28:54,525 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 12:28:54,525 INFO ]: Interpolant automaton has 6 states. [2018-06-25 12:28:54,525 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 12:28:54,526 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 12:28:54,526 INFO ]: Found error trace [2018-06-25 12:28:54,526 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:28:54,526 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:28:54,526 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 12:28:54,526 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:28:54,526 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:28:54,527 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:28:54,527 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:28:54,527 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:28:54,817 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:28:55,621 WARN ]: Spent 139.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-25 12:28:55,621 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:28:55,622 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:28:55,622 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) [2018-06-25 12:28:55,639 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:28:55,972 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:28:55,972 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:28:56,002 INFO ]: Computing forward predicates... [2018-06-25 12:28:56,234 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-25 12:28:59,831 WARN ]: Spent 1.44 s on a formula simplification. DAG size of input: 17 DAG size of output: 15 [2018-06-25 12:28:59,848 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:28:59,885 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:28:59,885 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-25 12:28:59,885 INFO ]: Interpolant automaton has 8 states [2018-06-25 12:28:59,885 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 12:28:59,885 INFO ]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-06-25 12:28:59,886 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 8 states. [2018-06-25 12:29:00,251 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 17 [2018-06-25 12:29:00,293 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:29:00,293 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 12:29:00,293 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 12:29:00,293 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-25 12:29:00,293 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:29:00,294 INFO ]: With dead ends: 12 [2018-06-25 12:29:00,294 INFO ]: Without dead ends: 12 [2018-06-25 12:29:00,294 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=44, Invalid=66, Unknown=0, NotChecked=0, Total=110 [2018-06-25 12:29:00,294 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 12:29:00,295 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 12:29:00,295 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 12:29:00,295 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 12:29:00,296 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 9 [2018-06-25 12:29:00,296 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:29:00,296 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 12:29:00,296 INFO ]: Interpolant automaton has 8 states. [2018-06-25 12:29:00,296 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 12:29:00,296 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 12:29:00,296 INFO ]: Found error trace [2018-06-25 12:29:00,296 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:29:00,296 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:29:00,296 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-25 12:29:00,296 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:29:00,296 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:29:00,297 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:29:00,297 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:29:00,297 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:29:00,809 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:29:01,836 WARN ]: Spent 259.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-25 12:29:01,896 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:29:01,896 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:29:01,896 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-25 12:29:01,903 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 12:29:02,399 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 12:29:02,399 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:29:02,489 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-25 12:29:52,914 INFO ]: Timeout while computing interpolants [2018-06-25 12:29:53,115 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:29:53,115 WARN ]: Verification canceled [2018-06-25 12:29:53,118 WARN ]: Timeout [2018-06-25 12:29:53,119 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 12:29:53 BoogieIcfgContainer [2018-06-25 12:29:53,119 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 12:29:53,119 INFO ]: Toolchain (without parser) took 62836.03 ms. Allocated memory was 334.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 220.1 MB in the beginning and 280.9 MB in the end (delta: -60.8 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:29:53,120 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:29:53,120 INFO ]: ChcToBoogie took 99.80 ms. Allocated memory is still 334.5 MB. Free memory was 220.1 MB in the beginning and 215.3 MB in the end (delta: 4.8 MB). Peak memory consumption was 4.8 MB. Max. memory is 3.6 GB. [2018-06-25 12:29:53,120 INFO ]: Boogie Preprocessor took 125.65 ms. Allocated memory is still 334.5 MB. Free memory was 215.3 MB in the beginning and 212.1 MB in the end (delta: 3.2 MB). Peak memory consumption was 3.2 MB. Max. memory is 3.6 GB. [2018-06-25 12:29:53,120 INFO ]: RCFGBuilder took 932.20 ms. Allocated memory was 334.5 MB in the beginning and 372.8 MB in the end (delta: 38.3 MB). Free memory was 212.1 MB in the beginning and 211.6 MB in the end (delta: 495.0 kB). Peak memory consumption was 40.2 MB. Max. memory is 3.6 GB. [2018-06-25 12:29:53,121 INFO ]: TraceAbstraction took 61668.08 ms. Allocated memory was 372.8 MB in the beginning and 1.5 GB in the end (delta: 1.1 GB). Free memory was 211.6 MB in the beginning and 280.9 MB in the end (delta: -69.4 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-25 12:29:53,123 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 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 99.80 ms. Allocated memory is still 334.5 MB. Free memory was 220.1 MB in the beginning and 215.3 MB in the end (delta: 4.8 MB). Peak memory consumption was 4.8 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 125.65 ms. Allocated memory is still 334.5 MB. Free memory was 215.3 MB in the beginning and 212.1 MB in the end (delta: 3.2 MB). Peak memory consumption was 3.2 MB. Max. memory is 3.6 GB. * RCFGBuilder took 932.20 ms. Allocated memory was 334.5 MB in the beginning and 372.8 MB in the end (delta: 38.3 MB). Free memory was 212.1 MB in the beginning and 211.6 MB in the end (delta: 495.0 kB). Peak memory consumption was 40.2 MB. Max. memory is 3.6 GB. * TraceAbstraction took 61668.08 ms. Allocated memory was 372.8 MB in the beginning and 1.5 GB in the end (delta: 1.1 GB). Free memory was 211.6 MB in the beginning and 280.9 MB in the end (delta: -69.4 MB). Peak memory consumption was 1.2 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 XnfDer was eliminating 48 quantified variables from 12 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 61.6s OverallTime, 4 OverallIterations, 4 TraceHistogramMax, 0.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 21 SDtfs, 0 SDslu, 40 SDs, 0 SdLazy, 22 SolverSat, 5 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 31 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 3.0s 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.2s SsaConstructionTime, 1.0s SatisfiabilityAnalysisTime, 6.5s InterpolantComputationTime, 41 NumberOfCodeBlocks, 41 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 36 ConstructedInterpolants, 0 QuantifiedInterpolants, 738 SizeOfPredicates, 5 NumberOfNonLiveVariables, 2250 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.4.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_12-29-53-137.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/token_ring.4.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_12-29-53-137.csv Completed graceful shutdown