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_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.3.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 14:31:43,862 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 14:31:43,864 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 14:31:43,877 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 14:31:43,878 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 14:31:43,879 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 14:31:43,882 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 14:31:43,884 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 14:31:43,886 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 14:31:43,886 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 14:31:43,888 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 14:31:43,888 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 14:31:43,889 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 14:31:43,890 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 14:31:43,890 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 14:31:43,894 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 14:31:43,895 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 14:31:43,905 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 14:31:43,906 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 14:31:43,907 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 14:31:43,908 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 14:31:43,914 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 14:31:43,914 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 14:31:43,914 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 14:31:43,916 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 14:31:43,917 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 14:31:43,917 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 14:31:43,918 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 14:31:43,919 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 14:31:43,919 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 14:31:43,919 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 14:31:43,922 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 14:31:43,922 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 14:31:43,923 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 14:31:43,923 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 14:31:43,924 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 14:31:43,943 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 14:31:43,943 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 14:31:43,944 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 14:31:43,944 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 14:31:43,945 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 14:31:43,945 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 14:31:43,945 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 14:31:43,945 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 14:31:43,946 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 14:31:43,949 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 14:31:43,949 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 14:31:43,949 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 14:31:43,949 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 14:31:43,949 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 14:31:43,950 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 14:31:43,950 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 14:31:43,950 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 14:31:43,950 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 14:31:43,950 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 14:31:43,952 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 14:31:43,953 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 14:31:43,999 INFO ]: Repository-Root is: /tmp [2018-06-22 14:31:44,013 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 14:31:44,017 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 14:31:44,018 INFO ]: Initializing SmtParser... [2018-06-22 14:31:44,018 INFO ]: SmtParser initialized [2018-06-22 14:31:44,019 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.3.smt2 [2018-06-22 14:31:44,021 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 14:31:44,104 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.3.smt2 unknown [2018-06-22 14:31:45,073 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/token_ring.3.smt2 [2018-06-22 14:31:45,077 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 14:31:45,092 INFO ]: Walking toolchain with 4 elements. [2018-06-22 14:31:45,093 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 14:31:45,093 INFO ]: Initializing ChcToBoogie... [2018-06-22 14:31:45,093 INFO ]: ChcToBoogie initialized [2018-06-22 14:31:45,099 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:31:45" (1/1) ... [2018-06-22 14:31:45,190 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45 Unit [2018-06-22 14:31:45,190 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 14:31:45,191 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 14:31:45,191 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 14:31:45,191 INFO ]: Boogie Preprocessor initialized [2018-06-22 14:31:45,214 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45" (1/1) ... [2018-06-22 14:31:45,214 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45" (1/1) ... [2018-06-22 14:31:45,243 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45" (1/1) ... [2018-06-22 14:31:45,244 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45" (1/1) ... [2018-06-22 14:31:45,279 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45" (1/1) ... [2018-06-22 14:31:45,280 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45" (1/1) ... [2018-06-22 14:31:45,294 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45" (1/1) ... [2018-06-22 14:31:45,302 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 14:31:45,302 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 14:31:45,303 INFO ]: Initializing RCFGBuilder... [2018-06-22 14:31:45,303 INFO ]: RCFGBuilder initialized [2018-06-22 14:31:45,312 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45" (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 14:31:45,325 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 14:31:45,325 INFO ]: Found specification of procedure False [2018-06-22 14:31:45,325 INFO ]: Found implementation of procedure False [2018-06-22 14:31:45,325 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 14:31:45,325 INFO ]: Found specification of procedure state [2018-06-22 14:31:45,325 INFO ]: Found implementation of procedure state [2018-06-22 14:31:45,325 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 14:31:45,325 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 14:31:45,325 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 14:31:45,969 INFO ]: Using library mode [2018-06-22 14:31:45,969 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:31:45 BoogieIcfgContainer [2018-06-22 14:31:45,969 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 14:31:45,971 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 14:31:45,971 INFO ]: Initializing TraceAbstraction... [2018-06-22 14:31:45,975 INFO ]: TraceAbstraction initialized [2018-06-22 14:31:45,975 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:31:45" (1/3) ... [2018-06-22 14:31:45,976 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4dacad14 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 02:31:45, skipping insertion in model container [2018-06-22 14:31:45,976 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:31:45" (2/3) ... [2018-06-22 14:31:45,976 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4dacad14 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 02:31:45, skipping insertion in model container [2018-06-22 14:31:45,977 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:31:45" (3/3) ... [2018-06-22 14:31:45,978 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 14:31:45,988 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 14:31:45,998 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 14:31:46,042 INFO ]: Using default assertion order modulation [2018-06-22 14:31:46,042 INFO ]: Interprodecural is true [2018-06-22 14:31:46,042 INFO ]: Hoare is false [2018-06-22 14:31:46,042 INFO ]: Compute interpolants for FPandBP [2018-06-22 14:31:46,043 INFO ]: Backedges is TWOTRACK [2018-06-22 14:31:46,043 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 14:31:46,043 INFO ]: Difference is false [2018-06-22 14:31:46,043 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 14:31:46,043 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 14:31:46,058 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 14:31:46,072 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 14:31:46,072 INFO ]: Found error trace [2018-06-22 14:31:46,073 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:31:46,073 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:31:46,079 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 14:31:46,081 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:31:46,081 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:31:46,130 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:31:46,130 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:31:46,130 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:31:46,201 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:31:46,427 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 14:31:46,429 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 14:31:46,429 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 14:31:46,431 INFO ]: Interpolant automaton has 4 states [2018-06-22 14:31:46,448 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 14:31:46,448 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:31:46,450 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 14:31:46,661 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:31:46,661 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 14:31:46,662 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 14:31:46,664 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 14:31:46,664 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:31:46,678 INFO ]: With dead ends: 13 [2018-06-22 14:31:46,678 INFO ]: Without dead ends: 13 [2018-06-22 14:31:46,679 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:31:46,699 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 14:31:46,726 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 14:31:46,727 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 14:31:46,727 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 14:31:46,729 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 14:31:46,729 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:31:46,729 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 14:31:46,729 INFO ]: Interpolant automaton has 4 states. [2018-06-22 14:31:46,729 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 14:31:46,730 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 14:31:46,730 INFO ]: Found error trace [2018-06-22 14:31:46,730 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:31:46,730 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:31:46,730 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 14:31:46,730 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:31:46,730 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:31:46,731 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:31:46,731 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:31:46,731 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:31:46,926 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:31:47,414 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:31:47,414 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:31:47,414 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 14:31:47,429 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:31:47,642 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:31:47,661 INFO ]: Computing forward predicates... [2018-06-22 14:31:49,298 WARN ]: Spent 742.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 15 [2018-06-22 14:31:49,423 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 14:31:49,444 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:31:49,444 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 14:31:49,445 INFO ]: Interpolant automaton has 9 states [2018-06-22 14:31:49,445 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 14:31:49,445 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-22 14:31:49,445 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 14:31:49,573 WARN ]: Spent 110.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 14:31:49,877 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:31:49,877 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 14:31:49,878 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 14:31:49,878 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 14:31:49,878 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:31:49,878 INFO ]: With dead ends: 15 [2018-06-22 14:31:49,878 INFO ]: Without dead ends: 15 [2018-06-22 14:31:49,879 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2018-06-22 14:31:49,879 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 14:31:49,882 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 14:31:49,882 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 14:31:49,882 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 14:31:49,882 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 14:31:49,882 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:31:49,882 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 14:31:49,882 INFO ]: Interpolant automaton has 9 states. [2018-06-22 14:31:49,883 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 14:31:49,883 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 14:31:49,883 INFO ]: Found error trace [2018-06-22 14:31:49,883 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:31:49,883 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:31:49,883 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 14:31:49,883 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:31:49,883 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:31:49,884 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:31:49,884 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:31:49,884 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:31:50,029 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:31:50,600 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:31:50,600 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:31:50,601 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:31:50,608 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 14:31:50,834 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 14:31:50,834 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:31:50,848 INFO ]: Computing forward predicates... [2018-06-22 14:31:51,901 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 24 [2018-06-22 14:31:52,032 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 14:31:52,059 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:31:52,059 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-22 14:31:52,059 INFO ]: Interpolant automaton has 14 states [2018-06-22 14:31:52,060 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 14:31:52,060 INFO ]: CoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2018-06-22 14:31:52,060 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 14 states. [2018-06-22 14:31:52,397 WARN ]: Spent 236.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 35 [2018-06-22 14:31:52,861 WARN ]: Spent 232.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 34 [2018-06-22 14:31:52,901 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:31:52,902 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 14:31:52,904 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 14:31:52,904 INFO ]: Start accepts. Automaton has 14 states. Word has length 17 [2018-06-22 14:31:52,904 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:31:52,905 INFO ]: With dead ends: 19 [2018-06-22 14:31:52,905 INFO ]: Without dead ends: 19 [2018-06-22 14:31:52,905 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=79, Invalid=263, Unknown=0, NotChecked=0, Total=342 [2018-06-22 14:31:52,905 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 14:31:52,908 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 14:31:52,908 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 14:31:52,909 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 14:31:52,909 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-22 14:31:52,909 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:31:52,909 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 14:31:52,909 INFO ]: Interpolant automaton has 14 states. [2018-06-22 14:31:52,909 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 14:31:52,910 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 14:31:52,910 INFO ]: Found error trace [2018-06-22 14:31:52,910 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:31:52,910 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:31:52,910 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 3 times [2018-06-22 14:31:52,910 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:31:52,910 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:31:52,911 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:31:52,911 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:31:52,911 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:31:53,236 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:31:53,782 WARN ]: Spent 132.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 14:31:54,043 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 14:31:54,043 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:31:54,043 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 14:31:54,060 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 14:31:54,433 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 14:31:54,433 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:31:54,456 INFO ]: Computing forward predicates... [2018-06-22 14:31:54,979 WARN ]: Spent 234.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 31 [2018-06-22 14:32:40,914 WARN ]: Simplifying disjunction of 7680 conjuctions. This might take some time... [2018-06-22 14:32:46,689 INFO ]: Simplified to disjunction of 7680 conjuctions. [2018-06-22 14:32:46,751 WARN ]: Simplifying disjunction of 7680 conjuctions. This might take some time... Received shutdown request... [2018-06-22 14:32:52,034 INFO ]: Timeout while computing interpolants [2018-06-22 14:32:52,235 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:32:52,235 WARN ]: Verification canceled [2018-06-22 14:32:52,239 WARN ]: Timeout [2018-06-22 14:32:52,240 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 02:32:52 BoogieIcfgContainer [2018-06-22 14:32:52,240 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 14:32:52,241 INFO ]: Toolchain (without parser) took 67162.61 ms. Allocated memory was 334.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 285.5 MB in the beginning and 1.2 GB in the end (delta: -925.7 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 14:32:52,241 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 14:32:52,242 INFO ]: ChcToBoogie took 97.96 ms. Allocated memory is still 334.5 MB. Free memory was 285.5 MB in the beginning and 282.3 MB in the end (delta: 3.3 MB). Peak memory consumption was 3.3 MB. Max. memory is 3.6 GB. [2018-06-22 14:32:52,242 INFO ]: Boogie Preprocessor took 110.86 ms. Allocated memory is still 334.5 MB. Free memory was 282.3 MB in the beginning and 279.0 MB in the end (delta: 3.3 MB). Peak memory consumption was 3.3 MB. Max. memory is 3.6 GB. [2018-06-22 14:32:52,242 INFO ]: RCFGBuilder took 666.83 ms. Allocated memory is still 334.5 MB. Free memory was 279.0 MB in the beginning and 188.7 MB in the end (delta: 90.3 MB). Peak memory consumption was 90.3 MB. Max. memory is 3.6 GB. [2018-06-22 14:32:52,247 INFO ]: TraceAbstraction took 66268.83 ms. Allocated memory was 334.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 188.7 MB in the beginning and 1.2 GB in the end (delta: -1.0 GB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 14:32:52,252 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 97.96 ms. Allocated memory is still 334.5 MB. Free memory was 285.5 MB in the beginning and 282.3 MB in the end (delta: 3.3 MB). Peak memory consumption was 3.3 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 110.86 ms. Allocated memory is still 334.5 MB. Free memory was 282.3 MB in the beginning and 279.0 MB in the end (delta: 3.3 MB). Peak memory consumption was 3.3 MB. Max. memory is 3.6 GB. * RCFGBuilder took 666.83 ms. Allocated memory is still 334.5 MB. Free memory was 279.0 MB in the beginning and 188.7 MB in the end (delta: 90.3 MB). Peak memory consumption was 90.3 MB. Max. memory is 3.6 GB. * TraceAbstraction took 66268.83 ms. Allocated memory was 334.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 188.7 MB in the beginning and 1.2 GB in the end (delta: -1.0 GB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 26 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was XNF transformer was simplifying 7680 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 66.2s OverallTime, 4 OverallIterations, 5 TraceHistogramMax, 1.5s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 33 SDtfs, 27 SDslu, 97 SDs, 0 SdLazy, 71 SolverSat, 34 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 53 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 3.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=19occurred 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.1s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 4.2s InterpolantComputationTime, 69 NumberOfCodeBlocks, 69 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 64 ConstructedInterpolants, 0 QuantifiedInterpolants, 4576 SizeOfPredicates, 809 NumberOfNonLiveVariables, 1234 ConjunctsInSsa, 30 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 8/26 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.3.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_14-32-52-261.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/token_ring.3.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_14-32-52-261.csv Completed graceful shutdown