java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifo.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 13:09:02,497 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 13:09:02,499 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 13:09:02,514 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 13:09:02,514 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 13:09:02,518 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 13:09:02,519 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 13:09:02,521 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 13:09:02,523 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 13:09:02,525 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 13:09:02,526 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 13:09:02,526 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 13:09:02,527 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 13:09:02,528 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 13:09:02,532 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 13:09:02,533 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 13:09:02,536 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 13:09:02,548 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 13:09:02,549 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 13:09:02,550 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 13:09:02,552 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 13:09:02,554 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 13:09:02,554 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 13:09:02,555 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 13:09:02,560 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 13:09:02,561 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 13:09:02,561 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 13:09:02,562 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 13:09:02,567 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 13:09:02,567 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 13:09:02,568 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 13:09:02,569 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 13:09:02,569 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 13:09:02,570 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 13:09:02,570 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 13:09:02,570 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 13:09:02,595 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 13:09:02,595 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 13:09:02,595 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 13:09:02,596 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 13:09:02,597 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 13:09:02,598 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 13:09:02,598 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 13:09:02,598 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 13:09:02,598 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 13:09:02,598 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 13:09:02,599 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 13:09:02,599 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 13:09:02,599 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:09:02,599 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 13:09:02,599 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 13:09:02,600 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 13:09:02,600 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 13:09:02,600 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 13:09:02,600 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 13:09:02,600 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 13:09:02,601 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 13:09:02,603 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 13:09:02,603 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 13:09:02,658 INFO ]: Repository-Root is: /tmp [2018-06-25 13:09:02,677 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 13:09:02,682 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 13:09:02,684 INFO ]: Initializing SmtParser... [2018-06-25 13:09:02,684 INFO ]: SmtParser initialized [2018-06-25 13:09:02,685 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifo.c.smt2 [2018-06-25 13:09:02,686 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-25 13:09:02,780 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifo.c.smt2 unknown [2018-06-25 13:09:03,340 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/lifo.c.smt2 [2018-06-25 13:09:03,346 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 13:09:03,352 INFO ]: Walking toolchain with 4 elements. [2018-06-25 13:09:03,352 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 13:09:03,352 INFO ]: Initializing ChcToBoogie... [2018-06-25 13:09:03,352 INFO ]: ChcToBoogie initialized [2018-06-25 13:09:03,356 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:09:03" (1/1) ... [2018-06-25 13:09:03,415 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03 Unit [2018-06-25 13:09:03,415 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 13:09:03,416 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 13:09:03,416 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 13:09:03,416 INFO ]: Boogie Preprocessor initialized [2018-06-25 13:09:03,437 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03" (1/1) ... [2018-06-25 13:09:03,437 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03" (1/1) ... [2018-06-25 13:09:03,459 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03" (1/1) ... [2018-06-25 13:09:03,459 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03" (1/1) ... [2018-06-25 13:09:03,471 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03" (1/1) ... [2018-06-25 13:09:03,473 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03" (1/1) ... [2018-06-25 13:09:03,477 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03" (1/1) ... [2018-06-25 13:09:03,482 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 13:09:03,483 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 13:09:03,483 INFO ]: Initializing RCFGBuilder... [2018-06-25 13:09:03,483 INFO ]: RCFGBuilder initialized [2018-06-25 13:09:03,484 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03" (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-25 13:09:03,508 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 13:09:03,508 INFO ]: Found specification of procedure gotoProc [2018-06-25 13:09:03,508 INFO ]: Found implementation of procedure gotoProc [2018-06-25 13:09:03,508 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 13:09:03,508 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 13:09:03,508 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-25 13:09:03,903 INFO ]: Using library mode [2018-06-25 13:09:03,903 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:09:03 BoogieIcfgContainer [2018-06-25 13:09:03,903 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 13:09:03,905 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 13:09:03,905 INFO ]: Initializing TraceAbstraction... [2018-06-25 13:09:03,908 INFO ]: TraceAbstraction initialized [2018-06-25 13:09:03,908 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:09:03" (1/3) ... [2018-06-25 13:09:03,909 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f253831 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:09:03, skipping insertion in model container [2018-06-25 13:09:03,909 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:09:03" (2/3) ... [2018-06-25 13:09:03,909 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f253831 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:09:03, skipping insertion in model container [2018-06-25 13:09:03,909 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:09:03" (3/3) ... [2018-06-25 13:09:03,911 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 13:09:03,921 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 13:09:03,929 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 13:09:03,987 INFO ]: Using default assertion order modulation [2018-06-25 13:09:03,987 INFO ]: Interprodecural is true [2018-06-25 13:09:03,987 INFO ]: Hoare is false [2018-06-25 13:09:03,988 INFO ]: Compute interpolants for FPandBP [2018-06-25 13:09:03,988 INFO ]: Backedges is TWOTRACK [2018-06-25 13:09:03,988 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 13:09:03,988 INFO ]: Difference is false [2018-06-25 13:09:03,988 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 13:09:03,988 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 13:09:04,006 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 13:09:04,021 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 13:09:04,021 INFO ]: Found error trace [2018-06-25 13:09:04,022 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:09:04,022 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:09:04,029 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 13:09:04,032 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:09:04,033 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:09:04,082 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:09:04,082 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:09:04,082 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:09:04,138 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:09:04,308 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:09:04,310 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 13:09:04,310 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 13:09:04,312 INFO ]: Interpolant automaton has 3 states [2018-06-25 13:09:04,322 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 13:09:04,322 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:09:04,324 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 13:09:04,458 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:09:04,458 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 13:09:04,459 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 13:09:04,460 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 13:09:04,461 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:09:04,473 INFO ]: With dead ends: 9 [2018-06-25 13:09:04,473 INFO ]: Without dead ends: 9 [2018-06-25 13:09:04,475 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:09:04,493 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 13:09:04,507 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 13:09:04,508 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 13:09:04,508 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 13:09:04,512 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 13:09:04,512 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:09:04,512 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 13:09:04,512 INFO ]: Interpolant automaton has 3 states. [2018-06-25 13:09:04,512 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 13:09:04,512 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 13:09:04,512 INFO ]: Found error trace [2018-06-25 13:09:04,512 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:09:04,513 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:09:04,513 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 13:09:04,513 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:09:04,513 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:09:04,514 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:09:04,514 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:09:04,514 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:09:04,687 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:09:04,925 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:09:04,925 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:09:04,925 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:09:04,937 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:09:05,052 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:09:05,062 INFO ]: Computing forward predicates... [2018-06-25 13:09:06,122 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:09:06,156 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:09:06,156 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 13:09:06,156 INFO ]: Interpolant automaton has 5 states [2018-06-25 13:09:06,157 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 13:09:06,157 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 13:09:06,157 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 13:09:06,343 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:09:06,343 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 13:09:06,344 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 13:09:06,344 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 13:09:06,345 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:09:06,345 INFO ]: With dead ends: 11 [2018-06-25 13:09:06,345 INFO ]: Without dead ends: 11 [2018-06-25 13:09:06,346 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:09:06,346 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 13:09:06,347 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 13:09:06,347 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 13:09:06,348 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 13:09:06,348 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-25 13:09:06,348 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:09:06,348 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 13:09:06,348 INFO ]: Interpolant automaton has 5 states. [2018-06-25 13:09:06,348 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 13:09:06,348 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 13:09:06,348 INFO ]: Found error trace [2018-06-25 13:09:06,348 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:09:06,348 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:09:06,349 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 2 times [2018-06-25 13:09:06,349 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:09:06,349 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:09:06,350 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:09:06,350 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:09:06,350 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:09:06,543 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:09:07,418 WARN ]: Spent 555.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 7 [2018-06-25 13:09:07,931 WARN ]: Spent 441.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 9 [2018-06-25 13:09:08,019 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:09:08,019 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:09:08,019 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-25 13:09:08,041 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:09:08,257 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:09:08,257 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:09:08,264 INFO ]: Computing forward predicates... [2018-06-25 13:09:13,037 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:09:13,047 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:09:13,112 WARN ]: expecting exponential blowup for input size 7 Received shutdown request... [2018-06-25 13:10:16,669 INFO ]: Timeout while computing interpolants [2018-06-25 13:10:16,870 WARN ]: Destroyed unattended storables created during the last iteration: 4 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:10:16,870 WARN ]: Verification canceled [2018-06-25 13:10:16,873 WARN ]: Timeout [2018-06-25 13:10:16,874 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:10:16 BoogieIcfgContainer [2018-06-25 13:10:16,874 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 13:10:16,874 INFO ]: Toolchain (without parser) took 73528.07 ms. Allocated memory was 301.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 230.1 MB in the beginning and 565.2 MB in the end (delta: -335.1 MB). Peak memory consumption was 881.2 MB. Max. memory is 3.6 GB. [2018-06-25 13:10:16,875 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 301.5 MB. Free memory is still 267.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:10:16,876 INFO ]: ChcToBoogie took 63.15 ms. Allocated memory is still 301.5 MB. Free memory was 229.1 MB in the beginning and 227.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:10:16,876 INFO ]: Boogie Preprocessor took 66.51 ms. Allocated memory is still 301.5 MB. Free memory was 227.1 MB in the beginning and 225.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:10:16,877 INFO ]: RCFGBuilder took 420.80 ms. Allocated memory is still 301.5 MB. Free memory was 225.1 MB in the beginning and 197.6 MB in the end (delta: 27.6 MB). Peak memory consumption was 27.6 MB. Max. memory is 3.6 GB. [2018-06-25 13:10:16,877 INFO ]: TraceAbstraction took 72969.20 ms. Allocated memory was 301.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 197.6 MB in the beginning and 565.2 MB in the end (delta: -367.6 MB). Peak memory consumption was 848.7 MB. Max. memory is 3.6 GB. [2018-06-25 13:10:16,882 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 301.5 MB. Free memory is still 267.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 63.15 ms. Allocated memory is still 301.5 MB. Free memory was 229.1 MB in the beginning and 227.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 66.51 ms. Allocated memory is still 301.5 MB. Free memory was 227.1 MB in the beginning and 225.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 420.80 ms. Allocated memory is still 301.5 MB. Free memory was 225.1 MB in the beginning and 197.6 MB in the end (delta: 27.6 MB). Peak memory consumption was 27.6 MB. Max. memory is 3.6 GB. * TraceAbstraction took 72969.20 ms. Allocated memory was 301.5 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 197.6 MB in the beginning and 565.2 MB in the end (delta: -367.6 MB). Peak memory consumption was 848.7 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 11 with TraceHistMax 3, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 7 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 72.9s OverallTime, 3 OverallIterations, 3 TraceHistogramMax, 0.3s 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.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 15 GetRequests, 9 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=11occurred in iteration=2, 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.0s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 1.4s InterpolantComputationTime, 23 NumberOfCodeBlocks, 23 NumberOfCodeBlocksAsserted, 3 NumberOfCheckSat, 20 ConstructedInterpolants, 0 QuantifiedInterpolants, 258 SizeOfPredicates, 7 NumberOfNonLiveVariables, 215 ConjunctsInSsa, 19 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/lifo.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_13-10-16-905.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/lifo.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_13-10-16-905.csv Completed graceful shutdown