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/cav12/toy.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 12:33:24,691 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 12:33:24,693 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 12:33:24,708 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 12:33:24,709 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 12:33:24,710 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 12:33:24,714 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 12:33:24,715 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 12:33:24,717 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 12:33:24,719 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 12:33:24,720 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 12:33:24,720 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 12:33:24,723 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 12:33:24,725 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 12:33:24,725 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 12:33:24,726 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 12:33:24,730 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 12:33:24,732 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 12:33:24,746 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 12:33:24,747 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 12:33:24,748 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 12:33:24,750 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 12:33:24,750 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 12:33:24,750 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 12:33:24,751 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 12:33:24,752 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 12:33:24,753 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 12:33:24,753 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 12:33:24,760 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 12:33:24,764 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 12:33:24,765 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 12:33:24,766 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 12:33:24,766 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 12:33:24,767 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 12:33:24,768 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 12:33:24,768 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 12:33:24,785 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 12:33:24,785 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 12:33:24,788 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 12:33:24,788 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 12:33:24,789 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 12:33:24,789 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 12:33:24,789 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 12:33:24,790 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 12:33:24,790 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 12:33:24,790 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 12:33:24,790 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 12:33:24,790 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 12:33:24,791 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:33:24,791 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 12:33:24,791 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 12:33:24,791 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 12:33:24,791 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 12:33:24,792 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 12:33:24,793 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 12:33:24,793 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 12:33:24,793 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 12:33:24,794 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 12:33:24,795 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 12:33:24,843 INFO ]: Repository-Root is: /tmp [2018-06-25 12:33:24,860 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 12:33:24,864 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 12:33:24,866 INFO ]: Initializing SmtParser... [2018-06-25 12:33:24,866 INFO ]: SmtParser initialized [2018-06-25 12:33:24,866 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/toy.smt2 [2018-06-25 12:33:24,868 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 12:33:24,958 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/toy.smt2 unknown [2018-06-25 12:33:25,429 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/toy.smt2 [2018-06-25 12:33:25,436 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 12:33:25,442 INFO ]: Walking toolchain with 4 elements. [2018-06-25 12:33:25,443 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 12:33:25,443 INFO ]: Initializing ChcToBoogie... [2018-06-25 12:33:25,443 INFO ]: ChcToBoogie initialized [2018-06-25 12:33:25,446 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:33:25" (1/1) ... [2018-06-25 12:33:25,527 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25 Unit [2018-06-25 12:33:25,527 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 12:33:25,528 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 12:33:25,528 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 12:33:25,528 INFO ]: Boogie Preprocessor initialized [2018-06-25 12:33:25,542 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25" (1/1) ... [2018-06-25 12:33:25,543 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25" (1/1) ... [2018-06-25 12:33:25,556 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25" (1/1) ... [2018-06-25 12:33:25,557 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25" (1/1) ... [2018-06-25 12:33:25,571 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25" (1/1) ... [2018-06-25 12:33:25,572 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25" (1/1) ... [2018-06-25 12:33:25,577 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25" (1/1) ... [2018-06-25 12:33:25,581 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 12:33:25,582 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 12:33:25,582 INFO ]: Initializing RCFGBuilder... [2018-06-25 12:33:25,582 INFO ]: RCFGBuilder initialized [2018-06-25 12:33:25,583 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25" (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 12:33:25,592 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 12:33:25,592 INFO ]: Found specification of procedure gotoProc [2018-06-25 12:33:25,592 INFO ]: Found implementation of procedure gotoProc [2018-06-25 12:33:25,592 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 12:33:25,592 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 12:33:25,593 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 12:33:26,055 INFO ]: Using library mode [2018-06-25 12:33:26,055 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:33:26 BoogieIcfgContainer [2018-06-25 12:33:26,055 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 12:33:26,057 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 12:33:26,057 INFO ]: Initializing TraceAbstraction... [2018-06-25 12:33:26,060 INFO ]: TraceAbstraction initialized [2018-06-25 12:33:26,060 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:33:25" (1/3) ... [2018-06-25 12:33:26,061 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41f02712 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 12:33:26, skipping insertion in model container [2018-06-25 12:33:26,061 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:33:25" (2/3) ... [2018-06-25 12:33:26,062 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41f02712 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 12:33:26, skipping insertion in model container [2018-06-25 12:33:26,062 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:33:26" (3/3) ... [2018-06-25 12:33:26,064 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 12:33:26,074 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 12:33:26,084 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 12:33:26,128 INFO ]: Using default assertion order modulation [2018-06-25 12:33:26,129 INFO ]: Interprodecural is true [2018-06-25 12:33:26,129 INFO ]: Hoare is false [2018-06-25 12:33:26,129 INFO ]: Compute interpolants for FPandBP [2018-06-25 12:33:26,129 INFO ]: Backedges is TWOTRACK [2018-06-25 12:33:26,129 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 12:33:26,129 INFO ]: Difference is false [2018-06-25 12:33:26,129 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 12:33:26,129 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 12:33:26,140 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 12:33:26,151 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 12:33:26,151 INFO ]: Found error trace [2018-06-25 12:33:26,152 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:33:26,152 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:33:26,157 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 12:33:26,159 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:33:26,159 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:33:26,199 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:26,200 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:33:26,200 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:26,265 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:33:26,354 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:33:26,356 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 12:33:26,356 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 12:33:26,359 INFO ]: Interpolant automaton has 3 states [2018-06-25 12:33:26,369 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 12:33:26,369 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:33:26,372 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 12:33:26,451 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:33:26,451 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 12:33:26,454 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 12:33:26,455 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 12:33:26,455 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:33:26,466 INFO ]: With dead ends: 9 [2018-06-25 12:33:26,466 INFO ]: Without dead ends: 9 [2018-06-25 12:33:26,468 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 12:33:26,480 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 12:33:26,518 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 12:33:26,519 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 12:33:26,520 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 12:33:26,521 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 12:33:26,521 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:33:26,521 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 12:33:26,521 INFO ]: Interpolant automaton has 3 states. [2018-06-25 12:33:26,521 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 12:33:26,522 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 12:33:26,522 INFO ]: Found error trace [2018-06-25 12:33:26,522 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:33:26,522 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:33:26,522 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 12:33:26,522 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:33:26,522 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:33:26,524 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:26,524 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:33:26,524 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:26,685 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:33:26,928 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:33:26,928 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:33:26,928 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 12:33:26,939 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:33:27,053 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:33:27,064 INFO ]: Computing forward predicates... [2018-06-25 12:33:27,466 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:33:27,487 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:33:27,487 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-25 12:33:27,488 INFO ]: Interpolant automaton has 6 states [2018-06-25 12:33:27,488 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 12:33:27,488 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:33:27,488 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-25 12:33:27,771 WARN ]: Spent 210.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 7 [2018-06-25 12:33:28,146 WARN ]: Spent 258.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-25 12:33:28,244 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:33:28,244 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 12:33:28,244 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-25 12:33:28,245 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-25 12:33:28,245 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:33:28,245 INFO ]: With dead ends: 11 [2018-06-25 12:33:28,245 INFO ]: Without dead ends: 11 [2018-06-25 12:33:28,246 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2018-06-25 12:33:28,246 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 12:33:28,247 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 12:33:28,247 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 12:33:28,248 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 12:33:28,251 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-25 12:33:28,251 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:33:28,251 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 12:33:28,251 INFO ]: Interpolant automaton has 6 states. [2018-06-25 12:33:28,252 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 12:33:28,252 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 12:33:28,252 INFO ]: Found error trace [2018-06-25 12:33:28,252 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:33:28,252 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:33:28,252 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 2 times [2018-06-25 12:33:28,252 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:33:28,252 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:33:28,253 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:28,253 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:33:28,253 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:28,423 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:33:28,947 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:33:28,947 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:33:28,947 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 12:33:28,957 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:33:29,089 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:33:29,089 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:33:29,102 INFO ]: Computing forward predicates... [2018-06-25 12:33:30,176 WARN ]: Spent 429.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 12 [2018-06-25 12:33:30,663 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 16 [2018-06-25 12:33:30,675 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:33:30,695 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:33:30,696 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-25 12:33:30,696 INFO ]: Interpolant automaton has 10 states [2018-06-25 12:33:30,696 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-25 12:33:30,696 INFO ]: CoverageRelationStatistics Valid=32, Invalid=58, Unknown=0, NotChecked=0, Total=90 [2018-06-25 12:33:30,696 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 10 states. [2018-06-25 12:33:30,917 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:33:30,917 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 12:33:30,918 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 12:33:30,918 INFO ]: Start accepts. Automaton has 10 states. Word has length 10 [2018-06-25 12:33:30,918 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:33:30,918 INFO ]: With dead ends: 12 [2018-06-25 12:33:30,918 INFO ]: Without dead ends: 12 [2018-06-25 12:33:30,919 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=59, Invalid=97, Unknown=0, NotChecked=0, Total=156 [2018-06-25 12:33:30,919 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 12:33:30,920 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 12:33:30,920 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 12:33:30,920 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 12:33:30,920 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 12:33:30,921 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:33:30,921 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 12:33:30,921 INFO ]: Interpolant automaton has 10 states. [2018-06-25 12:33:30,921 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 12:33:30,921 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 12:33:30,921 INFO ]: Found error trace [2018-06-25 12:33:30,921 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:33:30,921 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:33:30,921 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-25 12:33:30,921 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:33:30,921 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:33:30,922 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:30,922 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:33:30,922 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:31,058 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:33:31,616 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 2 [2018-06-25 12:33:32,057 WARN ]: Spent 368.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 21 [2018-06-25 12:33:32,102 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:33:32,102 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:33:32,102 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 12:33:32,113 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 12:33:32,237 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 12:33:32,237 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:33:32,246 INFO ]: Computing forward predicates... [2018-06-25 12:33:33,470 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:33:33,497 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:33:33,497 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-25 12:33:33,497 INFO ]: Interpolant automaton has 12 states [2018-06-25 12:33:33,497 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-25 12:33:33,498 INFO ]: CoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2018-06-25 12:33:33,499 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 12 states. [2018-06-25 12:33:33,993 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 23 [2018-06-25 12:33:34,133 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:33:34,134 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-25 12:33:34,134 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-25 12:33:34,134 INFO ]: Start accepts. Automaton has 12 states. Word has length 11 [2018-06-25 12:33:34,134 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:33:34,134 INFO ]: With dead ends: 16 [2018-06-25 12:33:34,134 INFO ]: Without dead ends: 16 [2018-06-25 12:33:34,134 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=130, Invalid=250, Unknown=0, NotChecked=0, Total=380 [2018-06-25 12:33:34,135 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-25 12:33:34,135 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-25 12:33:34,136 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-25 12:33:34,136 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-25 12:33:34,136 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 11 [2018-06-25 12:33:34,136 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:33:34,136 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-25 12:33:34,136 INFO ]: Interpolant automaton has 12 states. [2018-06-25 12:33:34,136 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-25 12:33:34,136 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-25 12:33:34,136 INFO ]: Found error trace [2018-06-25 12:33:34,136 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:33:34,136 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:33:34,136 INFO ]: Analyzing trace with hash 1051911180, now seen corresponding path program 4 times [2018-06-25 12:33:34,136 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:33:34,136 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:33:34,137 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:34,137 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:33:34,137 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:33:34,437 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:33:35,224 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-25 12:33:35,546 WARN ]: Spent 258.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 20 [2018-06-25 12:33:35,786 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 42 [2018-06-25 12:33:36,038 WARN ]: Spent 239.00 ms on a formula simplification. DAG size of input: 58 DAG size of output: 33 [2018-06-25 12:33:36,160 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 39 [2018-06-25 12:33:36,252 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:33:36,252 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:33:36,252 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-25 12:33:36,267 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:33:43,945 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 12:33:43,945 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:33:43,965 INFO ]: Computing forward predicates... [2018-06-25 12:33:47,971 WARN ]: Spent 1.05 s on a formula simplification. DAG size of input: 16 DAG size of output: 13 Received shutdown request... [2018-06-25 12:34:33,024 INFO ]: Timeout while computing interpolants [2018-06-25 12:34:33,225 WARN ]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:34:33,225 WARN ]: Verification canceled [2018-06-25 12:34:33,228 WARN ]: Timeout [2018-06-25 12:34:33,229 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 12:34:33 BoogieIcfgContainer [2018-06-25 12:34:33,229 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 12:34:33,229 INFO ]: Toolchain (without parser) took 67792.57 ms. Allocated memory was 309.3 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 239.8 MB in the beginning and 254.1 MB in the end (delta: -14.3 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:34:33,230 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:34:33,230 INFO ]: ChcToBoogie took 84.35 ms. Allocated memory is still 309.3 MB. Free memory was 239.8 MB in the beginning and 237.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:34:33,231 INFO ]: Boogie Preprocessor took 53.77 ms. Allocated memory is still 309.3 MB. Free memory was 237.8 MB in the beginning and 235.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:34:33,231 INFO ]: RCFGBuilder took 473.66 ms. Allocated memory is still 309.3 MB. Free memory was 235.8 MB in the beginning and 207.8 MB in the end (delta: 27.9 MB). Peak memory consumption was 27.9 MB. Max. memory is 3.6 GB. [2018-06-25 12:34:33,231 INFO ]: TraceAbstraction took 67171.69 ms. Allocated memory was 309.3 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 207.8 MB in the beginning and 254.1 MB in the end (delta: -46.3 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:34:33,235 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 309.3 MB. Free memory is still 273.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 84.35 ms. Allocated memory is still 309.3 MB. Free memory was 239.8 MB in the beginning and 237.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 53.77 ms. Allocated memory is still 309.3 MB. Free memory was 237.8 MB in the beginning and 235.8 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 473.66 ms. Allocated memory is still 309.3 MB. Free memory was 235.8 MB in the beginning and 207.8 MB in the end (delta: 27.9 MB). Peak memory consumption was 27.9 MB. Max. memory is 3.6 GB. * TraceAbstraction took 67171.69 ms. Allocated memory was 309.3 MB in the beginning and 1.4 GB in the end (delta: 1.1 GB). Free memory was 207.8 MB in the beginning and 254.1 MB in the end (delta: -46.3 MB). Peak memory consumption was 1.3 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 16 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was XNF transformer was simplifying 2090 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 67.1s OverallTime, 5 OverallIterations, 8 TraceHistogramMax, 1.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 28 SDtfs, 5 SDslu, 66 SDs, 0 SdLazy, 33 SolverSat, 20 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 59 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 97 ImplicationChecksByTransitivity, 3.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=16occurred in iteration=4, 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, 4 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 5.1s InterpolantComputationTime, 65 NumberOfCodeBlocks, 65 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 58 ConstructedInterpolants, 0 QuantifiedInterpolants, 2580 SizeOfPredicates, 12 NumberOfNonLiveVariables, 925 ConjunctsInSsa, 62 ConjunctsInUnsatCore, 7 InterpolantComputations, 1 PerfectInterpolantSequences, 0/34 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.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_12-34-33-244.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/toy.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_12-34-33-244.csv Completed graceful shutdown