java -Xss1g -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_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 13:59:28,851 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 13:59:28,853 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 13:59:28,868 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 13:59:28,868 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 13:59:28,869 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 13:59:28,870 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 13:59:28,876 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 13:59:28,878 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 13:59:28,879 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 13:59:28,879 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 13:59:28,881 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 13:59:28,882 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 13:59:28,883 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 13:59:28,884 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 13:59:28,887 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 13:59:28,889 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 13:59:28,891 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 13:59:28,903 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 13:59:28,904 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 13:59:28,905 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 13:59:28,907 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 13:59:28,907 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 13:59:28,908 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 13:59:28,908 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 13:59:28,909 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 13:59:28,910 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 13:59:28,911 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 13:59:28,916 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 13:59:28,916 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 13:59:28,916 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 13:59:28,917 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 13:59:28,917 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 13:59:28,922 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 13:59:28,922 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 13:59:28,923 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 13:59:28,938 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 13:59:28,940 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 13:59:28,940 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 13:59:28,940 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 13:59:28,941 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 13:59:28,941 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 13:59:28,941 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 13:59:28,942 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 13:59:28,942 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 13:59:28,942 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 13:59:28,942 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 13:59:28,942 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 13:59:28,943 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 13:59:28,943 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 13:59:28,943 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 13:59:28,944 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 13:59:28,944 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 13:59:28,944 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 13:59:28,944 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 13:59:28,945 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 13:59:28,945 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 13:59:28,993 INFO ]: Repository-Root is: /tmp [2018-06-22 13:59:29,008 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 13:59:29,013 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 13:59:29,014 INFO ]: Initializing SmtParser... [2018-06-22 13:59:29,014 INFO ]: SmtParser initialized [2018-06-22 13:59:29,015 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 [2018-06-22 13:59:29,016 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-22 13:59:29,102 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 unknown [2018-06-22 13:59:29,530 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 [2018-06-22 13:59:29,540 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 13:59:29,546 INFO ]: Walking toolchain with 4 elements. [2018-06-22 13:59:29,546 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 13:59:29,546 INFO ]: Initializing ChcToBoogie... [2018-06-22 13:59:29,547 INFO ]: ChcToBoogie initialized [2018-06-22 13:59:29,550 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:59:29" (1/1) ... [2018-06-22 13:59:29,602 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29 Unit [2018-06-22 13:59:29,602 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 13:59:29,602 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 13:59:29,602 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 13:59:29,602 INFO ]: Boogie Preprocessor initialized [2018-06-22 13:59:29,622 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29" (1/1) ... [2018-06-22 13:59:29,622 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29" (1/1) ... [2018-06-22 13:59:29,634 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29" (1/1) ... [2018-06-22 13:59:29,634 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29" (1/1) ... [2018-06-22 13:59:29,654 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29" (1/1) ... [2018-06-22 13:59:29,656 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29" (1/1) ... [2018-06-22 13:59:29,667 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29" (1/1) ... [2018-06-22 13:59:29,670 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 13:59:29,671 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 13:59:29,671 INFO ]: Initializing RCFGBuilder... [2018-06-22 13:59:29,671 INFO ]: RCFGBuilder initialized [2018-06-22 13:59:29,672 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29" (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-22 13:59:29,688 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 13:59:29,688 INFO ]: Found specification of procedure False [2018-06-22 13:59:29,688 INFO ]: Found implementation of procedure False [2018-06-22 13:59:29,689 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 13:59:29,689 INFO ]: Found specification of procedure state [2018-06-22 13:59:29,689 INFO ]: Found implementation of procedure state [2018-06-22 13:59:29,689 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 13:59:29,689 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 13:59:29,689 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-22 13:59:30,081 INFO ]: Using library mode [2018-06-22 13:59:30,081 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:59:30 BoogieIcfgContainer [2018-06-22 13:59:30,082 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 13:59:30,083 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 13:59:30,083 INFO ]: Initializing TraceAbstraction... [2018-06-22 13:59:30,087 INFO ]: TraceAbstraction initialized [2018-06-22 13:59:30,087 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:59:29" (1/3) ... [2018-06-22 13:59:30,088 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@27cc76dc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:59:30, skipping insertion in model container [2018-06-22 13:59:30,088 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:59:29" (2/3) ... [2018-06-22 13:59:30,088 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@27cc76dc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:59:30, skipping insertion in model container [2018-06-22 13:59:30,088 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:59:30" (3/3) ... [2018-06-22 13:59:30,090 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 13:59:30,100 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 13:59:30,111 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 13:59:30,155 INFO ]: Using default assertion order modulation [2018-06-22 13:59:30,156 INFO ]: Interprodecural is true [2018-06-22 13:59:30,156 INFO ]: Hoare is false [2018-06-22 13:59:30,156 INFO ]: Compute interpolants for FPandBP [2018-06-22 13:59:30,156 INFO ]: Backedges is TWOTRACK [2018-06-22 13:59:30,156 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 13:59:30,156 INFO ]: Difference is false [2018-06-22 13:59:30,156 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 13:59:30,156 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 13:59:30,171 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 13:59:30,181 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 13:59:30,181 INFO ]: Found error trace [2018-06-22 13:59:30,182 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 13:59:30,182 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 13:59:30,191 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 13:59:30,193 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 13:59:30,193 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 13:59:30,229 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:30,229 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 13:59:30,229 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:30,272 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:59:30,378 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 13:59:30,379 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 13:59:30,379 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 13:59:30,381 INFO ]: Interpolant automaton has 4 states [2018-06-22 13:59:30,392 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 13:59:30,392 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 13:59:30,394 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 13:59:30,529 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 13:59:30,530 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 13:59:30,531 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 13:59:30,532 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 13:59:30,532 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 13:59:30,543 INFO ]: With dead ends: 13 [2018-06-22 13:59:30,543 INFO ]: Without dead ends: 13 [2018-06-22 13:59:30,545 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 13:59:30,557 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 13:59:30,577 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 13:59:30,579 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 13:59:30,579 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 13:59:30,580 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 13:59:30,580 INFO ]: Finished accepts. word is rejected. [2018-06-22 13:59:30,580 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 13:59:30,580 INFO ]: Interpolant automaton has 4 states. [2018-06-22 13:59:30,580 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 13:59:30,581 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 13:59:30,581 INFO ]: Found error trace [2018-06-22 13:59:30,581 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 13:59:30,582 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 13:59:30,582 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 13:59:30,582 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 13:59:30,582 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 13:59:30,582 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:30,582 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 13:59:30,582 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:30,711 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:59:31,215 WARN ]: Spent 223.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 13:59:31,432 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 13:59:31,432 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 13:59:31,432 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-22 13:59:31,444 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 13:59:31,514 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:59:31,526 INFO ]: Computing forward predicates... [2018-06-22 13:59:33,562 WARN ]: Spent 1.30 s on a formula simplification. DAG size of input: 35 DAG size of output: 26 [2018-06-22 13:59:33,711 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 13:59:33,733 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 13:59:33,733 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 13:59:33,734 INFO ]: Interpolant automaton has 9 states [2018-06-22 13:59:33,734 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 13:59:33,734 INFO ]: CoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2018-06-22 13:59:33,734 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 13:59:33,946 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 19 [2018-06-22 13:59:33,982 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 13:59:33,982 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 13:59:33,983 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 13:59:33,983 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 13:59:33,983 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 13:59:33,983 INFO ]: With dead ends: 15 [2018-06-22 13:59:33,983 INFO ]: Without dead ends: 15 [2018-06-22 13:59:33,984 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2018-06-22 13:59:33,984 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 13:59:33,987 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 13:59:33,987 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 13:59:33,987 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 13:59:33,987 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 13:59:33,987 INFO ]: Finished accepts. word is rejected. [2018-06-22 13:59:33,988 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 13:59:33,988 INFO ]: Interpolant automaton has 9 states. [2018-06-22 13:59:33,988 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 13:59:33,988 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 13:59:33,988 INFO ]: Found error trace [2018-06-22 13:59:33,988 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 13:59:33,988 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 13:59:33,988 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 13:59:33,988 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 13:59:33,988 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 13:59:33,989 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:33,989 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 13:59:33,989 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:34,065 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:59:34,329 WARN ]: Spent 127.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 13:59:34,563 WARN ]: Spent 189.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 13:59:34,701 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 13:59:34,701 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 13:59:34,702 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-22 13:59:34,709 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 13:59:34,781 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 13:59:34,781 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:59:34,787 INFO ]: Computing forward predicates... [2018-06-22 13:59:35,677 WARN ]: Spent 388.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 31 [2018-06-22 13:59:36,214 INFO ]: Checked inductivity of 10 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-22 13:59:36,247 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 13:59:36,247 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 11 [2018-06-22 13:59:36,247 INFO ]: Interpolant automaton has 11 states [2018-06-22 13:59:36,247 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 13:59:36,247 INFO ]: CoverageRelationStatistics Valid=33, Invalid=77, Unknown=0, NotChecked=0, Total=110 [2018-06-22 13:59:36,248 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 13:59:36,563 WARN ]: Spent 147.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 22 [2018-06-22 13:59:36,783 WARN ]: Spent 200.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 26 [2018-06-22 13:59:36,803 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 13:59:36,803 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 13:59:36,804 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 13:59:36,804 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 13:59:36,804 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 13:59:36,805 INFO ]: With dead ends: 19 [2018-06-22 13:59:36,805 INFO ]: Without dead ends: 19 [2018-06-22 13:59:36,805 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=56, Invalid=126, Unknown=0, NotChecked=0, Total=182 [2018-06-22 13:59:36,805 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 13:59:36,808 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 13:59:36,808 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 13:59:36,809 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 13:59:36,809 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-22 13:59:36,809 INFO ]: Finished accepts. word is rejected. [2018-06-22 13:59:36,809 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 13:59:36,809 INFO ]: Interpolant automaton has 11 states. [2018-06-22 13:59:36,809 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 13:59:36,809 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 13:59:36,809 INFO ]: Found error trace [2018-06-22 13:59:36,810 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 13:59:36,810 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 13:59:36,810 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 3 times [2018-06-22 13:59:36,810 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 13:59:36,810 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 13:59:36,810 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:36,810 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 13:59:36,810 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:37,007 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:59:37,404 WARN ]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 13:59:37,524 WARN ]: Spent 114.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 22 [2018-06-22 13:59:37,779 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 13:59:37,779 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 13:59:37,779 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-22 13:59:37,794 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 13:59:37,915 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 13:59:37,915 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:59:37,924 INFO ]: Computing forward predicates... [2018-06-22 13:59:38,549 WARN ]: Spent 265.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 31 [2018-06-22 13:59:42,378 WARN ]: Spent 2.82 s on a formula simplification. DAG size of input: 320 DAG size of output: 49 [2018-06-22 13:59:43,690 WARN ]: Spent 788.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 62 [2018-06-22 13:59:45,122 WARN ]: Spent 604.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 51 [2018-06-22 13:59:45,381 INFO ]: Checked inductivity of 36 backedges. 3 proven. 23 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 13:59:45,428 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 13:59:45,428 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2018-06-22 13:59:45,428 INFO ]: Interpolant automaton has 19 states [2018-06-22 13:59:45,428 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 13:59:45,428 INFO ]: CoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2018-06-22 13:59:45,429 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 19 states. [2018-06-22 13:59:47,061 WARN ]: Spent 1.52 s on a formula simplification. DAG size of input: 130 DAG size of output: 117 [2018-06-22 13:59:47,296 WARN ]: Spent 179.00 ms on a formula simplification. DAG size of input: 124 DAG size of output: 23 [2018-06-22 13:59:47,662 WARN ]: Spent 327.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 20 [2018-06-22 13:59:47,965 WARN ]: Spent 266.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 38 [2018-06-22 13:59:48,855 WARN ]: Spent 837.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 95 [2018-06-22 13:59:48,964 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 13:59:48,964 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 13:59:48,966 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 13:59:48,966 INFO ]: Start accepts. Automaton has 19 states. Word has length 25 [2018-06-22 13:59:48,967 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 13:59:48,967 INFO ]: With dead ends: 21 [2018-06-22 13:59:48,967 INFO ]: Without dead ends: 21 [2018-06-22 13:59:48,968 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 18 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 73 ImplicationChecksByTransitivity, 9.2s TimeCoverageRelationStatistics Valid=137, Invalid=415, Unknown=0, NotChecked=0, Total=552 [2018-06-22 13:59:48,968 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 13:59:48,971 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 13:59:48,971 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 13:59:48,972 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 13:59:48,972 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 13:59:48,972 INFO ]: Finished accepts. word is rejected. [2018-06-22 13:59:48,972 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 13:59:48,972 INFO ]: Interpolant automaton has 19 states. [2018-06-22 13:59:48,972 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 13:59:48,973 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 13:59:48,973 INFO ]: Found error trace [2018-06-22 13:59:48,973 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 13:59:48,973 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 13:59:48,973 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 4 times [2018-06-22 13:59:48,973 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 13:59:48,973 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 13:59:48,974 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:48,974 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 13:59:48,974 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 13:59:49,210 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:59:49,654 WARN ]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 13:59:50,172 WARN ]: Spent 473.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-22 13:59:50,563 WARN ]: Spent 266.00 ms on a formula simplification. DAG size of input: 137 DAG size of output: 60 [2018-06-22 13:59:50,896 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 26 [2018-06-22 13:59:50,978 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 13:59:50,978 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 13:59:50,978 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-22 13:59:50,984 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 13:59:51,093 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 13:59:51,093 INFO ]: Conjunction of SSA is unsat [2018-06-22 13:59:51,105 INFO ]: Computing forward predicates... [2018-06-22 13:59:52,168 WARN ]: Spent 493.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 45 [2018-06-22 13:59:57,451 WARN ]: Spent 3.85 s on a formula simplification. DAG size of input: 442 DAG size of output: 51 [2018-06-22 13:59:58,654 WARN ]: Spent 910.00 ms on a formula simplification. DAG size of input: 164 DAG size of output: 71 [2018-06-22 14:00:00,729 WARN ]: Spent 1.59 s on a formula simplification. DAG size of input: 235 DAG size of output: 88 [2018-06-22 14:00:01,801 WARN ]: Spent 606.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 59 [2018-06-22 14:00:01,995 INFO ]: Checked inductivity of 55 backedges. 3 proven. 37 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 14:00:02,016 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:00:02,016 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 22 [2018-06-22 14:00:02,016 INFO ]: Interpolant automaton has 22 states [2018-06-22 14:00:02,016 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-22 14:00:02,017 INFO ]: CoverageRelationStatistics Valid=82, Invalid=380, Unknown=0, NotChecked=0, Total=462 [2018-06-22 14:00:02,017 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 22 states. [2018-06-22 14:00:03,707 WARN ]: Spent 1.64 s on a formula simplification. DAG size of input: 162 DAG size of output: 144 [2018-06-22 14:00:03,977 WARN ]: Spent 194.00 ms on a formula simplification. DAG size of input: 156 DAG size of output: 35 [2018-06-22 14:00:04,190 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 157 DAG size of output: 30 [2018-06-22 14:00:04,463 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 156 DAG size of output: 46 [2018-06-22 14:00:04,782 WARN ]: Spent 264.00 ms on a formula simplification. DAG size of input: 158 DAG size of output: 37 [2018-06-22 14:00:05,239 WARN ]: Spent 376.00 ms on a formula simplification. DAG size of input: 159 DAG size of output: 53 [2018-06-22 14:00:05,298 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:00:05,298 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 14:00:05,304 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 14:00:05,304 INFO ]: Start accepts. Automaton has 22 states. Word has length 29 [2018-06-22 14:00:05,304 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:00:05,305 INFO ]: With dead ends: 23 [2018-06-22 14:00:05,305 INFO ]: Without dead ends: 23 [2018-06-22 14:00:05,306 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 20 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 114 ImplicationChecksByTransitivity, 13.3s TimeCoverageRelationStatistics Valid=176, Invalid=580, Unknown=0, NotChecked=0, Total=756 [2018-06-22 14:00:05,306 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 14:00:05,310 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 14:00:05,310 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 14:00:05,310 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 14:00:05,310 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 14:00:05,311 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:00:05,311 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 14:00:05,311 INFO ]: Interpolant automaton has 22 states. [2018-06-22 14:00:05,311 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 14:00:05,311 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 14:00:05,311 INFO ]: Found error trace [2018-06-22 14:00:05,311 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:00:05,312 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:00:05,314 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 5 times [2018-06-22 14:00:05,314 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:00:05,314 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:00:05,315 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:00:05,315 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:00:05,315 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:00:05,570 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:00:05,908 WARN ]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 14:00:06,451 WARN ]: Spent 492.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 13 [2018-06-22 14:00:06,996 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 14:00:06,996 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:00:06,996 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-22 14:00:07,002 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 14:00:07,136 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-06-22 14:00:07,136 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:00:07,148 INFO ]: Computing forward predicates... [2018-06-22 14:00:07,463 WARN ]: Spent 210.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 31 [2018-06-22 14:00:08,702 WARN ]: Spent 658.00 ms on a formula simplification. DAG size of input: 131 DAG size of output: 62 [2018-06-22 14:00:10,041 WARN ]: Spent 1.03 s on a formula simplification. DAG size of input: 172 DAG size of output: 79 [2018-06-22 14:00:12,054 WARN ]: Spent 1.63 s on a formula simplification. DAG size of input: 237 DAG size of output: 88 [2018-06-22 14:00:12,751 WARN ]: Spent 446.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 59 [2018-06-22 14:00:12,982 INFO ]: Checked inductivity of 78 backedges. 9 proven. 47 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-22 14:00:13,014 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:00:13,014 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 26 [2018-06-22 14:00:13,015 INFO ]: Interpolant automaton has 26 states [2018-06-22 14:00:13,015 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 14:00:13,015 INFO ]: CoverageRelationStatistics Valid=105, Invalid=545, Unknown=0, NotChecked=0, Total=650 [2018-06-22 14:00:13,015 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 26 states. [2018-06-22 14:00:14,059 WARN ]: Spent 987.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 111 [2018-06-22 14:00:14,420 WARN ]: Spent 175.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 37 [2018-06-22 14:00:14,611 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 30 [2018-06-22 14:00:14,828 WARN ]: Spent 177.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 36 [2018-06-22 14:00:15,020 WARN ]: Spent 154.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 32 [2018-06-22 14:00:15,251 WARN ]: Spent 184.00 ms on a formula simplification. DAG size of input: 135 DAG size of output: 39 [2018-06-22 14:00:16,127 WARN ]: Spent 822.00 ms on a formula simplification. DAG size of input: 136 DAG size of output: 82 [2018-06-22 14:00:16,180 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:00:16,180 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 14:00:16,180 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 14:00:16,180 INFO ]: Start accepts. Automaton has 26 states. Word has length 33 [2018-06-22 14:00:16,180 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:00:16,181 INFO ]: With dead ends: 25 [2018-06-22 14:00:16,181 INFO ]: Without dead ends: 25 [2018-06-22 14:00:16,182 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 112 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=227, Invalid=829, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 14:00:16,182 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 14:00:16,184 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 14:00:16,184 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 14:00:16,185 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 14:00:16,185 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 14:00:16,185 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:00:16,185 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 14:00:16,185 INFO ]: Interpolant automaton has 26 states. [2018-06-22 14:00:16,185 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 14:00:16,186 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 14:00:16,186 INFO ]: Found error trace [2018-06-22 14:00:16,186 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:00:16,186 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:00:16,186 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 6 times [2018-06-22 14:00:16,186 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:00:16,186 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:00:16,187 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:00:16,187 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:00:16,187 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:00:16,446 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:00:16,874 WARN ]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 14:00:17,273 WARN ]: Spent 354.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 14:00:17,554 WARN ]: Spent 144.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 52 [2018-06-22 14:00:17,784 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 55 [2018-06-22 14:00:18,158 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 14:00:18,158 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 14:00:18,158 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-22 14:00:18,164 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 14:00:18,454 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2018-06-22 14:00:18,454 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:00:18,471 INFO ]: Computing forward predicates... [2018-06-22 14:00:18,789 WARN ]: Spent 213.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 31 [2018-06-22 14:00:19,427 WARN ]: Spent 485.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 51 [2018-06-22 14:00:20,226 WARN ]: Spent 632.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 60 [2018-06-22 14:00:21,327 WARN ]: Spent 814.00 ms on a formula simplification. DAG size of input: 146 DAG size of output: 71 [2018-06-22 14:00:22,665 WARN ]: Spent 879.00 ms on a formula simplification. DAG size of input: 148 DAG size of output: 75 [2018-06-22 14:00:23,824 WARN ]: Spent 785.00 ms on a formula simplification. DAG size of input: 148 DAG size of output: 71 [2018-06-22 14:00:24,505 WARN ]: Spent 515.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 51 [2018-06-22 14:00:24,773 INFO ]: Checked inductivity of 105 backedges. 14 proven. 63 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 14:00:24,793 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 14:00:24,793 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 31 [2018-06-22 14:00:24,794 INFO ]: Interpolant automaton has 31 states [2018-06-22 14:00:24,794 INFO ]: Constructing interpolant automaton starting with 31 interpolants. [2018-06-22 14:00:24,795 INFO ]: CoverageRelationStatistics Valid=164, Invalid=766, Unknown=0, NotChecked=0, Total=930 [2018-06-22 14:00:24,795 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 31 states. [2018-06-22 14:00:26,267 WARN ]: Spent 1.43 s on a formula simplification. DAG size of input: 119 DAG size of output: 103 [2018-06-22 14:00:26,433 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 33 [2018-06-22 14:00:26,573 WARN ]: Spent 110.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 34 [2018-06-22 14:00:26,830 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 26 [2018-06-22 14:00:26,989 WARN ]: Spent 120.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 36 [2018-06-22 14:00:27,266 WARN ]: Spent 241.00 ms on a formula simplification. DAG size of input: 119 DAG size of output: 42 [2018-06-22 14:00:27,774 WARN ]: Spent 466.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 66 [2018-06-22 14:00:27,829 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 14:00:27,829 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-22 14:00:27,832 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-22 14:00:27,832 INFO ]: Start accepts. Automaton has 31 states. Word has length 37 [2018-06-22 14:00:27,833 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 14:00:27,833 INFO ]: With dead ends: 27 [2018-06-22 14:00:27,833 INFO ]: Without dead ends: 27 [2018-06-22 14:00:27,834 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 217 ImplicationChecksByTransitivity, 9.4s TimeCoverageRelationStatistics Valid=338, Invalid=1144, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 14:00:27,834 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-22 14:00:27,840 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-22 14:00:27,840 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-22 14:00:27,841 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-22 14:00:27,841 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 37 [2018-06-22 14:00:27,841 INFO ]: Finished accepts. word is rejected. [2018-06-22 14:00:27,841 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-22 14:00:27,841 INFO ]: Interpolant automaton has 31 states. [2018-06-22 14:00:27,841 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-22 14:00:27,841 INFO ]: Finished isEmpty. Found accepting run of length 42 [2018-06-22 14:00:27,841 INFO ]: Found error trace [2018-06-22 14:00:27,842 INFO ]: trace histogram [9, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 14:00:27,842 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 14:00:27,842 INFO ]: Analyzing trace with hash -544278078, now seen corresponding path program 7 times [2018-06-22 14:00:27,842 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 14:00:27,842 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 14:00:27,843 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:00:27,843 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 14:00:27,843 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 14:00:28,144 INFO ]: Conjunction of SSA is unsat [2018-06-22 14:00:28,588 WARN ]: Spent 120.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 14:00:28,988 WARN ]: Spent 352.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 22 [2018-06-22 14:00:29,369 WARN ]: Spent 261.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 60 [2018-06-22 14:00:29,528 WARN ]: Spent 137.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 63 Received shutdown request... [2018-06-22 14:00:29,731 WARN ]: Verification canceled [2018-06-22 14:00:29,735 WARN ]: Timeout [2018-06-22 14:00:29,735 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 02:00:29 BoogieIcfgContainer [2018-06-22 14:00:29,735 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 14:00:29,736 INFO ]: Toolchain (without parser) took 60195.41 ms. Allocated memory was 309.3 MB in the beginning and 1.3 GB in the end (delta: 991.4 MB). Free memory was 248.9 MB in the beginning and 1.0 GB in the end (delta: -778.2 MB). Peak memory consumption was 213.2 MB. Max. memory is 3.6 GB. [2018-06-22 14:00:29,736 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 274.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 14:00:29,737 INFO ]: ChcToBoogie took 55.58 ms. Allocated memory is still 309.3 MB. Free memory was 248.9 MB in the beginning and 244.9 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-22 14:00:29,737 INFO ]: Boogie Preprocessor took 67.93 ms. Allocated memory is still 309.3 MB. Free memory is still 244.9 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 14:00:29,737 INFO ]: RCFGBuilder took 410.90 ms. Allocated memory is still 309.3 MB. Free memory was 244.9 MB in the beginning and 223.0 MB in the end (delta: 21.9 MB). Peak memory consumption was 21.9 MB. Max. memory is 3.6 GB. [2018-06-22 14:00:29,738 INFO ]: TraceAbstraction took 59651.69 ms. Allocated memory was 309.3 MB in the beginning and 1.3 GB in the end (delta: 991.4 MB). Free memory was 223.0 MB in the beginning and 1.0 GB in the end (delta: -804.1 MB). Peak memory consumption was 187.3 MB. Max. memory is 3.6 GB. [2018-06-22 14:00:29,741 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 309.3 MB. Free memory is still 274.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 55.58 ms. Allocated memory is still 309.3 MB. Free memory was 248.9 MB in the beginning and 244.9 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 67.93 ms. Allocated memory is still 309.3 MB. Free memory is still 244.9 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 410.90 ms. Allocated memory is still 309.3 MB. Free memory was 244.9 MB in the beginning and 223.0 MB in the end (delta: 21.9 MB). Peak memory consumption was 21.9 MB. Max. memory is 3.6 GB. * TraceAbstraction took 59651.69 ms. Allocated memory was 309.3 MB in the beginning and 1.3 GB in the end (delta: 991.4 MB). Free memory was 223.0 MB in the beginning and 1.0 GB in the end (delta: -804.1 MB). Peak memory consumption was 187.3 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 42 with TraceHistMax 9, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateComparison was comparing new predicate (quantifier-free) to 14 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 59.5s OverallTime, 8 OverallIterations, 9 TraceHistogramMax, 14.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 89 SDtfs, 159 SDslu, 466 SDs, 0 SdLazy, 409 SolverSat, 192 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 256 GetRequests, 113 SyntacticMatches, 5 SemanticMatches, 138 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 532 ImplicationChecksByTransitivity, 44.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=27occurred in iteration=7, 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, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 1.7s SatisfiabilityAnalysisTime, 41.2s InterpolantComputationTime, 317 NumberOfCodeBlocks, 317 NumberOfCodeBlocksAsserted, 31 NumberOfCheckSat, 304 ConstructedInterpolants, 0 QuantifiedInterpolants, 290412 SizeOfPredicates, 1640 NumberOfNonLiveVariables, 2148 ConjunctsInSsa, 246 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 187/574 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_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_14-00-29-750.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bubblesort_init-1.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_14-00-29-750.csv Completed graceful shutdown