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.10.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 04:48:07,032 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 04:48:07,034 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 04:48:07,048 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 04:48:07,048 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 04:48:07,050 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 04:48:07,051 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 04:48:07,056 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 04:48:07,057 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 04:48:07,060 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 04:48:07,061 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 04:48:07,061 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 04:48:07,062 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 04:48:07,067 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 04:48:07,068 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 04:48:07,069 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 04:48:07,081 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 04:48:07,086 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 04:48:07,087 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 04:48:07,089 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 04:48:07,090 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 04:48:07,092 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 04:48:07,092 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 04:48:07,092 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 04:48:07,093 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 04:48:07,094 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 04:48:07,099 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 04:48:07,099 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 04:48:07,100 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 04:48:07,101 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 04:48:07,101 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 04:48:07,108 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 04:48:07,109 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 04:48:07,110 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 04:48:07,110 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 04:48:07,111 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:48:07,131 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 04:48:07,132 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 04:48:07,132 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 04:48:07,132 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 04:48:07,133 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 04:48:07,134 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 04:48:07,134 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 04:48:07,134 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 04:48:07,134 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:48:07,134 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 04:48:07,137 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 04:48:07,137 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 04:48:07,138 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 04:48:07,138 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 04:48:07,138 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 04:48:07,138 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 04:48:07,138 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 04:48:07,140 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 04:48:07,140 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 04:48:07,192 INFO ]: Repository-Root is: /tmp [2018-06-22 04:48:07,206 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 04:48:07,209 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 04:48:07,211 INFO ]: Initializing SmtParser... [2018-06-22 04:48:07,211 INFO ]: SmtParser initialized [2018-06-22 04:48:07,212 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.10.smt2 [2018-06-22 04:48:07,213 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:48:07,308 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.10.smt2 unknown [2018-06-22 04:48:12,009 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.10.smt2 [2018-06-22 04:48:12,013 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 04:48:12,027 INFO ]: Walking toolchain with 4 elements. [2018-06-22 04:48:12,027 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 04:48:12,027 INFO ]: Initializing ChcToBoogie... [2018-06-22 04:48:12,027 INFO ]: ChcToBoogie initialized [2018-06-22 04:48:12,031 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:48:12" (1/1) ... [2018-06-22 04:48:12,197 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12 Unit [2018-06-22 04:48:12,197 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 04:48:12,198 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 04:48:12,198 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 04:48:12,198 INFO ]: Boogie Preprocessor initialized [2018-06-22 04:48:12,217 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12" (1/1) ... [2018-06-22 04:48:12,217 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12" (1/1) ... [2018-06-22 04:48:12,279 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12" (1/1) ... [2018-06-22 04:48:12,279 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12" (1/1) ... [2018-06-22 04:48:12,349 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12" (1/1) ... [2018-06-22 04:48:12,350 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12" (1/1) ... [2018-06-22 04:48:12,376 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12" (1/1) ... [2018-06-22 04:48:12,401 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 04:48:12,405 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 04:48:12,405 INFO ]: Initializing RCFGBuilder... [2018-06-22 04:48:12,405 INFO ]: RCFGBuilder initialized [2018-06-22 04:48:12,406 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12" (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-22 04:48:12,424 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 04:48:12,424 INFO ]: Found specification of procedure gotoProc [2018-06-22 04:48:12,424 INFO ]: Found implementation of procedure gotoProc [2018-06-22 04:48:12,424 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 04:48:12,424 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 04:48:12,424 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-22 04:48:17,326 INFO ]: Using library mode [2018-06-22 04:48:17,327 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:48:17 BoogieIcfgContainer [2018-06-22 04:48:17,327 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 04:48:17,328 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 04:48:17,328 INFO ]: Initializing TraceAbstraction... [2018-06-22 04:48:17,332 INFO ]: TraceAbstraction initialized [2018-06-22 04:48:17,332 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:48:12" (1/3) ... [2018-06-22 04:48:17,333 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c6bb921 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:48:17, skipping insertion in model container [2018-06-22 04:48:17,333 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:48:12" (2/3) ... [2018-06-22 04:48:17,333 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7c6bb921 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:48:17, skipping insertion in model container [2018-06-22 04:48:17,333 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:48:17" (3/3) ... [2018-06-22 04:48:17,335 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 04:48:17,344 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 04:48:17,356 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 04:48:17,399 INFO ]: Using default assertion order modulation [2018-06-22 04:48:17,399 INFO ]: Interprodecural is true [2018-06-22 04:48:17,399 INFO ]: Hoare is false [2018-06-22 04:48:17,399 INFO ]: Compute interpolants for FPandBP [2018-06-22 04:48:17,399 INFO ]: Backedges is TWOTRACK [2018-06-22 04:48:17,399 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 04:48:17,399 INFO ]: Difference is false [2018-06-22 04:48:17,399 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 04:48:17,399 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 04:48:17,419 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 04:48:17,433 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 04:48:17,433 INFO ]: Found error trace [2018-06-22 04:48:17,436 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:48:17,437 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:48:17,442 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 04:48:17,445 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:48:17,445 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:48:17,486 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:48:17,487 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:48:17,487 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:48:17,786 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:48:18,016 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:48:18,018 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 04:48:18,019 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 04:48:18,021 INFO ]: Interpolant automaton has 3 states [2018-06-22 04:48:18,036 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 04:48:18,036 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:48:18,039 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 04:48:18,386 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:48:18,386 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 04:48:18,387 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 04:48:18,388 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 04:48:18,389 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:48:18,397 INFO ]: With dead ends: 9 [2018-06-22 04:48:18,398 INFO ]: Without dead ends: 9 [2018-06-22 04:48:18,402 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:48:18,420 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 04:48:18,448 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 04:48:18,449 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 04:48:18,450 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 04:48:18,451 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 04:48:18,451 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:48:18,452 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 04:48:18,452 INFO ]: Interpolant automaton has 3 states. [2018-06-22 04:48:18,452 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 04:48:18,452 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 04:48:18,452 INFO ]: Found error trace [2018-06-22 04:48:18,452 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:48:18,452 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:48:18,452 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 04:48:18,452 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:48:18,452 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:48:18,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:48:18,453 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:48:18,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:48:19,202 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:48:20,391 WARN ]: Spent 179.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 04:48:20,473 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:48:20,473 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:48:20,473 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:48:20,480 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:48:21,368 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:48:21,432 INFO ]: Computing forward predicates... [2018-06-22 04:48:23,290 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:48:23,319 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:48:23,319 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-22 04:48:23,320 INFO ]: Interpolant automaton has 6 states [2018-06-22 04:48:23,320 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 04:48:23,320 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-22 04:48:23,320 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-22 04:48:23,716 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:48:23,716 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 04:48:23,716 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 04:48:23,716 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-22 04:48:23,717 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:48:23,717 INFO ]: With dead ends: 10 [2018-06-22 04:48:23,717 INFO ]: Without dead ends: 10 [2018-06-22 04:48:23,718 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-06-22 04:48:23,718 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 04:48:23,719 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 04:48:23,719 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 04:48:23,719 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 04:48:23,719 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 04:48:23,719 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:48:23,719 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 04:48:23,719 INFO ]: Interpolant automaton has 6 states. [2018-06-22 04:48:23,719 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 04:48:23,720 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 04:48:23,720 INFO ]: Found error trace [2018-06-22 04:48:23,720 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:48:23,720 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:48:23,720 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-22 04:48:23,720 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:48:23,720 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:48:23,721 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:48:23,721 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:48:23,721 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:48:24,834 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:48:26,205 WARN ]: Spent 148.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 04:48:26,224 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:48:26,224 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:48:26,224 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:48:26,233 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 04:48:27,468 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 04:48:27,468 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:48:27,584 INFO ]: Computing forward predicates... [2018-06-22 04:48:54,372 WARN ]: Spent 241.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 22 [2018-06-22 04:48:54,378 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:48:54,407 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:48:54,407 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-22 04:48:54,408 INFO ]: Interpolant automaton has 8 states [2018-06-22 04:48:54,408 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 04:48:54,408 INFO ]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2018-06-22 04:48:54,408 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 8 states. [2018-06-22 04:48:54,849 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:48:54,849 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 04:48:54,850 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 04:48:54,850 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-22 04:48:54,850 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:48:54,850 INFO ]: With dead ends: 12 [2018-06-22 04:48:54,850 INFO ]: Without dead ends: 12 [2018-06-22 04:48:54,850 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2018-06-22 04:48:54,850 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 04:48:54,852 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 04:48:54,852 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 04:48:54,853 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 04:48:54,853 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 9 [2018-06-22 04:48:54,853 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:48:54,853 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 04:48:54,853 INFO ]: Interpolant automaton has 8 states. [2018-06-22 04:48:54,853 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 04:48:54,853 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 04:48:54,853 INFO ]: Found error trace [2018-06-22 04:48:54,853 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:48:54,854 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:48:54,854 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 3 times [2018-06-22 04:48:54,854 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:48:54,854 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:48:54,855 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:48:54,855 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:48:54,855 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:48:56,184 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:48:58,663 WARN ]: Spent 188.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 04:48:58,926 WARN ]: Spent 214.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 04:48:59,000 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:48:59,000 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:48:59,000 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:48:59,007 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 04:49:00,851 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 04:49:00,851 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:49:00,998 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 04:49:01,932 INFO ]: Timeout while computing interpolants [2018-06-22 04:49:02,132 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:49:02,133 WARN ]: Verification canceled [2018-06-22 04:49:02,137 WARN ]: Timeout [2018-06-22 04:49:02,137 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:49:02 BoogieIcfgContainer [2018-06-22 04:49:02,137 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 04:49:02,138 INFO ]: Toolchain (without parser) took 50123.72 ms. Allocated memory was 625.5 MB in the beginning and 1.7 GB in the end (delta: 1.0 GB). Free memory was 329.5 MB in the beginning and 1.2 GB in the end (delta: -830.1 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 04:49:02,138 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 04:49:02,138 INFO ]: ChcToBoogie took 170.28 ms. Allocated memory is still 625.5 MB. Free memory was 329.5 MB in the beginning and 321.8 MB in the end (delta: 7.8 MB). Peak memory consumption was 7.8 MB. Max. memory is 3.6 GB. [2018-06-22 04:49:02,139 INFO ]: Boogie Preprocessor took 203.40 ms. Allocated memory is still 625.5 MB. Free memory was 321.8 MB in the beginning and 306.3 MB in the end (delta: 15.5 MB). Peak memory consumption was 15.5 MB. Max. memory is 3.6 GB. [2018-06-22 04:49:02,139 INFO ]: RCFGBuilder took 4921.83 ms. Allocated memory was 625.5 MB in the beginning and 1.2 GB in the end (delta: 609.2 MB). Free memory was 306.3 MB in the beginning and 978.3 MB in the end (delta: -672.0 MB). Peak memory consumption was 520.2 MB. Max. memory is 3.6 GB. [2018-06-22 04:49:02,139 INFO ]: TraceAbstraction took 44808.46 ms. Allocated memory was 1.2 GB in the beginning and 1.7 GB in the end (delta: 417.9 MB). Free memory was 978.3 MB in the beginning and 1.2 GB in the end (delta: -181.4 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 04:49:02,142 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 308.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 170.28 ms. Allocated memory is still 625.5 MB. Free memory was 329.5 MB in the beginning and 321.8 MB in the end (delta: 7.8 MB). Peak memory consumption was 7.8 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 203.40 ms. Allocated memory is still 625.5 MB. Free memory was 321.8 MB in the beginning and 306.3 MB in the end (delta: 15.5 MB). Peak memory consumption was 15.5 MB. Max. memory is 3.6 GB. * RCFGBuilder took 4921.83 ms. Allocated memory was 625.5 MB in the beginning and 1.2 GB in the end (delta: 609.2 MB). Free memory was 306.3 MB in the beginning and 978.3 MB in the end (delta: -672.0 MB). Peak memory consumption was 520.2 MB. Max. memory is 3.6 GB. * TraceAbstraction took 44808.46 ms. Allocated memory was 1.2 GB in the beginning and 1.7 GB in the end (delta: 417.9 MB). Free memory was 978.3 MB in the beginning and 1.2 GB in the end (delta: -181.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 1133 quantified variables from 10 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 44.7s OverallTime, 4 OverallIterations, 4 TraceHistogramMax, 1.2s 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.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 29 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 1.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.8s SsaConstructionTime, 3.4s SatisfiabilityAnalysisTime, 31.6s InterpolantComputationTime, 41 NumberOfCodeBlocks, 41 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 36 ConstructedInterpolants, 0 QuantifiedInterpolants, 1163 SizeOfPredicates, 6 NumberOfNonLiveVariables, 7385 ConjunctsInSsa, 38 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.10.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_04-49-02-156.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/token_ring.10.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_04-49-02-156.csv Completed graceful shutdown