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.6.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 12:29:56,217 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 12:29:56,219 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 12:29:56,233 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 12:29:56,233 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 12:29:56,234 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 12:29:56,239 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 12:29:56,241 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 12:29:56,242 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 12:29:56,244 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 12:29:56,245 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 12:29:56,245 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 12:29:56,246 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 12:29:56,247 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 12:29:56,251 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 12:29:56,252 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 12:29:56,253 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 12:29:56,266 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 12:29:56,268 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 12:29:56,269 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 12:29:56,270 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 12:29:56,272 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 12:29:56,272 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 12:29:56,272 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 12:29:56,273 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 12:29:56,278 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 12:29:56,278 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 12:29:56,279 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 12:29:56,280 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 12:29:56,280 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 12:29:56,284 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 12:29:56,285 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 12:29:56,285 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 12:29:56,286 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 12:29:56,286 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 12:29:56,287 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:29:56,308 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 12:29:56,308 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 12:29:56,309 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 12:29:56,309 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 12:29:56,314 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 12:29:56,314 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 12:29:56,314 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 12:29:56,314 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 12:29:56,315 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 12:29:56,315 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 12:29:56,315 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 12:29:56,315 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 12:29:56,315 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:29:56,315 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 12:29:56,316 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 12:29:56,316 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 12:29:56,316 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 12:29:56,316 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 12:29:56,316 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 12:29:56,317 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 12:29:56,318 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 12:29:56,319 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 12:29:56,319 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 12:29:56,368 INFO ]: Repository-Root is: /tmp [2018-06-25 12:29:56,384 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 12:29:56,390 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 12:29:56,392 INFO ]: Initializing SmtParser... [2018-06-25 12:29:56,392 INFO ]: SmtParser initialized [2018-06-25 12:29:56,392 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.6.smt2 [2018-06-25 12:29:56,394 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:29:56,484 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.6.smt2 unknown [2018-06-25 12:29:59,352 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.6.smt2 [2018-06-25 12:29:59,366 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 12:29:59,373 INFO ]: Walking toolchain with 4 elements. [2018-06-25 12:29:59,374 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 12:29:59,374 INFO ]: Initializing ChcToBoogie... [2018-06-25 12:29:59,374 INFO ]: ChcToBoogie initialized [2018-06-25 12:29:59,378 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:29:59" (1/1) ... [2018-06-25 12:29:59,510 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59 Unit [2018-06-25 12:29:59,510 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 12:29:59,511 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 12:29:59,511 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 12:29:59,511 INFO ]: Boogie Preprocessor initialized [2018-06-25 12:29:59,533 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59" (1/1) ... [2018-06-25 12:29:59,533 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59" (1/1) ... [2018-06-25 12:29:59,587 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59" (1/1) ... [2018-06-25 12:29:59,588 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59" (1/1) ... [2018-06-25 12:29:59,630 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59" (1/1) ... [2018-06-25 12:29:59,632 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59" (1/1) ... [2018-06-25 12:29:59,643 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59" (1/1) ... [2018-06-25 12:29:59,656 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 12:29:59,656 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 12:29:59,656 INFO ]: Initializing RCFGBuilder... [2018-06-25 12:29:59,656 INFO ]: RCFGBuilder initialized [2018-06-25 12:29:59,657 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59" (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-25 12:29:59,680 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 12:29:59,681 INFO ]: Found specification of procedure gotoProc [2018-06-25 12:29:59,681 INFO ]: Found implementation of procedure gotoProc [2018-06-25 12:29:59,681 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 12:29:59,681 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 12:29:59,681 INFO ]: Found implementation of procedure Ultimate.START [2018-06-25 12:30:01,206 INFO ]: Using library mode [2018-06-25 12:30:01,206 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:30:01 BoogieIcfgContainer [2018-06-25 12:30:01,206 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 12:30:01,207 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 12:30:01,207 INFO ]: Initializing TraceAbstraction... [2018-06-25 12:30:01,210 INFO ]: TraceAbstraction initialized [2018-06-25 12:30:01,211 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:29:59" (1/3) ... [2018-06-25 12:30:01,211 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f8a2d04 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 12:30:01, skipping insertion in model container [2018-06-25 12:30:01,211 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:29:59" (2/3) ... [2018-06-25 12:30:01,212 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f8a2d04 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 12:30:01, skipping insertion in model container [2018-06-25 12:30:01,212 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:30:01" (3/3) ... [2018-06-25 12:30:01,213 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 12:30:01,222 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 12:30:01,231 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 12:30:01,286 INFO ]: Using default assertion order modulation [2018-06-25 12:30:01,286 INFO ]: Interprodecural is true [2018-06-25 12:30:01,286 INFO ]: Hoare is false [2018-06-25 12:30:01,286 INFO ]: Compute interpolants for FPandBP [2018-06-25 12:30:01,286 INFO ]: Backedges is TWOTRACK [2018-06-25 12:30:01,286 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 12:30:01,286 INFO ]: Difference is false [2018-06-25 12:30:01,286 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 12:30:01,286 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 12:30:01,303 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 12:30:01,316 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 12:30:01,316 INFO ]: Found error trace [2018-06-25 12:30:01,317 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:30:01,317 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:30:01,321 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 12:30:01,322 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:30:01,322 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:30:01,366 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:30:01,366 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:30:01,366 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:30:01,578 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:30:01,788 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:30:01,791 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 12:30:01,791 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 12:30:01,794 INFO ]: Interpolant automaton has 3 states [2018-06-25 12:30:01,810 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 12:30:01,810 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:30:01,813 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 12:30:01,992 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:30:01,993 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 12:30:01,994 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 12:30:01,995 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 12:30:01,995 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:30:02,005 INFO ]: With dead ends: 9 [2018-06-25 12:30:02,005 INFO ]: Without dead ends: 9 [2018-06-25 12:30:02,008 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:30:02,024 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 12:30:02,044 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 12:30:02,045 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 12:30:02,046 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 12:30:02,047 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 12:30:02,047 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:30:02,047 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 12:30:02,047 INFO ]: Interpolant automaton has 3 states. [2018-06-25 12:30:02,047 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 12:30:02,048 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 12:30:02,048 INFO ]: Found error trace [2018-06-25 12:30:02,048 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:30:02,048 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:30:02,048 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 12:30:02,048 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:30:02,048 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:30:02,049 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:30:02,049 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:30:02,049 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:30:02,412 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:30:02,975 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:30:02,975 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:30:02,975 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:30:02,984 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:30:03,494 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:30:03,526 INFO ]: Computing forward predicates... [2018-06-25 12:30:03,811 WARN ]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-25 12:30:05,480 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:30:05,504 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:30:05,504 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-25 12:30:05,504 INFO ]: Interpolant automaton has 6 states [2018-06-25 12:30:05,505 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 12:30:05,505 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:30:05,505 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-25 12:30:05,690 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:30:05,691 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 12:30:05,691 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 12:30:05,691 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-25 12:30:05,691 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:30:05,691 INFO ]: With dead ends: 10 [2018-06-25 12:30:05,691 INFO ]: Without dead ends: 10 [2018-06-25 12:30:05,692 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2018-06-25 12:30:05,692 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 12:30:05,693 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 12:30:05,693 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 12:30:05,693 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 12:30:05,694 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 12:30:05,694 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:30:05,694 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 12:30:05,694 INFO ]: Interpolant automaton has 6 states. [2018-06-25 12:30:05,694 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 12:30:05,694 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 12:30:05,694 INFO ]: Found error trace [2018-06-25 12:30:05,694 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:30:05,694 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:30:05,694 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 12:30:05,694 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:30:05,694 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:30:05,697 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:30:05,697 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:30:05,697 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:30:06,163 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:30:07,064 WARN ]: Spent 141.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 12:30:07,359 WARN ]: Spent 143.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-25 12:30:07,360 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:30:07,360 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:30:07,360 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:30:07,375 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:30:07,894 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:30:07,894 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:30:07,942 INFO ]: Computing forward predicates... [2018-06-25 12:30:08,198 WARN ]: Spent 124.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-25 12:30:09,781 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:30:09,806 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:30:09,806 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-25 12:30:09,806 INFO ]: Interpolant automaton has 8 states [2018-06-25 12:30:09,806 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 12:30:09,806 INFO ]: CoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-25 12:30:09,806 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 8 states. [2018-06-25 12:30:09,993 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:30:09,993 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 12:30:10,037 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 12:30:10,037 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-25 12:30:10,037 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:30:10,038 INFO ]: With dead ends: 12 [2018-06-25 12:30:10,038 INFO ]: Without dead ends: 12 [2018-06-25 12:30:10,038 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=31, Invalid=41, Unknown=0, NotChecked=0, Total=72 [2018-06-25 12:30:10,038 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 12:30:10,039 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 12:30:10,039 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 12:30:10,040 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 12:30:10,040 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 9 [2018-06-25 12:30:10,040 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:30:10,040 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 12:30:10,040 INFO ]: Interpolant automaton has 8 states. [2018-06-25 12:30:10,040 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 12:30:10,040 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 12:30:10,040 INFO ]: Found error trace [2018-06-25 12:30:10,040 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:30:10,040 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:30:10,040 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-25 12:30:10,041 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:30:10,041 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:30:10,041 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:30:10,041 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:30:10,041 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:30:10,807 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:30:11,762 WARN ]: Spent 138.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-25 12:30:11,970 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:30:11,970 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:30:11,970 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:30:11,978 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 12:30:12,680 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 12:30:12,680 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:30:12,747 INFO ]: Computing forward predicates... [2018-06-25 12:30:14,218 WARN ]: Spent 362.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-25 12:30:30,856 WARN ]: Simplifying disjunction of 8192 conjuctions. This might take some time... [2018-06-25 12:30:35,548 INFO ]: Simplified to disjunction of 8192 conjuctions. [2018-06-25 12:30:35,617 WARN ]: Simplifying disjunction of 8192 conjuctions. This might take some time... [2018-06-25 12:30:40,004 INFO ]: Simplified to disjunction of 8192 conjuctions. [2018-06-25 12:30:40,109 WARN ]: Simplifying disjunction of 16384 conjuctions. This might take some time... Received shutdown request... [2018-06-25 12:31:00,637 INFO ]: Timeout while computing interpolants [2018-06-25 12:31:00,837 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:31:00,837 WARN ]: Verification canceled [2018-06-25 12:31:00,842 WARN ]: Timeout [2018-06-25 12:31:00,842 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 12:31:00 BoogieIcfgContainer [2018-06-25 12:31:00,842 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 12:31:00,843 INFO ]: Toolchain (without parser) took 61476.46 ms. Allocated memory was 403.2 MB in the beginning and 1.5 GB in the end (delta: 1.1 GB). Free memory was 187.0 MB in the beginning and 513.9 MB in the end (delta: -326.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-25 12:31:00,843 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:31:00,844 INFO ]: ChcToBoogie took 136.62 ms. Allocated memory is still 403.2 MB. Free memory was 184.1 MB in the beginning and 179.0 MB in the end (delta: 5.2 MB). Peak memory consumption was 5.2 MB. Max. memory is 3.6 GB. [2018-06-25 12:31:00,844 INFO ]: Boogie Preprocessor took 145.19 ms. Allocated memory was 403.2 MB in the beginning and 412.6 MB in the end (delta: 9.4 MB). Free memory was 179.0 MB in the beginning and 380.6 MB in the end (delta: -201.7 MB). There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:31:00,844 INFO ]: RCFGBuilder took 1550.04 ms. Allocated memory was 412.6 MB in the beginning and 516.4 MB in the end (delta: 103.8 MB). Free memory was 380.6 MB in the beginning and 452.6 MB in the end (delta: -72.0 MB). Peak memory consumption was 205.2 MB. Max. memory is 3.6 GB. [2018-06-25 12:31:00,844 INFO ]: TraceAbstraction took 59634.54 ms. Allocated memory was 516.4 MB in the beginning and 1.5 GB in the end (delta: 984.1 MB). Free memory was 452.6 MB in the beginning and 513.9 MB in the end (delta: -61.3 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:31:00,846 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.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 136.62 ms. Allocated memory is still 403.2 MB. Free memory was 184.1 MB in the beginning and 179.0 MB in the end (delta: 5.2 MB). Peak memory consumption was 5.2 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 145.19 ms. Allocated memory was 403.2 MB in the beginning and 412.6 MB in the end (delta: 9.4 MB). Free memory was 179.0 MB in the beginning and 380.6 MB in the end (delta: -201.7 MB). There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 1550.04 ms. Allocated memory was 412.6 MB in the beginning and 516.4 MB in the end (delta: 103.8 MB). Free memory was 380.6 MB in the beginning and 452.6 MB in the end (delta: -72.0 MB). Peak memory consumption was 205.2 MB. Max. memory is 3.6 GB. * TraceAbstraction took 59634.54 ms. Allocated memory was 516.4 MB in the beginning and 1.5 GB in the end (delta: 984.1 MB). Free memory was 452.6 MB in the beginning and 513.9 MB in the end (delta: -61.3 MB). Peak memory consumption was 1.3 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, 59.5s 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, 1.2s 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.6s SatisfiabilityAnalysisTime, 5.8s 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-25_12-31-00-860.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-25_12-31-00-860.csv Completed graceful shutdown