java -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/chccomp2018/chcToBoogie_automizer.epf -i /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-55b8104 [2018-06-18 12:43:29,036 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-18 12:43:29,039 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-18 12:43:29,058 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-18 12:43:29,058 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-18 12:43:29,061 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-18 12:43:29,063 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-18 12:43:29,065 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-18 12:43:29,066 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-18 12:43:29,068 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-18 12:43:29,069 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-18 12:43:29,069 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-18 12:43:29,070 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-18 12:43:29,071 INFO L177 SettingsManager]: ChcToBoogie provides no preferences, ignoring... [2018-06-18 12:43:29,071 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-18 12:43:29,076 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-18 12:43:29,078 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-18 12:43:29,091 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-18 12:43:29,094 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-18 12:43:29,095 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-18 12:43:29,096 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-18 12:43:29,098 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-18 12:43:29,098 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-18 12:43:29,098 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-18 12:43:29,099 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-18 12:43:29,100 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-18 12:43:29,100 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-18 12:43:29,101 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-18 12:43:29,105 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-18 12:43:29,105 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-18 12:43:29,106 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-18 12:43:29,106 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-18 12:43:29,107 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-18 12:43:29,107 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-18 12:43:29,110 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-18 12:43:29,110 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chccomp2018/chcToBoogie_automizer.epf [2018-06-18 12:43:29,136 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-18 12:43:29,136 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-18 12:43:29,137 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-18 12:43:29,137 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-18 12:43:29,140 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-18 12:43:29,140 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-18 12:43:29,140 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-18 12:43:29,140 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-18 12:43:29,140 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-18 12:43:29,141 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-18 12:43:29,141 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-18 12:43:29,141 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-18 12:43:29,141 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-18 12:43:29,141 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-18 12:43:29,142 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-18 12:43:29,142 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-18 12:43:29,142 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-18 12:43:29,144 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-18 12:43:29,144 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-18 12:43:29,185 INFO ]: Repository-Root is: /tmp [2018-06-18 12:43:29,200 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-18 12:43:29,204 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-18 12:43:29,205 INFO ]: Initializing SmtParser... [2018-06-18 12:43:29,206 INFO ]: SmtParser initialized [2018-06-18 12:43:29,206 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 [2018-06-18 12:43:29,207 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-18 12:43:29,301 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 unknown [2018-06-18 12:43:29,744 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 [2018-06-18 12:43:29,749 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-18 12:43:29,754 INFO ]: Walking toolchain with 4 elements. [2018-06-18 12:43:29,754 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-18 12:43:29,754 INFO ]: Initializing ChcToBoogie... [2018-06-18 12:43:29,755 INFO ]: ChcToBoogie initialized [2018-06-18 12:43:29,762 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 12:43:29" (1/1) ... [2018-06-18 12:43:30,496 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30 Unit [2018-06-18 12:43:30,497 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-18 12:43:30,497 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-18 12:43:30,497 INFO ]: Initializing Boogie Preprocessor... [2018-06-18 12:43:30,497 INFO ]: Boogie Preprocessor initialized [2018-06-18 12:43:30,520 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30" (1/1) ... [2018-06-18 12:43:30,520 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30" (1/1) ... [2018-06-18 12:43:30,564 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30" (1/1) ... [2018-06-18 12:43:30,564 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30" (1/1) ... [2018-06-18 12:43:30,624 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30" (1/1) ... [2018-06-18 12:43:30,626 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30" (1/1) ... [2018-06-18 12:43:30,641 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30" (1/1) ... [2018-06-18 12:43:30,654 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-18 12:43:30,655 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-18 12:43:30,655 INFO ]: Initializing RCFGBuilder... [2018-06-18 12:43:30,655 INFO ]: RCFGBuilder initialized [2018-06-18 12:43:30,657 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30" (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-18 12:43:30,668 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-18 12:43:30,668 INFO ]: Found specification of procedure False [2018-06-18 12:43:30,668 INFO ]: Found implementation of procedure False [2018-06-18 12:43:30,668 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-18 12:43:30,669 INFO ]: Found specification of procedure state [2018-06-18 12:43:30,669 INFO ]: Found implementation of procedure state [2018-06-18 12:43:30,669 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-18 12:43:30,669 INFO ]: Found specification of procedure Ultimate.START [2018-06-18 12:43:30,669 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-18 12:43:31,513 INFO ]: Using library mode [2018-06-18 12:43:31,514 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 12:43:31 BoogieIcfgContainer [2018-06-18 12:43:31,515 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-18 12:43:31,516 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-18 12:43:31,516 INFO ]: Initializing TraceAbstraction... [2018-06-18 12:43:31,519 INFO ]: TraceAbstraction initialized [2018-06-18 12:43:31,519 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 18.06 12:43:29" (1/3) ... [2018-06-18 12:43:31,520 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@679665b1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 18.06 12:43:31, skipping insertion in model container [2018-06-18 12:43:31,520 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 18.06 12:43:30" (2/3) ... [2018-06-18 12:43:31,520 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@679665b1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 18.06 12:43:31, skipping insertion in model container [2018-06-18 12:43:31,520 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 18.06 12:43:31" (3/3) ... [2018-06-18 12:43:31,523 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-18 12:43:31,533 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-18 12:43:31,542 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-18 12:43:31,591 INFO ]: Using default assertion order modulation [2018-06-18 12:43:31,592 INFO ]: Interprodecural is true [2018-06-18 12:43:31,592 INFO ]: Hoare is false [2018-06-18 12:43:31,592 INFO ]: Compute interpolants for FPandBP [2018-06-18 12:43:31,592 INFO ]: Backedges is TWOTRACK [2018-06-18 12:43:31,592 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-18 12:43:31,592 INFO ]: Difference is false [2018-06-18 12:43:31,592 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-18 12:43:31,592 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-18 12:43:31,610 INFO ]: Start isEmpty. Operand 13 states. [2018-06-18 12:43:31,627 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-18 12:43:31,627 INFO ]: Found error trace [2018-06-18 12:43:31,628 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 12:43:31,628 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 12:43:31,634 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-18 12:43:31,636 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 12:43:31,636 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 12:43:31,686 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:31,686 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 12:43:31,686 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:31,731 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:43:31,741 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 12:43:31,917 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-18 12:43:31,919 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-18 12:43:31,920 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-18 12:43:31,921 INFO ]: Interpolant automaton has 4 states [2018-06-18 12:43:31,937 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-18 12:43:31,937 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 12:43:31,940 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-18 12:43:32,049 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 12:43:32,050 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-18 12:43:32,050 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-18 12:43:32,051 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-18 12:43:32,051 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 12:43:32,061 INFO ]: With dead ends: 13 [2018-06-18 12:43:32,062 INFO ]: Without dead ends: 13 [2018-06-18 12:43:32,063 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-18 12:43:32,080 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-18 12:43:32,108 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-18 12:43:32,109 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-18 12:43:32,109 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-18 12:43:32,110 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-18 12:43:32,111 INFO ]: Finished accepts. word is rejected. [2018-06-18 12:43:32,111 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-18 12:43:32,111 INFO ]: Interpolant automaton has 4 states. [2018-06-18 12:43:32,111 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-18 12:43:32,112 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-18 12:43:32,112 INFO ]: Found error trace [2018-06-18 12:43:32,112 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 12:43:32,112 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 12:43:32,112 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-18 12:43:32,113 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 12:43:32,113 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 12:43:32,113 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:32,113 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 12:43:32,113 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:32,238 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:43:32,239 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 12:43:32,663 WARN ]: Spent 124.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-18 12:43:32,666 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 12:43:32,666 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 12:43:32,666 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) [2018-06-18 12:43:32,683 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 12:43:32,756 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:43:32,771 INFO ]: Computing forward predicates... [2018-06-18 12:43:35,026 WARN ]: Spent 1.54 s on a formula simplification. DAG size of input: 40 DAG size of output: 31 [2018-06-18 12:43:35,498 WARN ]: Spent 113.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-18 12:43:35,550 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-18 12:43:35,572 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 12:43:35,572 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-18 12:43:35,573 INFO ]: Interpolant automaton has 9 states [2018-06-18 12:43:35,573 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-18 12:43:35,573 INFO ]: CoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2018-06-18 12:43:35,573 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-18 12:43:35,889 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 16 [2018-06-18 12:43:36,212 WARN ]: Spent 272.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 26 [2018-06-18 12:43:36,226 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 12:43:36,226 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-18 12:43:36,226 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-18 12:43:36,226 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-18 12:43:36,227 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 12:43:36,227 INFO ]: With dead ends: 17 [2018-06-18 12:43:36,227 INFO ]: Without dead ends: 17 [2018-06-18 12:43:36,228 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=36, Invalid=74, Unknown=0, NotChecked=0, Total=110 [2018-06-18 12:43:36,228 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-18 12:43:36,231 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-18 12:43:36,231 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-18 12:43:36,232 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-18 12:43:36,232 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 13 [2018-06-18 12:43:36,232 INFO ]: Finished accepts. word is rejected. [2018-06-18 12:43:36,232 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-18 12:43:36,232 INFO ]: Interpolant automaton has 9 states. [2018-06-18 12:43:36,232 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-18 12:43:36,233 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-18 12:43:36,233 INFO ]: Found error trace [2018-06-18 12:43:36,233 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 12:43:36,233 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 12:43:36,233 INFO ]: Analyzing trace with hash 2119922091, now seen corresponding path program 2 times [2018-06-18 12:43:36,233 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 12:43:36,233 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 12:43:36,234 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:36,234 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-18 12:43:36,234 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:36,440 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:43:36,441 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 12:43:36,839 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 12:43:36,839 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 12:43:36,839 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-18 12:43:36,888 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-18 12:43:36,990 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-18 12:43:36,990 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:43:37,001 INFO ]: Computing forward predicates... [2018-06-18 12:43:37,839 WARN ]: Spent 364.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 26 [2018-06-18 12:43:39,131 WARN ]: Spent 764.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 48 [2018-06-18 12:43:40,313 WARN ]: Spent 711.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 51 [2018-06-18 12:43:41,122 WARN ]: Spent 339.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 12 [2018-06-18 12:43:41,127 INFO ]: Checked inductivity of 21 backedges. 1 proven. 14 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-18 12:43:41,151 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 12:43:41,151 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2018-06-18 12:43:41,151 INFO ]: Interpolant automaton has 16 states [2018-06-18 12:43:41,152 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-18 12:43:41,152 INFO ]: CoverageRelationStatistics Valid=56, Invalid=184, Unknown=0, NotChecked=0, Total=240 [2018-06-18 12:43:41,152 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 16 states. [2018-06-18 12:43:42,025 WARN ]: Spent 800.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 80 [2018-06-18 12:43:42,334 WARN ]: Spent 274.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 23 [2018-06-18 12:43:43,006 WARN ]: Spent 376.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 52 [2018-06-18 12:43:43,032 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 12:43:43,032 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-18 12:43:43,035 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-18 12:43:43,035 INFO ]: Start accepts. Automaton has 16 states. Word has length 21 [2018-06-18 12:43:43,035 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 12:43:43,036 INFO ]: With dead ends: 19 [2018-06-18 12:43:43,036 INFO ]: Without dead ends: 19 [2018-06-18 12:43:43,037 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=103, Invalid=277, Unknown=0, NotChecked=0, Total=380 [2018-06-18 12:43:43,037 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-18 12:43:43,039 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-18 12:43:43,040 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-18 12:43:43,043 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-18 12:43:43,043 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-18 12:43:43,043 INFO ]: Finished accepts. word is rejected. [2018-06-18 12:43:43,043 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-18 12:43:43,043 INFO ]: Interpolant automaton has 16 states. [2018-06-18 12:43:43,043 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-18 12:43:43,044 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-18 12:43:43,044 INFO ]: Found error trace [2018-06-18 12:43:43,044 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 12:43:43,044 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 12:43:43,044 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 3 times [2018-06-18 12:43:43,044 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 12:43:43,044 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 12:43:43,045 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:43,045 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 12:43:43,045 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:43,328 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:43:43,329 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 12:43:43,706 WARN ]: Spent 123.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-18 12:43:43,964 WARN ]: Spent 210.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-18 12:43:44,275 WARN ]: Spent 297.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 72 [2018-06-18 12:43:44,544 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 12:43:44,544 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 12:43:44,544 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-18 12:43:44,552 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-18 12:43:44,635 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-18 12:43:44,635 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:43:44,645 INFO ]: Computing forward predicates... [2018-06-18 12:43:45,995 WARN ]: Spent 794.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 31 [2018-06-18 12:43:49,633 WARN ]: Spent 2.50 s on a formula simplification. DAG size of input: 320 DAG size of output: 49 [2018-06-18 12:43:50,764 WARN ]: Spent 715.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 62 [2018-06-18 12:43:51,717 WARN ]: Spent 526.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 51 [2018-06-18 12:43:51,934 INFO ]: Checked inductivity of 36 backedges. 3 proven. 23 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-18 12:43:51,956 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 12:43:51,956 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2018-06-18 12:43:51,956 INFO ]: Interpolant automaton has 19 states [2018-06-18 12:43:51,956 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-18 12:43:51,956 INFO ]: CoverageRelationStatistics Valid=73, Invalid=269, Unknown=0, NotChecked=0, Total=342 [2018-06-18 12:43:51,957 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 19 states. [2018-06-18 12:43:53,607 WARN ]: Spent 1.60 s on a formula simplification. DAG size of input: 167 DAG size of output: 147 [2018-06-18 12:43:53,911 WARN ]: Spent 196.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 23 [2018-06-18 12:43:54,300 WARN ]: Spent 354.00 ms on a formula simplification. DAG size of input: 118 DAG size of output: 21 [2018-06-18 12:43:54,750 WARN ]: Spent 413.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 52 [2018-06-18 12:43:55,785 WARN ]: Spent 983.00 ms on a formula simplification. DAG size of input: 171 DAG size of output: 130 [2018-06-18 12:43:55,834 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 12:43:55,834 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-18 12:43:55,835 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-18 12:43:55,835 INFO ]: Start accepts. Automaton has 19 states. Word has length 25 [2018-06-18 12:43:55,835 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 12:43:55,836 INFO ]: With dead ends: 21 [2018-06-18 12:43:55,836 INFO ]: Without dead ends: 21 [2018-06-18 12:43:55,836 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 9.9s TimeCoverageRelationStatistics Valid=144, Invalid=408, Unknown=0, NotChecked=0, Total=552 [2018-06-18 12:43:55,836 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-18 12:43:55,841 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-18 12:43:55,841 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-18 12:43:55,841 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-18 12:43:55,841 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-18 12:43:55,842 INFO ]: Finished accepts. word is rejected. [2018-06-18 12:43:55,842 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-18 12:43:55,842 INFO ]: Interpolant automaton has 19 states. [2018-06-18 12:43:55,842 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-18 12:43:55,842 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-18 12:43:55,842 INFO ]: Found error trace [2018-06-18 12:43:55,843 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 12:43:55,843 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 12:43:55,843 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 4 times [2018-06-18 12:43:55,843 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 12:43:55,843 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 12:43:55,844 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:55,844 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 12:43:55,844 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:43:56,144 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:43:56,145 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 12:43:56,553 WARN ]: Spent 106.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-18 12:43:57,039 WARN ]: Spent 436.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-18 12:43:57,498 WARN ]: Spent 379.00 ms on a formula simplification. DAG size of input: 129 DAG size of output: 63 [2018-06-18 12:43:57,751 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 131 DAG size of output: 80 [2018-06-18 12:43:58,053 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 12:43:58,053 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 12:43:58,053 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) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 12:43:58,059 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-18 12:43:58,198 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-18 12:43:58,198 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:43:58,209 INFO ]: Computing forward predicates... [2018-06-18 12:43:59,145 WARN ]: Spent 386.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 31 [2018-06-18 12:43:59,828 WARN ]: Spent 473.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 45 [2018-06-18 12:44:02,890 WARN ]: Spent 2.48 s on a formula simplification. DAG size of input: 321 DAG size of output: 82 [2018-06-18 12:44:06,237 WARN ]: Spent 2.70 s on a formula simplification. DAG size of input: 257 DAG size of output: 98 [2018-06-18 12:44:07,130 WARN ]: Spent 505.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 65 [2018-06-18 12:44:07,385 INFO ]: Checked inductivity of 55 backedges. 5 proven. 35 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-18 12:44:07,406 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 12:44:07,406 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 24 [2018-06-18 12:44:07,406 INFO ]: Interpolant automaton has 24 states [2018-06-18 12:44:07,406 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-18 12:44:07,407 INFO ]: CoverageRelationStatistics Valid=108, Invalid=444, Unknown=0, NotChecked=0, Total=552 [2018-06-18 12:44:07,407 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 24 states. [2018-06-18 12:44:09,998 WARN ]: Spent 2.52 s on a formula simplification. DAG size of input: 226 DAG size of output: 197 [2018-06-18 12:44:10,346 WARN ]: Spent 283.00 ms on a formula simplification. DAG size of input: 226 DAG size of output: 41 [2018-06-18 12:44:10,583 WARN ]: Spent 187.00 ms on a formula simplification. DAG size of input: 196 DAG size of output: 34 [2018-06-18 12:44:10,833 WARN ]: Spent 209.00 ms on a formula simplification. DAG size of input: 196 DAG size of output: 40 [2018-06-18 12:44:11,639 WARN ]: Spent 744.00 ms on a formula simplification. DAG size of input: 199 DAG size of output: 73 [2018-06-18 12:44:13,150 WARN ]: Spent 1.43 s on a formula simplification. DAG size of input: 230 DAG size of output: 183 [2018-06-18 12:44:13,298 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 12:44:13,298 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-18 12:44:13,299 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-18 12:44:13,299 INFO ]: Start accepts. Automaton has 24 states. Word has length 29 [2018-06-18 12:44:13,299 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 12:44:13,300 INFO ]: With dead ends: 23 [2018-06-18 12:44:13,300 INFO ]: Without dead ends: 23 [2018-06-18 12:44:13,300 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 132 ImplicationChecksByTransitivity, 15.2s TimeCoverageRelationStatistics Valid=213, Invalid=657, Unknown=0, NotChecked=0, Total=870 [2018-06-18 12:44:13,300 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-18 12:44:13,304 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-18 12:44:13,304 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-18 12:44:13,304 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-18 12:44:13,305 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-18 12:44:13,305 INFO ]: Finished accepts. word is rejected. [2018-06-18 12:44:13,305 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-18 12:44:13,305 INFO ]: Interpolant automaton has 24 states. [2018-06-18 12:44:13,305 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-18 12:44:13,306 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-18 12:44:13,306 INFO ]: Found error trace [2018-06-18 12:44:13,306 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 12:44:13,306 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 12:44:13,306 INFO ]: Analyzing trace with hash -1661294575, now seen corresponding path program 5 times [2018-06-18 12:44:13,306 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 12:44:13,306 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 12:44:13,307 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:44:13,307 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 12:44:13,307 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:44:13,630 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:44:13,631 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 12:44:14,271 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 139 DAG size of output: 78 [2018-06-18 12:44:14,623 WARN ]: Spent 334.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 82 [2018-06-18 12:44:15,030 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-18 12:44:15,030 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-18 12:44:15,030 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-18 12:44:15,038 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-18 12:44:15,225 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-06-18 12:44:15,225 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:44:15,250 INFO ]: Computing forward predicates... [2018-06-18 12:44:15,603 WARN ]: Spent 218.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 31 [2018-06-18 12:44:16,957 WARN ]: Spent 658.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 62 [2018-06-18 12:44:20,022 WARN ]: Spent 2.19 s on a formula simplification. DAG size of input: 305 DAG size of output: 75 [2018-06-18 12:44:21,193 WARN ]: Spent 844.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 71 [2018-06-18 12:44:22,241 WARN ]: Spent 741.00 ms on a formula simplification. DAG size of input: 177 DAG size of output: 70 [2018-06-18 12:44:22,485 INFO ]: Checked inductivity of 78 backedges. 9 proven. 47 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-18 12:44:22,516 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-18 12:44:22,516 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 24 [2018-06-18 12:44:22,516 INFO ]: Interpolant automaton has 24 states [2018-06-18 12:44:22,516 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-18 12:44:22,517 INFO ]: CoverageRelationStatistics Valid=97, Invalid=455, Unknown=0, NotChecked=0, Total=552 [2018-06-18 12:44:22,517 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 24 states. [2018-06-18 12:44:23,801 WARN ]: Spent 1.08 s on a formula simplification. DAG size of input: 216 DAG size of output: 161 [2018-06-18 12:44:24,025 WARN ]: Spent 160.00 ms on a formula simplification. DAG size of input: 217 DAG size of output: 27 [2018-06-18 12:44:24,235 WARN ]: Spent 151.00 ms on a formula simplification. DAG size of input: 221 DAG size of output: 23 [2018-06-18 12:44:24,501 WARN ]: Spent 212.00 ms on a formula simplification. DAG size of input: 220 DAG size of output: 37 [2018-06-18 12:44:24,754 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 217 DAG size of output: 36 [2018-06-18 12:44:24,970 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 219 DAG size of output: 29 [2018-06-18 12:44:25,851 WARN ]: Spent 823.00 ms on a formula simplification. DAG size of input: 220 DAG size of output: 84 [2018-06-18 12:44:25,903 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-18 12:44:25,903 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-18 12:44:25,904 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-18 12:44:25,904 INFO ]: Start accepts. Automaton has 24 states. Word has length 33 [2018-06-18 12:44:25,904 INFO ]: Finished accepts. some prefix is accepted. [2018-06-18 12:44:25,905 INFO ]: With dead ends: 25 [2018-06-18 12:44:25,905 INFO ]: Without dead ends: 25 [2018-06-18 12:44:25,906 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 23 SyntacticMatches, 3 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 108 ImplicationChecksByTransitivity, 9.9s TimeCoverageRelationStatistics Valid=218, Invalid=712, Unknown=0, NotChecked=0, Total=930 [2018-06-18 12:44:25,906 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-18 12:44:25,909 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-18 12:44:25,909 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-18 12:44:25,909 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-18 12:44:25,909 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-18 12:44:25,910 INFO ]: Finished accepts. word is rejected. [2018-06-18 12:44:25,911 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-18 12:44:25,911 INFO ]: Interpolant automaton has 24 states. [2018-06-18 12:44:25,911 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-18 12:44:25,911 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-18 12:44:25,912 INFO ]: Found error trace [2018-06-18 12:44:25,912 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-18 12:44:25,912 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-18 12:44:25,912 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 6 times [2018-06-18 12:44:25,912 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-18 12:44:25,912 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-18 12:44:25,913 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:44:25,913 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-18 12:44:25,913 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-18 12:44:26,319 INFO ]: Conjunction of SSA is unsat [2018-06-18 12:44:26,320 WARN ]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-06-18 12:44:26,739 WARN ]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-18 12:44:27,257 WARN ]: Spent 466.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-06-18 12:44:27,833 WARN ]: Spent 466.00 ms on a formula simplification. DAG size of input: 172 DAG size of output: 107 Received shutdown request... [2018-06-18 12:44:28,059 WARN ]: Removed 6 from assertion stack [2018-06-18 12:44:28,059 WARN ]: Verification canceled [2018-06-18 12:44:28,062 WARN ]: Timeout [2018-06-18 12:44:28,063 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 18.06 12:44:28 BoogieIcfgContainer [2018-06-18 12:44:28,063 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-18 12:44:28,063 INFO ]: Toolchain (without parser) took 58314.16 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 245.5 MB in the beginning and 991.7 MB in the end (delta: -746.1 MB). Peak memory consumption was 426.2 MB. Max. memory is 3.6 GB. [2018-06-18 12:44:28,064 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 305.1 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-18 12:44:28,064 INFO ]: ChcToBoogie took 742.49 ms. Allocated memory was 305.1 MB in the beginning and 401.1 MB in the end (delta: 95.9 MB). Free memory was 245.5 MB in the beginning and 338.7 MB in the end (delta: -93.2 MB). Peak memory consumption was 123.6 MB. Max. memory is 3.6 GB. [2018-06-18 12:44:28,065 INFO ]: Boogie Preprocessor took 157.26 ms. Allocated memory is still 401.1 MB. Free memory was 338.7 MB in the beginning and 328.7 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 3.6 GB. [2018-06-18 12:44:28,065 INFO ]: RCFGBuilder took 860.37 ms. Allocated memory is still 401.1 MB. Free memory was 328.7 MB in the beginning and 246.0 MB in the end (delta: 82.7 MB). Peak memory consumption was 82.7 MB. Max. memory is 3.6 GB. [2018-06-18 12:44:28,066 INFO ]: TraceAbstraction took 56546.49 ms. Allocated memory was 401.1 MB in the beginning and 1.5 GB in the end (delta: 1.1 GB). Free memory was 246.0 MB in the beginning and 991.7 MB in the end (delta: -745.7 MB). Peak memory consumption was 330.7 MB. Max. memory is 3.6 GB. [2018-06-18 12:44:28,068 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 305.1 MB. Free memory is still 270.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 742.49 ms. Allocated memory was 305.1 MB in the beginning and 401.1 MB in the end (delta: 95.9 MB). Free memory was 245.5 MB in the beginning and 338.7 MB in the end (delta: -93.2 MB). Peak memory consumption was 123.6 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 157.26 ms. Allocated memory is still 401.1 MB. Free memory was 338.7 MB in the beginning and 328.7 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 860.37 ms. Allocated memory is still 401.1 MB. Free memory was 328.7 MB in the beginning and 246.0 MB in the end (delta: 82.7 MB). Peak memory consumption was 82.7 MB. Max. memory is 3.6 GB. * TraceAbstraction took 56546.49 ms. Allocated memory was 401.1 MB in the beginning and 1.5 GB in the end (delta: 1.1 GB). Free memory was 246.0 MB in the beginning and 991.7 MB in the end (delta: -745.7 MB). Peak memory consumption was 330.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 38 with TraceHistMax 8, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 155. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 56.4s OverallTime, 7 OverallIterations, 8 TraceHistogramMax, 15.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 74 SDtfs, 130 SDslu, 322 SDs, 0 SdLazy, 287 SolverSat, 158 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 202 GetRequests, 90 SyntacticMatches, 4 SemanticMatches, 108 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 357 ImplicationChecksByTransitivity, 42.6s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=6, 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, 6 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.6s SatisfiabilityAnalysisTime, 36.1s InterpolantComputationTime, 251 NumberOfCodeBlocks, 251 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 240 ConstructedInterpolants, 0 QuantifiedInterpolants, 206456 SizeOfPredicates, 1245 NumberOfNonLiveVariables, 1669 ConjunctsInSsa, 198 ConjunctsInUnsatCore, 11 InterpolantComputations, 1 PerfectInterpolantSequences, 125/386 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/bubblesort_init-1.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-18_12-44-28-078.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bubblesort_init-1.smt2_chcToBoogie_automizer.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-18_12-44-28-078.csv Completed graceful shutdown