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/bubblesort-2.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 11:53:38,011 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 11:53:38,013 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 11:53:38,027 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 11:53:38,027 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 11:53:38,029 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 11:53:38,030 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 11:53:38,032 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 11:53:38,034 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 11:53:38,034 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 11:53:38,035 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 11:53:38,035 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 11:53:38,037 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 11:53:38,038 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 11:53:38,039 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 11:53:38,042 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 11:53:38,044 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 11:53:38,054 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 11:53:38,056 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 11:53:38,057 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 11:53:38,059 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 11:53:38,061 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 11:53:38,062 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 11:53:38,062 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 11:53:38,062 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 11:53:38,068 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 11:53:38,069 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 11:53:38,069 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 11:53:38,070 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 11:53:38,070 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 11:53:38,071 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 11:53:38,071 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 11:53:38,077 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 11:53:38,078 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 11:53:38,079 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 11:53:38,079 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 11:53:38,103 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 11:53:38,104 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 11:53:38,104 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 11:53:38,104 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 11:53:38,105 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 11:53:38,105 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 11:53:38,106 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 11:53:38,106 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 11:53:38,106 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 11:53:38,106 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 11:53:38,106 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 11:53:38,107 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 11:53:38,110 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 11:53:38,110 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 11:53:38,110 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 11:53:38,111 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 11:53:38,111 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 11:53:38,111 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 11:53:38,111 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 11:53:38,111 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 11:53:38,111 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 11:53:38,113 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 11:53:38,113 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 11:53:38,171 INFO ]: Repository-Root is: /tmp [2018-06-25 11:53:38,191 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 11:53:38,199 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 11:53:38,200 INFO ]: Initializing SmtParser... [2018-06-25 11:53:38,201 INFO ]: SmtParser initialized [2018-06-25 11:53:38,201 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort-2.smt2 [2018-06-25 11:53:38,203 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 11:53:38,297 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort-2.smt2 unknown [2018-06-25 11:53:38,818 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort-2.smt2 [2018-06-25 11:53:38,826 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 11:53:38,832 INFO ]: Walking toolchain with 4 elements. [2018-06-25 11:53:38,832 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 11:53:38,832 INFO ]: Initializing ChcToBoogie... [2018-06-25 11:53:38,833 INFO ]: ChcToBoogie initialized [2018-06-25 11:53:38,841 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 11:53:38" (1/1) ... [2018-06-25 11:53:38,944 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38 Unit [2018-06-25 11:53:38,944 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 11:53:38,945 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 11:53:38,945 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 11:53:38,945 INFO ]: Boogie Preprocessor initialized [2018-06-25 11:53:38,959 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38" (1/1) ... [2018-06-25 11:53:38,959 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38" (1/1) ... [2018-06-25 11:53:38,969 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38" (1/1) ... [2018-06-25 11:53:38,969 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38" (1/1) ... [2018-06-25 11:53:38,981 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38" (1/1) ... [2018-06-25 11:53:38,982 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38" (1/1) ... [2018-06-25 11:53:38,986 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38" (1/1) ... [2018-06-25 11:53:38,990 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 11:53:38,990 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 11:53:38,990 INFO ]: Initializing RCFGBuilder... [2018-06-25 11:53:38,990 INFO ]: RCFGBuilder initialized [2018-06-25 11:53:38,991 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38" (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 11:53:39,001 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 11:53:39,001 INFO ]: Found specification of procedure gotoProc [2018-06-25 11:53:39,001 INFO ]: Found implementation of procedure gotoProc [2018-06-25 11:53:39,001 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 11:53:39,001 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 11:53:39,001 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 11:53:39,400 INFO ]: Using library mode [2018-06-25 11:53:39,400 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 11:53:39 BoogieIcfgContainer [2018-06-25 11:53:39,400 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 11:53:39,402 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 11:53:39,402 INFO ]: Initializing TraceAbstraction... [2018-06-25 11:53:39,405 INFO ]: TraceAbstraction initialized [2018-06-25 11:53:39,405 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 11:53:38" (1/3) ... [2018-06-25 11:53:39,406 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41d715c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 11:53:39, skipping insertion in model container [2018-06-25 11:53:39,406 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 11:53:38" (2/3) ... [2018-06-25 11:53:39,407 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@41d715c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 11:53:39, skipping insertion in model container [2018-06-25 11:53:39,407 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 11:53:39" (3/3) ... [2018-06-25 11:53:39,409 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 11:53:39,420 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 11:53:39,430 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 11:53:39,481 INFO ]: Using default assertion order modulation [2018-06-25 11:53:39,481 INFO ]: Interprodecural is true [2018-06-25 11:53:39,481 INFO ]: Hoare is false [2018-06-25 11:53:39,482 INFO ]: Compute interpolants for FPandBP [2018-06-25 11:53:39,482 INFO ]: Backedges is TWOTRACK [2018-06-25 11:53:39,482 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 11:53:39,482 INFO ]: Difference is false [2018-06-25 11:53:39,482 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 11:53:39,482 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 11:53:39,497 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 11:53:39,511 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 11:53:39,512 INFO ]: Found error trace [2018-06-25 11:53:39,514 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 11:53:39,514 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 11:53:39,519 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 11:53:39,521 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 11:53:39,522 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 11:53:39,570 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:39,570 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 11:53:39,570 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:39,636 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:39,771 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:39,774 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 11:53:39,774 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 11:53:39,776 INFO ]: Interpolant automaton has 3 states [2018-06-25 11:53:39,791 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 11:53:39,791 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 11:53:39,795 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 11:53:39,882 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 11:53:39,882 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 11:53:39,884 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 11:53:39,885 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 11:53:39,886 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 11:53:39,895 INFO ]: With dead ends: 9 [2018-06-25 11:53:39,895 INFO ]: Without dead ends: 9 [2018-06-25 11:53:39,897 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 11:53:39,915 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 11:53:39,937 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 11:53:39,939 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 11:53:39,939 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 11:53:39,941 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 11:53:39,941 INFO ]: Finished accepts. word is rejected. [2018-06-25 11:53:39,941 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 11:53:39,941 INFO ]: Interpolant automaton has 3 states. [2018-06-25 11:53:39,941 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 11:53:39,941 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 11:53:39,941 INFO ]: Found error trace [2018-06-25 11:53:39,941 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 11:53:39,941 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 11:53:39,942 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 11:53:39,942 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 11:53:39,942 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 11:53:39,942 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:39,942 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 11:53:39,942 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:40,078 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:40,289 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:40,289 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 11:53:40,289 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 11:53:40,299 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 11:53:40,428 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:40,440 INFO ]: Computing forward predicates... [2018-06-25 11:53:41,949 WARN ]: Spent 339.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 12 [2018-06-25 11:53:41,957 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:42,014 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 11:53:42,014 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 11:53:42,016 INFO ]: Interpolant automaton has 5 states [2018-06-25 11:53:42,016 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 11:53:42,016 INFO ]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-25 11:53:42,016 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 11:53:42,111 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 11:53:42,111 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 11:53:42,111 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 11:53:42,111 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 11:53:42,111 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 11:53:42,111 INFO ]: With dead ends: 10 [2018-06-25 11:53:42,111 INFO ]: Without dead ends: 10 [2018-06-25 11:53:42,112 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-25 11:53:42,112 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 11:53:42,113 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 11:53:42,113 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 11:53:42,114 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 11:53:42,114 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 11:53:42,114 INFO ]: Finished accepts. word is rejected. [2018-06-25 11:53:42,114 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 11:53:42,114 INFO ]: Interpolant automaton has 5 states. [2018-06-25 11:53:42,114 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 11:53:42,114 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 11:53:42,114 INFO ]: Found error trace [2018-06-25 11:53:42,114 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 11:53:42,114 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 11:53:42,114 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 11:53:42,114 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 11:53:42,114 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 11:53:42,115 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:42,115 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 11:53:42,115 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:42,198 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:42,451 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:42,451 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 11:53:42,451 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 11:53:42,457 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 11:53:42,567 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 11:53:42,567 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:42,577 INFO ]: Computing forward predicates... [2018-06-25 11:53:42,975 WARN ]: Spent 199.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 4 [2018-06-25 11:53:44,570 WARN ]: Spent 192.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 11 [2018-06-25 11:53:44,573 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:44,593 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 11:53:44,593 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 7 [2018-06-25 11:53:44,593 INFO ]: Interpolant automaton has 7 states [2018-06-25 11:53:44,593 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 11:53:44,593 INFO ]: CoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-25 11:53:44,593 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 7 states. [2018-06-25 11:53:44,670 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 11:53:44,671 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 11:53:44,672 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 11:53:44,672 INFO ]: Start accepts. Automaton has 7 states. Word has length 9 [2018-06-25 11:53:44,672 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 11:53:44,672 INFO ]: With dead ends: 11 [2018-06-25 11:53:44,672 INFO ]: Without dead ends: 11 [2018-06-25 11:53:44,673 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-25 11:53:44,673 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 11:53:44,674 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 11:53:44,675 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 11:53:44,675 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 11:53:44,675 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 11:53:44,675 INFO ]: Finished accepts. word is rejected. [2018-06-25 11:53:44,675 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 11:53:44,675 INFO ]: Interpolant automaton has 7 states. [2018-06-25 11:53:44,675 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 11:53:44,675 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 11:53:44,675 INFO ]: Found error trace [2018-06-25 11:53:44,675 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 11:53:44,676 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 11:53:44,676 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-25 11:53:44,676 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 11:53:44,676 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 11:53:44,676 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:44,676 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 11:53:44,676 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:44,794 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:45,074 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-25 11:53:45,426 WARN ]: Spent 140.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-25 11:53:45,645 WARN ]: Spent 123.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-25 11:53:45,646 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:45,646 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 11:53:45,646 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-25 11:53:45,663 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 11:53:45,793 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 11:53:45,793 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:45,804 INFO ]: Computing forward predicates... [2018-06-25 11:53:48,007 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 18 [2018-06-25 11:53:49,018 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:49,043 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 11:53:49,043 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-25 11:53:49,044 INFO ]: Interpolant automaton has 9 states [2018-06-25 11:53:49,044 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-25 11:53:49,044 INFO ]: CoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2018-06-25 11:53:49,044 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 9 states. [2018-06-25 11:53:49,239 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 11:53:49,240 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 11:53:49,240 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 11:53:49,240 INFO ]: Start accepts. Automaton has 9 states. Word has length 10 [2018-06-25 11:53:49,240 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 11:53:49,240 INFO ]: With dead ends: 12 [2018-06-25 11:53:49,240 INFO ]: Without dead ends: 12 [2018-06-25 11:53:49,241 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-06-25 11:53:49,241 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 11:53:49,242 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 11:53:49,242 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 11:53:49,242 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 11:53:49,242 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 11:53:49,242 INFO ]: Finished accepts. word is rejected. [2018-06-25 11:53:49,242 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 11:53:49,242 INFO ]: Interpolant automaton has 9 states. [2018-06-25 11:53:49,242 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 11:53:49,243 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 11:53:49,243 INFO ]: Found error trace [2018-06-25 11:53:49,243 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 11:53:49,243 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 11:53:49,243 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 4 times [2018-06-25 11:53:49,243 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 11:53:49,243 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 11:53:49,244 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:49,244 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 11:53:49,244 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:49,417 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:49,796 WARN ]: Spent 169.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 5 [2018-06-25 11:53:49,860 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:49,860 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 11:53:49,860 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-25 11:53:49,867 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 11:53:50,022 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 11:53:50,022 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:50,031 INFO ]: Computing forward predicates... [2018-06-25 11:53:52,727 WARN ]: Spent 1.12 s on a formula simplification. DAG size of input: 19 DAG size of output: 12 [2018-06-25 11:53:53,988 WARN ]: Spent 234.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 25 [2018-06-25 11:53:55,681 WARN ]: Spent 363.00 ms on a formula simplification. DAG size of input: 36 DAG size of output: 18 [2018-06-25 11:53:56,081 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:56,101 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 11:53:56,101 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2018-06-25 11:53:56,101 INFO ]: Interpolant automaton has 11 states [2018-06-25 11:53:56,101 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-25 11:53:56,101 INFO ]: CoverageRelationStatistics Valid=46, Invalid=64, Unknown=0, NotChecked=0, Total=110 [2018-06-25 11:53:56,101 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 11 states. [2018-06-25 11:53:56,278 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 11:53:56,279 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 11:53:56,279 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 11:53:56,279 INFO ]: Start accepts. Automaton has 11 states. Word has length 11 [2018-06-25 11:53:56,279 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 11:53:56,279 INFO ]: With dead ends: 14 [2018-06-25 11:53:56,279 INFO ]: Without dead ends: 14 [2018-06-25 11:53:56,279 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=75, Invalid=107, Unknown=0, NotChecked=0, Total=182 [2018-06-25 11:53:56,279 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 11:53:56,280 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 11:53:56,280 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 11:53:56,281 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 11:53:56,281 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 11 [2018-06-25 11:53:56,281 INFO ]: Finished accepts. word is rejected. [2018-06-25 11:53:56,281 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 11:53:56,281 INFO ]: Interpolant automaton has 11 states. [2018-06-25 11:53:56,281 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 11:53:56,281 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 11:53:56,281 INFO ]: Found error trace [2018-06-25 11:53:56,281 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 11:53:56,281 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 11:53:56,281 INFO ]: Analyzing trace with hash 23503628, now seen corresponding path program 5 times [2018-06-25 11:53:56,281 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 11:53:56,281 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 11:53:56,282 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:56,282 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 11:53:56,282 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:53:56,563 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:57,022 WARN ]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-25 11:53:57,519 WARN ]: Spent 417.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 9 [2018-06-25 11:53:57,803 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:53:57,803 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 11:53:57,803 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-25 11:53:57,809 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 11:53:58,010 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 11:53:58,010 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:53:58,021 INFO ]: Computing forward predicates... [2018-06-25 11:54:21,971 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 25 [2018-06-25 11:54:25,999 WARN ]: Spent 869.00 ms on a formula simplification. DAG size of input: 202 DAG size of output: 26 [2018-06-25 11:54:26,444 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 20 [2018-06-25 11:54:26,852 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:54:26,874 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 11:54:26,874 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2018-06-25 11:54:26,874 INFO ]: Interpolant automaton has 15 states [2018-06-25 11:54:26,874 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-25 11:54:26,874 INFO ]: CoverageRelationStatistics Valid=79, Invalid=131, Unknown=0, NotChecked=0, Total=210 [2018-06-25 11:54:26,874 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 15 states. [2018-06-25 11:54:27,490 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 11:54:27,490 INFO ]: Finished difference Result 19 states and 19 transitions. [2018-06-25 11:54:27,492 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-25 11:54:27,492 INFO ]: Start accepts. Automaton has 15 states. Word has length 13 [2018-06-25 11:54:27,492 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 11:54:27,492 INFO ]: With dead ends: 19 [2018-06-25 11:54:27,492 INFO ]: Without dead ends: 19 [2018-06-25 11:54:27,493 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=183, Invalid=279, Unknown=0, NotChecked=0, Total=462 [2018-06-25 11:54:27,493 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-25 11:54:27,494 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-25 11:54:27,494 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-25 11:54:27,495 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-06-25 11:54:27,495 INFO ]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 13 [2018-06-25 11:54:27,495 INFO ]: Finished accepts. word is rejected. [2018-06-25 11:54:27,495 INFO ]: Abstraction has 19 states and 19 transitions. [2018-06-25 11:54:27,495 INFO ]: Interpolant automaton has 15 states. [2018-06-25 11:54:27,495 INFO ]: Start isEmpty. Operand 19 states and 19 transitions. [2018-06-25 11:54:27,495 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-25 11:54:27,495 INFO ]: Found error trace [2018-06-25 11:54:27,495 INFO ]: trace histogram [11, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 11:54:27,495 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 11:54:27,496 INFO ]: Analyzing trace with hash -464714988, now seen corresponding path program 6 times [2018-06-25 11:54:27,496 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 11:54:27,496 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 11:54:27,496 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:54:27,496 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 11:54:27,496 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 11:54:28,476 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:54:29,116 WARN ]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-25 11:54:29,851 INFO ]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 11:54:29,851 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 11:54:29,851 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 11:54:29,861 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 11:54:30,307 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-25 11:54:30,307 INFO ]: Conjunction of SSA is unsat [2018-06-25 11:54:30,327 INFO ]: Computing forward predicates... [2018-06-25 11:54:31,687 WARN ]: Spent 325.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 31 [2018-06-25 11:54:34,711 WARN ]: Spent 1.09 s on a formula simplification. DAG size of input: 248 DAG size of output: 37 Received shutdown request... [2018-06-25 11:54:36,251 INFO ]: Timeout while computing interpolants [2018-06-25 11:54:36,451 WARN ]: Destroyed unattended storables created during the last iteration: 8 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 11:54:36,452 WARN ]: Verification canceled [2018-06-25 11:54:36,456 WARN ]: Timeout [2018-06-25 11:54:36,456 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 11:54:36 BoogieIcfgContainer [2018-06-25 11:54:36,456 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 11:54:36,457 INFO ]: Toolchain (without parser) took 57630.59 ms. Allocated memory was 303.0 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 239.5 MB in the beginning and 421.4 MB in the end (delta: -182.0 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 11:54:36,458 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 303.0 MB. Free memory is still 267.5 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 11:54:36,458 INFO ]: ChcToBoogie took 112.32 ms. Allocated memory is still 303.0 MB. Free memory was 239.5 MB in the beginning and 235.5 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-25 11:54:36,458 INFO ]: Boogie Preprocessor took 44.72 ms. Allocated memory is still 303.0 MB. Free memory was 235.5 MB in the beginning and 233.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 11:54:36,463 INFO ]: RCFGBuilder took 410.27 ms. Allocated memory is still 303.0 MB. Free memory was 233.5 MB in the beginning and 207.5 MB in the end (delta: 25.9 MB). Peak memory consumption was 25.9 MB. Max. memory is 3.6 GB. [2018-06-25 11:54:36,463 INFO ]: TraceAbstraction took 57053.81 ms. Allocated memory was 303.0 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 207.5 MB in the beginning and 421.4 MB in the end (delta: -213.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-25 11:54:36,466 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 303.0 MB. Free memory is still 267.5 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 112.32 ms. Allocated memory is still 303.0 MB. Free memory was 239.5 MB in the beginning and 235.5 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 44.72 ms. Allocated memory is still 303.0 MB. Free memory was 235.5 MB in the beginning and 233.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 410.27 ms. Allocated memory is still 303.0 MB. Free memory was 233.5 MB in the beginning and 207.5 MB in the end (delta: 25.9 MB). Peak memory consumption was 25.9 MB. Max. memory is 3.6 GB. * TraceAbstraction took 57053.81 ms. Allocated memory was 303.0 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 207.5 MB in the beginning and 421.4 MB in the end (delta: -213.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 19 with TraceHistMax 11, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 2 quantified variables from 1 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 56.9s OverallTime, 7 OverallIterations, 11 TraceHistogramMax, 1.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 42 SDtfs, 7 SDslu, 135 SDs, 0 SdLazy, 59 SolverSat, 30 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 94 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 127 ImplicationChecksByTransitivity, 7.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=19occurred 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.2s SsaConstructionTime, 1.3s SatisfiabilityAnalysisTime, 44.8s InterpolantComputationTime, 109 NumberOfCodeBlocks, 109 NumberOfCodeBlocksAsserted, 17 NumberOfCheckSat, 98 ConstructedInterpolants, 0 QuantifiedInterpolants, 6514 SizeOfPredicates, 20 NumberOfNonLiveVariables, 1967 ConjunctsInSsa, 167 ConjunctsInUnsatCore, 11 InterpolantComputations, 1 PerfectInterpolantSequences, 0/82 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-2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_11-54-36-475.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bubblesort-2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_11-54-36-475.csv Completed graceful shutdown