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/seq-sim.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 13:32:10,562 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 13:32:10,564 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 13:32:10,579 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 13:32:10,580 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 13:32:10,583 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 13:32:10,584 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 13:32:10,586 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 13:32:10,588 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 13:32:10,588 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 13:32:10,590 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 13:32:10,590 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 13:32:10,591 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 13:32:10,592 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 13:32:10,593 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 13:32:10,596 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 13:32:10,598 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 13:32:10,600 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 13:32:10,611 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 13:32:10,612 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 13:32:10,613 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 13:32:10,615 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 13:32:10,615 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 13:32:10,615 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 13:32:10,616 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 13:32:10,617 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 13:32:10,617 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 13:32:10,618 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 13:32:10,619 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 13:32:10,619 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 13:32:10,620 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 13:32:10,620 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 13:32:10,620 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 13:32:10,621 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 13:32:10,622 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 13:32:10,622 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:32:10,645 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 13:32:10,645 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 13:32:10,645 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 13:32:10,646 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 13:32:10,646 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 13:32:10,647 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 13:32:10,647 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 13:32:10,647 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 13:32:10,647 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 13:32:10,647 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 13:32:10,648 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 13:32:10,648 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 13:32:10,648 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:32:10,648 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 13:32:10,648 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 13:32:10,649 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 13:32:10,649 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 13:32:10,649 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 13:32:10,649 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 13:32:10,649 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 13:32:10,649 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 13:32:10,652 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 13:32:10,652 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 13:32:10,695 INFO ]: Repository-Root is: /tmp [2018-06-25 13:32:10,713 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 13:32:10,719 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 13:32:10,720 INFO ]: Initializing SmtParser... [2018-06-25 13:32:10,720 INFO ]: SmtParser initialized [2018-06-25 13:32:10,721 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq-sim.c.smt2 [2018-06-25 13:32:10,722 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:32:10,816 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq-sim.c.smt2 unknown [2018-06-25 13:32:11,081 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/seq-sim.c.smt2 [2018-06-25 13:32:11,086 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 13:32:11,093 INFO ]: Walking toolchain with 4 elements. [2018-06-25 13:32:11,093 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 13:32:11,093 INFO ]: Initializing ChcToBoogie... [2018-06-25 13:32:11,093 INFO ]: ChcToBoogie initialized [2018-06-25 13:32:11,096 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:32:11" (1/1) ... [2018-06-25 13:32:11,153 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11 Unit [2018-06-25 13:32:11,153 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 13:32:11,154 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 13:32:11,154 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 13:32:11,154 INFO ]: Boogie Preprocessor initialized [2018-06-25 13:32:11,169 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11" (1/1) ... [2018-06-25 13:32:11,169 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11" (1/1) ... [2018-06-25 13:32:11,175 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11" (1/1) ... [2018-06-25 13:32:11,175 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11" (1/1) ... [2018-06-25 13:32:11,180 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11" (1/1) ... [2018-06-25 13:32:11,182 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11" (1/1) ... [2018-06-25 13:32:11,184 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11" (1/1) ... [2018-06-25 13:32:11,186 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 13:32:11,186 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 13:32:11,186 INFO ]: Initializing RCFGBuilder... [2018-06-25 13:32:11,186 INFO ]: RCFGBuilder initialized [2018-06-25 13:32:11,193 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:32:11,216 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 13:32:11,216 INFO ]: Found specification of procedure gotoProc [2018-06-25 13:32:11,216 INFO ]: Found implementation of procedure gotoProc [2018-06-25 13:32:11,217 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 13:32:11,217 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 13:32:11,217 INFO ]: Found implementation of procedure Ultimate.START [2018-06-25 13:32:11,377 INFO ]: Using library mode [2018-06-25 13:32:11,377 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:32:11 BoogieIcfgContainer [2018-06-25 13:32:11,377 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 13:32:11,378 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 13:32:11,378 INFO ]: Initializing TraceAbstraction... [2018-06-25 13:32:11,384 INFO ]: TraceAbstraction initialized [2018-06-25 13:32:11,384 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:32:11" (1/3) ... [2018-06-25 13:32:11,385 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@161b0c12 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:32:11, skipping insertion in model container [2018-06-25 13:32:11,385 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:32:11" (2/3) ... [2018-06-25 13:32:11,385 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@161b0c12 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:32:11, skipping insertion in model container [2018-06-25 13:32:11,386 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:32:11" (3/3) ... [2018-06-25 13:32:11,387 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 13:32:11,394 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 13:32:11,402 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 13:32:11,438 INFO ]: Using default assertion order modulation [2018-06-25 13:32:11,439 INFO ]: Interprodecural is true [2018-06-25 13:32:11,439 INFO ]: Hoare is false [2018-06-25 13:32:11,439 INFO ]: Compute interpolants for FPandBP [2018-06-25 13:32:11,439 INFO ]: Backedges is TWOTRACK [2018-06-25 13:32:11,439 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 13:32:11,439 INFO ]: Difference is false [2018-06-25 13:32:11,439 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 13:32:11,439 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 13:32:11,454 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 13:32:11,466 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 13:32:11,466 INFO ]: Found error trace [2018-06-25 13:32:11,467 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:32:11,467 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:32:11,471 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 13:32:11,473 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:32:11,473 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:32:11,519 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:32:11,520 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:32:11,520 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:32:11,556 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:32:11,637 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:32:11,639 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 13:32:11,639 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 13:32:11,641 INFO ]: Interpolant automaton has 3 states [2018-06-25 13:32:11,656 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 13:32:11,657 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:32:11,660 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 13:32:11,746 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:32:11,746 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 13:32:11,747 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 13:32:11,748 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 13:32:11,748 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:32:11,766 INFO ]: With dead ends: 9 [2018-06-25 13:32:11,766 INFO ]: Without dead ends: 9 [2018-06-25 13:32:11,768 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:32:11,782 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 13:32:11,797 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 13:32:11,798 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 13:32:11,798 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 13:32:11,799 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 13:32:11,800 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:32:11,800 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 13:32:11,800 INFO ]: Interpolant automaton has 3 states. [2018-06-25 13:32:11,800 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 13:32:11,800 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 13:32:11,800 INFO ]: Found error trace [2018-06-25 13:32:11,800 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:32:11,800 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:32:11,800 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 13:32:11,801 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:32:11,801 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:32:11,801 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:32:11,802 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:32:11,802 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:32:11,850 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:32:12,029 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:32:12,029 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:32:12,029 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:32:12,042 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:32:12,090 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:32:12,097 INFO ]: Computing forward predicates... [2018-06-25 13:32:12,948 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:32:12,984 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:32:12,984 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 13:32:12,984 INFO ]: Interpolant automaton has 5 states [2018-06-25 13:32:12,984 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 13:32:12,985 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-25 13:32:12,985 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 13:32:13,213 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:32:13,214 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 13:32:13,214 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 13:32:13,214 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 13:32:13,215 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:32:13,215 INFO ]: With dead ends: 11 [2018-06-25 13:32:13,215 INFO ]: Without dead ends: 11 [2018-06-25 13:32:13,216 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:32:13,216 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 13:32:13,217 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 13:32:13,217 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 13:32:13,217 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 13:32:13,217 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-25 13:32:13,217 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:32:13,217 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 13:32:13,217 INFO ]: Interpolant automaton has 5 states. [2018-06-25 13:32:13,217 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 13:32:13,219 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 13:32:13,219 INFO ]: Found error trace [2018-06-25 13:32:13,219 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:32:13,219 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:32:13,219 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 2 times [2018-06-25 13:32:13,219 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:32:13,219 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:32:13,220 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:32:13,220 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:32:13,220 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:32:13,316 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:32:13,568 WARN ]: Spent 123.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-25 13:32:13,599 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:32:13,599 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:32:13,599 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:32:13,606 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:32:13,690 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:32:13,690 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:32:13,694 INFO ]: Computing forward predicates... [2018-06-25 13:32:15,963 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:32:15,995 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:32:15,995 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-25 13:32:15,995 INFO ]: Interpolant automaton has 7 states [2018-06-25 13:32:15,996 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 13:32:15,996 INFO ]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-06-25 13:32:15,996 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-25 13:32:16,282 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:32:16,282 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 13:32:16,282 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 13:32:16,282 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-25 13:32:16,283 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:32:16,283 INFO ]: With dead ends: 13 [2018-06-25 13:32:16,283 INFO ]: Without dead ends: 13 [2018-06-25 13:32:16,283 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2018-06-25 13:32:16,284 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 13:32:16,285 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 13:32:16,285 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 13:32:16,285 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 13:32:16,285 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 10 [2018-06-25 13:32:16,285 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:32:16,285 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 13:32:16,285 INFO ]: Interpolant automaton has 7 states. [2018-06-25 13:32:16,286 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 13:32:16,287 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 13:32:16,287 INFO ]: Found error trace [2018-06-25 13:32:16,287 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:32:16,287 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:32:16,287 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 3 times [2018-06-25 13:32:16,287 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:32:16,287 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:32:16,288 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:32:16,288 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:32:16,288 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:32:16,342 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:32:16,574 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:32:16,575 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:32:16,575 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-25 13:32:16,583 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 13:32:16,659 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-25 13:32:16,659 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:32:16,664 INFO ]: Computing forward predicates... [2018-06-25 13:32:43,769 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:43,802 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:43,810 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:43,818 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:43,830 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:43,849 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:44,081 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:44,094 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:44,107 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:44,199 WARN ]: expecting exponential blowup for input size 13 [2018-06-25 13:32:44,338 WARN ]: Simplifying disjunction of 11024 conjuctions. This might take some time... [2018-06-25 13:32:45,408 INFO ]: Simplified to disjunction of 704 conjuctions. [2018-06-25 13:32:45,442 WARN ]: expecting exponential blowup for input size 12 [2018-06-25 13:32:46,300 WARN ]: expecting exponential blowup for input size 8 [2018-06-25 13:32:46,485 WARN ]: expecting exponential blowup for input size 13 [2018-06-25 13:32:46,558 WARN ]: Simplifying disjunction of 12800 conjuctions. This might take some time... [2018-06-25 13:32:47,738 INFO ]: Simplified to disjunction of 704 conjuctions. [2018-06-25 13:32:48,524 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 13:32:48,589 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:48,617 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 13:32:48,899 WARN ]: expecting exponential blowup for input size 9 [2018-06-25 13:32:49,043 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:49,048 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:32:49,112 WARN ]: expecting exponential blowup for input size 8 Received shutdown request... [2018-06-25 13:33:19,582 INFO ]: Timeout while computing interpolants [2018-06-25 13:33:19,782 WARN ]: Destroyed unattended storables created during the last iteration: 5 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:33:19,782 WARN ]: Verification canceled [2018-06-25 13:33:19,786 WARN ]: Timeout [2018-06-25 13:33:19,786 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:33:19 BoogieIcfgContainer [2018-06-25 13:33:19,786 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 13:33:19,786 INFO ]: Toolchain (without parser) took 68700.01 ms. Allocated memory was 306.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 256.6 MB in the beginning and 476.6 MB in the end (delta: -220.1 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-25 13:33:19,788 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 306.2 MB. Free memory is still 268.7 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:33:19,789 INFO ]: ChcToBoogie took 60.28 ms. Allocated memory is still 306.2 MB. Free memory was 254.6 MB in the beginning and 252.6 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:33:19,789 INFO ]: Boogie Preprocessor took 31.99 ms. Allocated memory is still 306.2 MB. Free memory is still 252.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:33:19,789 INFO ]: RCFGBuilder took 191.35 ms. Allocated memory is still 306.2 MB. Free memory was 252.6 MB in the beginning and 240.6 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:33:19,791 INFO ]: TraceAbstraction took 68407.53 ms. Allocated memory was 306.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 240.6 MB in the beginning and 476.6 MB in the end (delta: -236.0 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-25 13:33:19,793 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 306.2 MB. Free memory is still 268.7 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 60.28 ms. Allocated memory is still 306.2 MB. Free memory was 254.6 MB in the beginning and 252.6 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 31.99 ms. Allocated memory is still 306.2 MB. Free memory is still 252.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 191.35 ms. Allocated memory is still 306.2 MB. Free memory was 252.6 MB in the beginning and 240.6 MB in the end (delta: 12.0 MB). Peak memory consumption was 12.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 68407.53 ms. Allocated memory was 306.2 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 240.6 MB in the beginning and 476.6 MB in the end (delta: -236.0 MB). Peak memory consumption was 1.4 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 13 with TraceHistMax 5, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while XnfDer was eliminating 84638 quantified variables from 16 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 68.3s OverallTime, 4 OverallIterations, 5 TraceHistogramMax, 0.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 21 SDtfs, 3 SDslu, 42 SDs, 0 SdLazy, 18 SolverSat, 9 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 33 GetRequests, 16 SyntacticMatches, 4 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=13occurred 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.2s SatisfiabilityAnalysisTime, 3.6s InterpolantComputationTime, 43 NumberOfCodeBlocks, 43 NumberOfCodeBlocksAsserted, 6 NumberOfCheckSat, 38 ConstructedInterpolants, 0 QuantifiedInterpolants, 902 SizeOfPredicates, 10 NumberOfNonLiveVariables, 266 ConjunctsInSsa, 42 ConjunctsInUnsatCore, 5 InterpolantComputations, 1 PerfectInterpolantSequences, 0/14 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/seq-sim.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_13-33-19-810.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/seq-sim.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_13-33-19-810.csv Completed graceful shutdown