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.12.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 04:49:04,905 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 04:49:04,907 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 04:49:04,918 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 04:49:04,919 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 04:49:04,919 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 04:49:04,921 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 04:49:04,925 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 04:49:04,926 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 04:49:04,928 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 04:49:04,929 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 04:49:04,929 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 04:49:04,930 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 04:49:04,931 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 04:49:04,934 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 04:49:04,935 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 04:49:04,944 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 04:49:04,946 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 04:49:04,952 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 04:49:04,953 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 04:49:04,954 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 04:49:04,956 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 04:49:04,957 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 04:49:04,957 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 04:49:04,958 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 04:49:04,958 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 04:49:04,964 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 04:49:04,964 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 04:49:04,968 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 04:49:04,968 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 04:49:04,969 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 04:49:04,970 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 04:49:04,970 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 04:49:04,971 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 04:49:04,971 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 04:49:04,971 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:49:04,999 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 04:49:04,999 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 04:49:04,999 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 04:49:05,000 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 04:49:05,004 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 04:49:05,005 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 04:49:05,005 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 04:49:05,005 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 04:49:05,005 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:49:05,005 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 04:49:05,006 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 04:49:05,006 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 04:49:05,006 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 04:49:05,006 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 04:49:05,006 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 04:49:05,007 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 04:49:05,007 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 04:49:05,009 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 04:49:05,009 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 04:49:05,056 INFO ]: Repository-Root is: /tmp [2018-06-22 04:49:05,074 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 04:49:05,081 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 04:49:05,082 INFO ]: Initializing SmtParser... [2018-06-22 04:49:05,082 INFO ]: SmtParser initialized [2018-06-22 04:49:05,083 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.12.smt2 [2018-06-22 04:49:05,084 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:49:05,178 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.12.smt2 unknown [2018-06-22 04:49:14,239 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.12.smt2 [2018-06-22 04:49:14,244 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 04:49:14,251 INFO ]: Walking toolchain with 4 elements. [2018-06-22 04:49:14,252 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 04:49:14,252 INFO ]: Initializing ChcToBoogie... [2018-06-22 04:49:14,252 INFO ]: ChcToBoogie initialized [2018-06-22 04:49:14,255 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:49:14" (1/1) ... [2018-06-22 04:49:14,421 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14 Unit [2018-06-22 04:49:14,421 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 04:49:14,422 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 04:49:14,422 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 04:49:14,422 INFO ]: Boogie Preprocessor initialized [2018-06-22 04:49:14,443 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14" (1/1) ... [2018-06-22 04:49:14,443 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14" (1/1) ... [2018-06-22 04:49:14,521 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14" (1/1) ... [2018-06-22 04:49:14,521 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14" (1/1) ... [2018-06-22 04:49:14,590 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14" (1/1) ... [2018-06-22 04:49:14,592 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14" (1/1) ... [2018-06-22 04:49:14,629 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14" (1/1) ... [2018-06-22 04:49:14,673 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 04:49:14,674 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 04:49:14,674 INFO ]: Initializing RCFGBuilder... [2018-06-22 04:49:14,674 INFO ]: RCFGBuilder initialized [2018-06-22 04:49:14,677 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:49:14,690 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 04:49:14,690 INFO ]: Found specification of procedure gotoProc [2018-06-22 04:49:14,690 INFO ]: Found implementation of procedure gotoProc [2018-06-22 04:49:14,690 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 04:49:14,690 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 04:49:14,690 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 04:49:22,381 INFO ]: Using library mode [2018-06-22 04:49:22,382 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:49:22 BoogieIcfgContainer [2018-06-22 04:49:22,382 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 04:49:22,383 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 04:49:22,383 INFO ]: Initializing TraceAbstraction... [2018-06-22 04:49:22,386 INFO ]: TraceAbstraction initialized [2018-06-22 04:49:22,386 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:49:14" (1/3) ... [2018-06-22 04:49:22,387 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1718280 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:49:22, skipping insertion in model container [2018-06-22 04:49:22,387 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:49:14" (2/3) ... [2018-06-22 04:49:22,387 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1718280 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:49:22, skipping insertion in model container [2018-06-22 04:49:22,387 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:49:22" (3/3) ... [2018-06-22 04:49:22,389 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 04:49:22,398 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 04:49:22,405 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 04:49:22,445 INFO ]: Using default assertion order modulation [2018-06-22 04:49:22,446 INFO ]: Interprodecural is true [2018-06-22 04:49:22,446 INFO ]: Hoare is false [2018-06-22 04:49:22,446 INFO ]: Compute interpolants for FPandBP [2018-06-22 04:49:22,446 INFO ]: Backedges is TWOTRACK [2018-06-22 04:49:22,446 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 04:49:22,446 INFO ]: Difference is false [2018-06-22 04:49:22,446 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 04:49:22,446 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 04:49:22,460 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 04:49:22,471 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 04:49:22,471 INFO ]: Found error trace [2018-06-22 04:49:22,472 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:49:22,472 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:49:22,478 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 04:49:22,479 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:49:22,480 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:49:22,516 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:49:22,516 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:49:22,516 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:49:22,830 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:49:23,080 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:49:23,084 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 04:49:23,084 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 04:49:23,086 INFO ]: Interpolant automaton has 3 states [2018-06-22 04:49:23,103 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 04:49:23,103 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:49:23,106 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 04:49:23,479 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:49:23,479 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 04:49:23,480 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 04:49:23,481 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 04:49:23,481 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:49:23,488 INFO ]: With dead ends: 9 [2018-06-22 04:49:23,488 INFO ]: Without dead ends: 9 [2018-06-22 04:49:23,489 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:49:23,502 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 04:49:23,523 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 04:49:23,524 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 04:49:23,525 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 04:49:23,526 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 04:49:23,526 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:49:23,526 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 04:49:23,526 INFO ]: Interpolant automaton has 3 states. [2018-06-22 04:49:23,526 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 04:49:23,527 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 04:49:23,527 INFO ]: Found error trace [2018-06-22 04:49:23,527 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:49:23,527 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:49:23,527 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 04:49:23,527 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:49:23,527 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:49:23,528 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:49:23,528 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:49:23,528 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:49:24,631 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:49:26,160 WARN ]: Spent 160.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 04:49:26,282 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:49:26,283 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:49:26,283 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:49:26,296 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:49:27,440 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:49:27,533 INFO ]: Computing forward predicates... [2018-06-22 04:49:30,227 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:49:30,260 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:49:30,260 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 04:49:30,261 INFO ]: Interpolant automaton has 5 states [2018-06-22 04:49:30,261 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 04:49:30,261 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 04:49:30,261 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 04:49:30,792 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:49:30,792 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-22 04:49:30,792 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 04:49:30,792 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 04:49:30,792 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:49:30,793 INFO ]: With dead ends: 10 [2018-06-22 04:49:30,793 INFO ]: Without dead ends: 10 [2018-06-22 04:49:30,793 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 04:49:30,793 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-22 04:49:30,794 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-22 04:49:30,795 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-22 04:49:30,795 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-22 04:49:30,795 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-22 04:49:30,795 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:49:30,795 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-22 04:49:30,795 INFO ]: Interpolant automaton has 5 states. [2018-06-22 04:49:30,795 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-22 04:49:30,795 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 04:49:30,795 INFO ]: Found error trace [2018-06-22 04:49:30,795 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:49:30,796 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:49:30,796 INFO ]: Analyzing trace with hash -2043975570, now seen corresponding path program 2 times [2018-06-22 04:49:30,796 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:49:30,796 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:49:30,796 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:49:30,796 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:49:30,796 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:49:32,239 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:49:34,488 WARN ]: Spent 162.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 04:49:34,802 WARN ]: Spent 168.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 04:49:34,803 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:49:34,803 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:49:34,803 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:49:34,819 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:49:36,453 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 04:49:36,453 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:49:36,653 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 04:50:00,828 INFO ]: Timeout while computing interpolants [2018-06-22 04:50:01,029 WARN ]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:50:01,029 WARN ]: Verification canceled [2018-06-22 04:50:01,033 WARN ]: Timeout [2018-06-22 04:50:01,033 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:50:01 BoogieIcfgContainer [2018-06-22 04:50:01,033 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 04:50:01,034 INFO ]: Toolchain (without parser) took 46789.57 ms. Allocated memory was 1.1 GB in the beginning and 1.6 GB in the end (delta: 562.0 MB). Free memory was 924.9 MB in the beginning and 995.9 MB in the end (delta: -71.1 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 04:50:01,035 INFO ]: SmtParser took 0.09 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-22 04:50:01,035 INFO ]: ChcToBoogie took 169.42 ms. Allocated memory is still 1.1 GB. Free memory was 924.9 MB in the beginning and 908.2 MB in the end (delta: 16.6 MB). Peak memory consumption was 16.6 MB. Max. memory is 3.6 GB. [2018-06-22 04:50:01,035 INFO ]: Boogie Preprocessor took 251.99 ms. Allocated memory is still 1.1 GB. Free memory was 908.2 MB in the beginning and 891.3 MB in the end (delta: 16.9 MB). Peak memory consumption was 16.9 MB. Max. memory is 3.6 GB. [2018-06-22 04:50:01,035 INFO ]: RCFGBuilder took 7707.93 ms. Allocated memory was 1.1 GB in the beginning and 1.6 GB in the end (delta: 499.1 MB). Free memory was 891.3 MB in the beginning and 1.1 GB in the end (delta: -254.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 04:50:01,036 INFO ]: TraceAbstraction took 38650.09 ms. Allocated memory was 1.6 GB in the beginning and 1.6 GB in the end (delta: 62.9 MB). Free memory was 1.1 GB in the beginning and 995.9 MB in the end (delta: 150.3 MB). Peak memory consumption was 1.0 GB. Max. memory is 3.6 GB. [2018-06-22 04:50:01,038 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.09 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 169.42 ms. Allocated memory is still 1.1 GB. Free memory was 924.9 MB in the beginning and 908.2 MB in the end (delta: 16.6 MB). Peak memory consumption was 16.6 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 251.99 ms. Allocated memory is still 1.1 GB. Free memory was 908.2 MB in the beginning and 891.3 MB in the end (delta: 16.9 MB). Peak memory consumption was 16.9 MB. Max. memory is 3.6 GB. * RCFGBuilder took 7707.93 ms. Allocated memory was 1.1 GB in the beginning and 1.6 GB in the end (delta: 499.1 MB). Free memory was 891.3 MB in the beginning and 1.1 GB in the end (delta: -254.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. * TraceAbstraction took 38650.09 ms. Allocated memory was 1.6 GB in the beginning and 1.6 GB in the end (delta: 62.9 MB). Free memory was 1.1 GB in the beginning and 995.9 MB in the end (delta: 150.3 MB). Peak memory consumption was 1.0 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 10 with TraceHistMax 2, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 1487 quantified variables from 8 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 38.5s OverallTime, 3 OverallIterations, 2 TraceHistogramMax, 0.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 14 SDtfs, 0 SDslu, 15 SDs, 0 SdLazy, 9 SolverSat, 2 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 15 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=10occurred in iteration=0, 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, 2 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.4s SsaConstructionTime, 2.0s SatisfiabilityAnalysisTime, 4.6s InterpolantComputationTime, 23 NumberOfCodeBlocks, 23 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 20 ConstructedInterpolants, 0 QuantifiedInterpolants, 274 SizeOfPredicates, 0 NumberOfNonLiveVariables, 4188 ConjunctsInSsa, 15 ConjunctsInUnsatCore, 3 InterpolantComputations, 1 PerfectInterpolantSequences, 0/2 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.12.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_04-50-01-049.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/token_ring.12.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_04-50-01-049.csv Completed graceful shutdown