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/toy-bug-1.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 14:35:17,993 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 14:35:17,995 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 14:35:18,029 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 14:35:18,029 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 14:35:18,030 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 14:35:18,031 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 14:35:18,041 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 14:35:18,043 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 14:35:18,044 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 14:35:18,045 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 14:35:18,045 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 14:35:18,049 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 14:35:18,050 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 14:35:18,051 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 14:35:18,055 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 14:35:18,057 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 14:35:18,069 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 14:35:18,071 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 14:35:18,072 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 14:35:18,073 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 14:35:18,076 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 14:35:18,076 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 14:35:18,076 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 14:35:18,081 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 14:35:18,082 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 14:35:18,083 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 14:35:18,084 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 14:35:18,085 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 14:35:18,085 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 14:35:18,086 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 14:35:18,086 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 14:35:18,086 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 14:35:18,087 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 14:35:18,088 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 14:35:18,088 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:35:18,104 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 14:35:18,105 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 14:35:18,105 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 14:35:18,105 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 14:35:18,106 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 14:35:18,107 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 14:35:18,107 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 14:35:18,107 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 14:35:18,107 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 14:35:18,107 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 14:35:18,108 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 14:35:18,108 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 14:35:18,108 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 14:35:18,108 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 14:35:18,108 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 14:35:18,109 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 14:35:18,109 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 14:35:18,110 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 14:35:18,110 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 14:35:18,112 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 14:35:18,112 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 14:35:18,174 INFO ]: Repository-Root is: /tmp [2018-06-22 14:35:18,192 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 14:35:18,199 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 14:35:18,201 INFO ]: Initializing SmtParser... [2018-06-22 14:35:18,201 INFO ]: SmtParser initialized [2018-06-22 14:35:18,203 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/toy-bug-1.smt2 [2018-06-22 14:35:18,204 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:35:18,300 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/toy-bug-1.smt2 unknown [2018-06-22 14:35:19,021 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/toy-bug-1.smt2 [2018-06-22 14:35:19,026 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 14:35:19,081 INFO ]: Walking toolchain with 4 elements. [2018-06-22 14:35:19,082 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 14:35:19,082 INFO ]: Initializing ChcToBoogie... [2018-06-22 14:35:19,082 INFO ]: ChcToBoogie initialized [2018-06-22 14:35:19,086 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:35:19" (1/1) ... [2018-06-22 14:35:19,175 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19 Unit [2018-06-22 14:35:19,176 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 14:35:19,176 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 14:35:19,176 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 14:35:19,176 INFO ]: Boogie Preprocessor initialized [2018-06-22 14:35:19,199 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19" (1/1) ... [2018-06-22 14:35:19,199 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19" (1/1) ... [2018-06-22 14:35:19,226 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19" (1/1) ... [2018-06-22 14:35:19,226 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19" (1/1) ... [2018-06-22 14:35:19,246 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19" (1/1) ... [2018-06-22 14:35:19,248 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19" (1/1) ... [2018-06-22 14:35:19,261 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19" (1/1) ... [2018-06-22 14:35:19,265 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 14:35:19,266 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 14:35:19,266 INFO ]: Initializing RCFGBuilder... [2018-06-22 14:35:19,266 INFO ]: RCFGBuilder initialized [2018-06-22 14:35:19,267 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19" (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:35:19,296 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 14:35:19,296 INFO ]: Found specification of procedure False [2018-06-22 14:35:19,296 INFO ]: Found implementation of procedure False [2018-06-22 14:35:19,296 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 14:35:19,296 INFO ]: Found specification of procedure state [2018-06-22 14:35:19,296 INFO ]: Found implementation of procedure state [2018-06-22 14:35:19,296 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 14:35:19,296 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 14:35:19,296 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:35:19,861 INFO ]: Using library mode [2018-06-22 14:35:19,862 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:35:19 BoogieIcfgContainer [2018-06-22 14:35:19,862 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 14:35:19,866 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 14:35:19,866 INFO ]: Initializing TraceAbstraction... [2018-06-22 14:35:19,881 INFO ]: TraceAbstraction initialized [2018-06-22 14:35:19,881 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 02:35:19" (1/3) ... [2018-06-22 14:35:19,882 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@184ca7d2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 02:35:19, skipping insertion in model container [2018-06-22 14:35:19,883 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 02:35:19" (2/3) ... [2018-06-22 14:35:19,883 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@184ca7d2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 02:35:19, skipping insertion in model container [2018-06-22 14:35:19,883 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 02:35:19" (3/3) ... [2018-06-22 14:35:19,890 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 14:35:19,913 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 14:35:19,935 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 14:35:20,003 INFO ]: Using default assertion order modulation [2018-06-22 14:35:20,004 INFO ]: Interprodecural is true [2018-06-22 14:35:20,004 INFO ]: Hoare is false [2018-06-22 14:35:20,004 INFO ]: Compute interpolants for FPandBP [2018-06-22 14:35:20,004 INFO ]: Backedges is TWOTRACK [2018-06-22 14:35:20,004 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 14:35:20,004 INFO ]: Difference is false [2018-06-22 14:35:20,004 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 14:35:20,004 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 14:35:20,029 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 14:35:20,040 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 14:35:20,040 INFO ]: Found error trace [2018-06-22 14:35:20,041 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:35:20,041 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:35:20,047 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 14:35:20,049 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:35:20,049 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:35:20,084 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:35:20,084 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:35:20,084 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:35:20,152 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:35:20,391 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:35:20,394 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 14:35:20,394 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 14:35:20,396 INFO ]: Interpolant automaton has 4 states [2018-06-22 14:35:20,413 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 14:35:20,413 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:35:20,416 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 14:35:20,553 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:35:20,553 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 14:35:20,554 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 14:35:20,555 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 14:35:20,556 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:35:20,573 INFO ]: With dead ends: 13 [2018-06-22 14:35:20,573 INFO ]: Without dead ends: 13 [2018-06-22 14:35:20,574 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 14:35:20,596 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 14:35:20,631 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 14:35:20,632 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 14:35:20,633 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 14:35:20,634 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 14:35:20,634 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:35:20,634 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 14:35:20,634 INFO ]: Interpolant automaton has 4 states. [2018-06-22 14:35:20,634 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 14:35:20,635 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 14:35:20,636 INFO ]: Found error trace [2018-06-22 14:35:20,636 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:35:20,636 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:35:20,636 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 14:35:20,636 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:35:20,636 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:35:20,637 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:35:20,637 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:35:20,637 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:35:20,795 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:35:21,247 WARN ]: Spent 206.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-22 14:35:21,651 WARN ]: Spent 140.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 14:35:21,654 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:35:21,654 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:35:21,654 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:35:21,691 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:35:21,842 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:35:21,859 INFO ]: Computing forward predicates... [2018-06-22 14:35:25,333 WARN ]: Spent 2.62 s on a formula simplification. DAG size of input: 45 DAG size of output: 32 [2018-06-22 14:35:25,661 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 14 [2018-06-22 14:35:25,693 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:35:25,730 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:35:25,730 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 14:35:25,730 INFO ]: Interpolant automaton has 8 states [2018-06-22 14:35:25,730 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 14:35:25,730 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-22 14:35:25,731 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 8 states. [2018-06-22 14:35:26,092 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 25 [2018-06-22 14:35:26,127 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:35:26,127 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 14:35:26,129 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 14:35:26,129 INFO ]: Start accepts. Automaton has 8 states. Word has length 13 [2018-06-22 14:35:26,129 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:35:26,129 INFO ]: With dead ends: 15 [2018-06-22 14:35:26,129 INFO ]: Without dead ends: 15 [2018-06-22 14:35:26,130 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-06-22 14:35:26,130 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 14:35:26,133 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 14:35:26,133 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 14:35:26,133 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 14:35:26,133 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 14:35:26,133 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:35:26,133 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 14:35:26,133 INFO ]: Interpolant automaton has 8 states. [2018-06-22 14:35:26,133 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 14:35:26,134 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 14:35:26,134 INFO ]: Found error trace [2018-06-22 14:35:26,134 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:35:26,134 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:35:26,134 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 14:35:26,134 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:35:26,134 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:35:26,148 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:35:26,148 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 14:35:26,148 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:35:26,234 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:35:26,739 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:35:26,739 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:35:26,739 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:35:26,754 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 14:35:26,866 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 14:35:26,866 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:35:26,888 INFO ]: Computing forward predicates... [2018-06-22 14:35:27,892 WARN ]: Spent 531.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 24 [2018-06-22 14:35:28,941 WARN ]: Spent 572.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 22 [2018-06-22 14:35:29,458 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:35:29,555 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:35:29,555 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2018-06-22 14:35:29,555 INFO ]: Interpolant automaton has 12 states [2018-06-22 14:35:29,555 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 14:35:29,556 INFO ]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-22 14:35:29,556 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 12 states. [2018-06-22 14:35:30,420 WARN ]: Spent 837.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 44 [2018-06-22 14:35:30,889 WARN ]: Spent 371.00 ms on a formula simplification. DAG size of input: 43 DAG size of output: 28 [2018-06-22 14:35:31,145 WARN ]: Spent 223.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 31 [2018-06-22 14:35:32,128 WARN ]: Spent 937.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 44 [2018-06-22 14:35:32,156 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:35:32,156 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 14:35:32,157 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 14:35:32,157 INFO ]: Start accepts. Automaton has 12 states. Word has length 17 [2018-06-22 14:35:32,157 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:35:32,157 INFO ]: With dead ends: 19 [2018-06-22 14:35:32,157 INFO ]: Without dead ends: 19 [2018-06-22 14:35:32,158 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=70, Invalid=170, Unknown=0, NotChecked=0, Total=240 [2018-06-22 14:35:32,158 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 14:35:32,161 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 14:35:32,161 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 14:35:32,162 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 14:35:32,162 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-22 14:35:32,162 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:35:32,162 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 14:35:32,162 INFO ]: Interpolant automaton has 12 states. [2018-06-22 14:35:32,162 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 14:35:32,163 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 14:35:32,163 INFO ]: Found error trace [2018-06-22 14:35:32,163 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:35:32,163 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:35:32,163 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 3 times [2018-06-22 14:35:32,163 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:35:32,163 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:35:32,164 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:35:32,164 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:35:32,164 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:35:32,311 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:35:32,824 WARN ]: Spent 155.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 14:35:33,823 WARN ]: Spent 948.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 19 [2018-06-22 14:35:34,129 WARN ]: Spent 236.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 22 [2018-06-22 14:35:34,297 WARN ]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-22 14:35:34,624 WARN ]: Spent 172.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 14:35:34,700 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:35:34,700 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:35:34,700 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) [2018-06-22 14:35:34,718 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:35:34,893 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 14:35:34,893 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:35:34,907 INFO ]: Computing forward predicates... [2018-06-22 14:35:36,170 WARN ]: Spent 934.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 31 Received shutdown request... [2018-06-22 14:36:34,350 INFO ]: Timeout while computing interpolants [2018-06-22 14:36:34,551 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 14:36:34,551 WARN ]: Verification canceled [2018-06-22 14:36:34,555 WARN ]: Timeout [2018-06-22 14:36:34,555 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 02:36:34 BoogieIcfgContainer [2018-06-22 14:36:34,555 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 14:36:34,556 INFO ]: Toolchain (without parser) took 75485.80 ms. Allocated memory was 305.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 238.1 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-22 14:36:34,557 INFO ]: SmtParser took 0.11 ms. Allocated memory is still 305.7 MB. Free memory is still 271.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 14:36:34,557 INFO ]: ChcToBoogie took 94.20 ms. Allocated memory is still 305.7 MB. Free memory was 238.1 MB in the beginning and 234.1 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:36:34,558 INFO ]: Boogie Preprocessor took 89.27 ms. Allocated memory is still 305.7 MB. Free memory was 234.1 MB in the beginning and 232.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:36:34,558 INFO ]: RCFGBuilder took 595.88 ms. Allocated memory is still 305.7 MB. Free memory was 232.1 MB in the beginning and 206.2 MB in the end (delta: 26.0 MB). Peak memory consumption was 26.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:36:34,558 INFO ]: TraceAbstraction took 74688.70 ms. Allocated memory was 305.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 206.2 MB in the beginning and 1.3 GB in the end (delta: -1.1 GB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-22 14:36:34,561 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.11 ms. Allocated memory is still 305.7 MB. Free memory is still 271.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 94.20 ms. Allocated memory is still 305.7 MB. Free memory was 238.1 MB in the beginning and 234.1 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 89.27 ms. Allocated memory is still 305.7 MB. Free memory was 234.1 MB in the beginning and 232.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 595.88 ms. Allocated memory is still 305.7 MB. Free memory was 232.1 MB in the beginning and 206.2 MB in the end (delta: 26.0 MB). Peak memory consumption was 26.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 74688.70 ms. Allocated memory was 305.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 206.2 MB in the beginning and 1.3 GB in the end (delta: -1.1 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 640 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 74.5s OverallTime, 4 OverallIterations, 5 TraceHistogramMax, 3.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 34 SDtfs, 19 SDslu, 83 SDs, 0 SdLazy, 64 SolverSat, 21 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 51 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 8.1s 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.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 8.0s InterpolantComputationTime, 69 NumberOfCodeBlocks, 69 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 64 ConstructedInterpolants, 0 QuantifiedInterpolants, 9648 SizeOfPredicates, 254 NumberOfNonLiveVariables, 364 ConjunctsInSsa, 38 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/toy-bug-1.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_14-36-34-581.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/toy-bug-1.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_14-36-34-581.csv Completed graceful shutdown