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.1.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 04:50:04,208 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 04:50:04,210 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 04:50:04,221 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 04:50:04,222 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 04:50:04,223 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 04:50:04,224 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 04:50:04,228 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 04:50:04,229 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 04:50:04,230 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 04:50:04,231 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 04:50:04,231 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 04:50:04,232 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 04:50:04,233 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 04:50:04,234 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 04:50:04,234 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 04:50:04,238 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 04:50:04,240 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 04:50:04,242 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 04:50:04,254 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 04:50:04,255 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 04:50:04,259 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 04:50:04,259 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 04:50:04,259 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 04:50:04,260 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 04:50:04,261 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 04:50:04,261 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 04:50:04,262 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 04:50:04,263 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 04:50:04,263 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 04:50:04,264 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 04:50:04,264 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 04:50:04,265 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 04:50:04,265 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 04:50:04,266 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 04:50:04,266 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:50:04,285 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 04:50:04,286 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 04:50:04,286 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 04:50:04,286 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 04:50:04,287 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 04:50:04,288 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 04:50:04,288 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 04:50:04,288 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 04:50:04,288 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:50:04,288 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 04:50:04,289 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 04:50:04,289 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 04:50:04,289 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 04:50:04,289 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 04:50:04,289 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 04:50:04,290 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 04:50:04,290 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 04:50:04,291 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 04:50:04,291 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 04:50:04,346 INFO ]: Repository-Root is: /tmp [2018-06-22 04:50:04,363 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 04:50:04,367 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 04:50:04,369 INFO ]: Initializing SmtParser... [2018-06-22 04:50:04,369 INFO ]: SmtParser initialized [2018-06-22 04:50:04,370 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.1.smt2 [2018-06-22 04:50:04,371 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:50:04,464 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.1.smt2 unknown [2018-06-22 04:50:05,152 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.1.smt2 [2018-06-22 04:50:05,163 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 04:50:05,178 INFO ]: Walking toolchain with 4 elements. [2018-06-22 04:50:05,178 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 04:50:05,178 INFO ]: Initializing ChcToBoogie... [2018-06-22 04:50:05,178 INFO ]: ChcToBoogie initialized [2018-06-22 04:50:05,181 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:50:05" (1/1) ... [2018-06-22 04:50:05,275 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05 Unit [2018-06-22 04:50:05,275 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 04:50:05,276 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 04:50:05,276 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 04:50:05,276 INFO ]: Boogie Preprocessor initialized [2018-06-22 04:50:05,297 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05" (1/1) ... [2018-06-22 04:50:05,297 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05" (1/1) ... [2018-06-22 04:50:05,320 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05" (1/1) ... [2018-06-22 04:50:05,321 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05" (1/1) ... [2018-06-22 04:50:05,341 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05" (1/1) ... [2018-06-22 04:50:05,342 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05" (1/1) ... [2018-06-22 04:50:05,349 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05" (1/1) ... [2018-06-22 04:50:05,353 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 04:50:05,354 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 04:50:05,354 INFO ]: Initializing RCFGBuilder... [2018-06-22 04:50:05,354 INFO ]: RCFGBuilder initialized [2018-06-22 04:50:05,355 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05" (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:50:05,366 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 04:50:05,366 INFO ]: Found specification of procedure gotoProc [2018-06-22 04:50:05,366 INFO ]: Found implementation of procedure gotoProc [2018-06-22 04:50:05,366 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 04:50:05,366 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 04:50:05,366 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:50:05,844 INFO ]: Using library mode [2018-06-22 04:50:05,846 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:50:05 BoogieIcfgContainer [2018-06-22 04:50:05,846 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 04:50:05,848 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 04:50:05,848 INFO ]: Initializing TraceAbstraction... [2018-06-22 04:50:05,855 INFO ]: TraceAbstraction initialized [2018-06-22 04:50:05,855 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:50:05" (1/3) ... [2018-06-22 04:50:05,856 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11fdf5d4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:50:05, skipping insertion in model container [2018-06-22 04:50:05,856 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:50:05" (2/3) ... [2018-06-22 04:50:05,856 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@11fdf5d4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:50:05, skipping insertion in model container [2018-06-22 04:50:05,857 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:50:05" (3/3) ... [2018-06-22 04:50:05,859 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 04:50:05,872 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 04:50:05,881 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 04:50:05,940 INFO ]: Using default assertion order modulation [2018-06-22 04:50:05,940 INFO ]: Interprodecural is true [2018-06-22 04:50:05,940 INFO ]: Hoare is false [2018-06-22 04:50:05,940 INFO ]: Compute interpolants for FPandBP [2018-06-22 04:50:05,940 INFO ]: Backedges is TWOTRACK [2018-06-22 04:50:05,940 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 04:50:05,940 INFO ]: Difference is false [2018-06-22 04:50:05,940 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 04:50:05,940 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 04:50:05,959 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 04:50:05,975 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 04:50:05,975 INFO ]: Found error trace [2018-06-22 04:50:05,976 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:50:05,977 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:50:05,984 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-22 04:50:05,987 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:50:05,987 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:50:06,037 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:06,037 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:50:06,037 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:06,144 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:50:06,300 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:50:06,303 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 04:50:06,303 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 04:50:06,305 INFO ]: Interpolant automaton has 3 states [2018-06-22 04:50:06,320 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 04:50:06,321 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:50:06,324 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 04:50:06,430 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:50:06,430 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 04:50:06,431 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 04:50:06,432 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 04:50:06,432 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:50:06,442 INFO ]: With dead ends: 9 [2018-06-22 04:50:06,442 INFO ]: Without dead ends: 9 [2018-06-22 04:50:06,446 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:50:06,465 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 04:50:06,495 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 04:50:06,497 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 04:50:06,497 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 04:50:06,499 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 04:50:06,499 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:50:06,499 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 04:50:06,499 INFO ]: Interpolant automaton has 3 states. [2018-06-22 04:50:06,499 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 04:50:06,499 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 04:50:06,500 INFO ]: Found error trace [2018-06-22 04:50:06,500 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:50:06,500 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:50:06,500 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-22 04:50:06,500 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:50:06,500 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:50:06,501 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:06,501 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:50:06,501 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:06,617 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:50:06,880 WARN ]: Spent 105.00 ms on a formula simplification that was a NOOP. DAG size: 4 [2018-06-22 04:50:06,935 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:50:06,935 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:50:06,935 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:50:06,968 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:50:07,122 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:50:07,134 INFO ]: Computing forward predicates... [2018-06-22 04:50:07,400 WARN ]: Spent 128.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 04:50:07,711 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:50:07,746 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:50:07,746 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-22 04:50:07,747 INFO ]: Interpolant automaton has 6 states [2018-06-22 04:50:07,747 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 04:50:07,747 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 04:50:07,747 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-22 04:50:08,006 WARN ]: Spent 123.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-22 04:50:08,094 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:50:08,094 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 04:50:08,094 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 04:50:08,094 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-22 04:50:08,095 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:50:08,095 INFO ]: With dead ends: 11 [2018-06-22 04:50:08,095 INFO ]: Without dead ends: 11 [2018-06-22 04:50:08,096 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=20, Invalid=22, Unknown=0, NotChecked=0, Total=42 [2018-06-22 04:50:08,096 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 04:50:08,097 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 04:50:08,097 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 04:50:08,097 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 04:50:08,098 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-22 04:50:08,098 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:50:08,100 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 04:50:08,100 INFO ]: Interpolant automaton has 6 states. [2018-06-22 04:50:08,100 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 04:50:08,100 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 04:50:08,100 INFO ]: Found error trace [2018-06-22 04:50:08,100 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:50:08,101 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:50:08,101 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 2 times [2018-06-22 04:50:08,101 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:50:08,101 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:50:08,102 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:08,102 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:50:08,102 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:08,252 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:50:08,695 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-22 04:50:08,696 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:50:08,696 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:50:08,696 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-22 04:50:08,716 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-22 04:50:09,031 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 04:50:09,031 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:50:09,048 INFO ]: Computing forward predicates... [2018-06-22 04:50:09,281 WARN ]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 04:50:10,937 WARN ]: Spent 542.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 14 [2018-06-22 04:50:10,942 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:50:10,964 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:50:10,964 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-22 04:50:10,964 INFO ]: Interpolant automaton has 10 states [2018-06-22 04:50:10,964 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 04:50:10,964 INFO ]: CoverageRelationStatistics Valid=35, Invalid=55, Unknown=0, NotChecked=0, Total=90 [2018-06-22 04:50:10,965 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 10 states. [2018-06-22 04:50:11,147 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:50:11,147 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 04:50:11,147 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 04:50:11,147 INFO ]: Start accepts. Automaton has 10 states. Word has length 10 [2018-06-22 04:50:11,148 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:50:11,148 INFO ]: With dead ends: 12 [2018-06-22 04:50:11,148 INFO ]: Without dead ends: 12 [2018-06-22 04:50:11,148 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=52, Invalid=80, Unknown=0, NotChecked=0, Total=132 [2018-06-22 04:50:11,148 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 04:50:11,150 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 04:50:11,150 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 04:50:11,150 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 04:50:11,150 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-22 04:50:11,150 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:50:11,150 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 04:50:11,150 INFO ]: Interpolant automaton has 10 states. [2018-06-22 04:50:11,150 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 04:50:11,151 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 04:50:11,151 INFO ]: Found error trace [2018-06-22 04:50:11,151 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:50:11,151 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:50:11,151 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-22 04:50:11,151 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:50:11,151 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:50:11,152 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:11,152 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:50:11,152 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:11,325 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:50:11,668 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 4 [2018-06-22 04:50:11,753 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:50:11,753 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:50:11,753 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:50:11,761 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 04:50:11,995 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 04:50:11,995 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:50:12,015 INFO ]: Computing forward predicates... [2018-06-22 04:50:14,428 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 18 [2018-06-22 04:50:15,214 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:50:15,236 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:50:15,236 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-22 04:50:15,236 INFO ]: Interpolant automaton has 12 states [2018-06-22 04:50:15,236 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 04:50:15,237 INFO ]: CoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-06-22 04:50:15,237 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 12 states. [2018-06-22 04:50:15,488 WARN ]: Spent 179.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 18 [2018-06-22 04:50:15,530 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:50:15,530 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-22 04:50:15,530 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 04:50:15,530 INFO ]: Start accepts. Automaton has 12 states. Word has length 11 [2018-06-22 04:50:15,530 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:50:15,531 INFO ]: With dead ends: 13 [2018-06-22 04:50:15,531 INFO ]: Without dead ends: 13 [2018-06-22 04:50:15,531 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=80, Invalid=130, Unknown=0, NotChecked=0, Total=210 [2018-06-22 04:50:15,531 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 04:50:15,532 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 04:50:15,532 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 04:50:15,532 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-22 04:50:15,532 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-22 04:50:15,532 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:50:15,532 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-22 04:50:15,532 INFO ]: Interpolant automaton has 12 states. [2018-06-22 04:50:15,532 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-22 04:50:15,532 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-22 04:50:15,532 INFO ]: Found error trace [2018-06-22 04:50:15,532 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:50:15,532 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:50:15,533 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 4 times [2018-06-22 04:50:15,533 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:50:15,533 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:50:15,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:15,533 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:50:15,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:50:15,664 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:50:16,057 WARN ]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 4 [2018-06-22 04:50:16,160 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:50:16,160 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:50:16,160 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:50:16,171 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST Received shutdown request... [2018-06-22 04:51:20,405 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 04:51:20,405 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:51:20,421 INFO ]: Computing forward predicates... [2018-06-22 04:51:20,423 INFO ]: Timeout while computing interpolants [2018-06-22 04:51:20,623 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:51:20,623 WARN ]: Verification canceled [2018-06-22 04:51:20,628 WARN ]: Timeout [2018-06-22 04:51:20,628 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:51:20 BoogieIcfgContainer [2018-06-22 04:51:20,628 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 04:51:20,629 INFO ]: Toolchain (without parser) took 75464.99 ms. Allocated memory was 309.3 MB in the beginning and 1.1 GB in the end (delta: 818.9 MB). Free memory was 237.9 MB in the beginning and 550.7 MB in the end (delta: -312.7 MB). Peak memory consumption was 506.2 MB. Max. memory is 3.6 GB. [2018-06-22 04:51:20,630 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 275.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 04:51:20,632 INFO ]: ChcToBoogie took 97.38 ms. Allocated memory is still 309.3 MB. Free memory was 237.9 MB in the beginning and 235.0 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:51:20,633 INFO ]: Boogie Preprocessor took 77.77 ms. Allocated memory is still 309.3 MB. Free memory was 235.0 MB in the beginning and 233.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:51:20,633 INFO ]: RCFGBuilder took 492.14 ms. Allocated memory is still 309.3 MB. Free memory was 233.0 MB in the beginning and 198.7 MB in the end (delta: 34.2 MB). Peak memory consumption was 34.2 MB. Max. memory is 3.6 GB. [2018-06-22 04:51:20,633 INFO ]: TraceAbstraction took 74780.09 ms. Allocated memory was 309.3 MB in the beginning and 1.1 GB in the end (delta: 818.9 MB). Free memory was 198.7 MB in the beginning and 550.7 MB in the end (delta: -351.9 MB). Peak memory consumption was 467.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:51:20,635 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 275.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 97.38 ms. Allocated memory is still 309.3 MB. Free memory was 237.9 MB in the beginning and 235.0 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 77.77 ms. Allocated memory is still 309.3 MB. Free memory was 235.0 MB in the beginning and 233.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 492.14 ms. Allocated memory is still 309.3 MB. Free memory was 233.0 MB in the beginning and 198.7 MB in the end (delta: 34.2 MB). Peak memory consumption was 34.2 MB. Max. memory is 3.6 GB. * TraceAbstraction took 74780.09 ms. Allocated memory was 309.3 MB in the beginning and 1.1 GB in the end (delta: 818.9 MB). Free memory was 198.7 MB in the beginning and 550.7 MB in the end (delta: -351.9 MB). Peak memory consumption was 467.0 MB. 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 13 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1 quantified variables from 2 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 74.7s OverallTime, 5 OverallIterations, 5 TraceHistogramMax, 0.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 28 SDtfs, 3 SDslu, 73 SDs, 0 SdLazy, 36 SolverSat, 14 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 52 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82 ImplicationChecksByTransitivity, 2.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=13occurred in iteration=4, 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, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 0.9s SatisfiabilityAnalysisTime, 7.0s InterpolantComputationTime, 65 NumberOfCodeBlocks, 65 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 58 ConstructedInterpolants, 0 QuantifiedInterpolants, 2258 SizeOfPredicates, 8 NumberOfNonLiveVariables, 1605 ConjunctsInSsa, 67 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 0/34 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.1.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_04-51-20-648.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/token_ring.1.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_04-51-20-648.csv Completed graceful shutdown