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_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 04:17:56,758 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 04:17:56,761 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 04:17:56,776 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 04:17:56,776 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 04:17:56,777 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 04:17:56,781 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 04:17:56,783 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 04:17:56,784 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 04:17:56,785 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 04:17:56,787 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 04:17:56,787 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 04:17:56,788 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 04:17:56,789 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 04:17:56,790 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 04:17:56,793 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 04:17:56,795 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 04:17:56,808 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 04:17:56,809 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 04:17:56,810 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 04:17:56,811 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 04:17:56,814 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 04:17:56,814 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 04:17:56,814 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 04:17:56,815 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 04:17:56,822 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 04:17:56,823 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 04:17:56,823 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 04:17:56,824 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 04:17:56,824 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 04:17:56,825 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 04:17:56,831 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 04:17:56,831 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 04:17:56,832 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 04:17:56,833 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 04:17:56,833 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 04:17:56,857 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 04:17:56,858 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 04:17:56,858 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 04:17:56,858 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 04:17:56,859 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 04:17:56,859 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 04:17:56,860 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 04:17:56,860 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 04:17:56,860 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:17:56,860 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 04:17:56,860 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 04:17:56,861 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 04:17:56,863 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 04:17:56,864 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 04:17:56,864 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 04:17:56,864 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 04:17:56,864 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 04:17:56,866 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 04:17:56,866 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 04:17:56,915 INFO ]: Repository-Root is: /tmp [2018-06-22 04:17:56,934 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 04:17:56,938 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 04:17:56,940 INFO ]: Initializing SmtParser... [2018-06-22 04:17:56,940 INFO ]: SmtParser initialized [2018-06-22 04:17:56,941 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 [2018-06-22 04:17:56,942 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 04:17:57,030 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 unknown [2018-06-22 04:17:57,452 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort_init-1.smt2 [2018-06-22 04:17:57,458 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 04:17:57,464 INFO ]: Walking toolchain with 4 elements. [2018-06-22 04:17:57,464 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 04:17:57,464 INFO ]: Initializing ChcToBoogie... [2018-06-22 04:17:57,465 INFO ]: ChcToBoogie initialized [2018-06-22 04:17:57,468 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:17:57" (1/1) ... [2018-06-22 04:17:57,535 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57 Unit [2018-06-22 04:17:57,535 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 04:17:57,535 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 04:17:57,535 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 04:17:57,535 INFO ]: Boogie Preprocessor initialized [2018-06-22 04:17:57,556 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57" (1/1) ... [2018-06-22 04:17:57,556 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57" (1/1) ... [2018-06-22 04:17:57,577 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57" (1/1) ... [2018-06-22 04:17:57,577 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57" (1/1) ... [2018-06-22 04:17:57,595 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57" (1/1) ... [2018-06-22 04:17:57,597 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57" (1/1) ... [2018-06-22 04:17:57,607 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57" (1/1) ... [2018-06-22 04:17:57,611 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 04:17:57,612 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 04:17:57,612 INFO ]: Initializing RCFGBuilder... [2018-06-22 04:17:57,612 INFO ]: RCFGBuilder initialized [2018-06-22 04:17:57,613 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57" (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 04:17:57,630 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 04:17:57,630 INFO ]: Found specification of procedure gotoProc [2018-06-22 04:17:57,631 INFO ]: Found implementation of procedure gotoProc [2018-06-22 04:17:57,631 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 04:17:57,631 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 04:17:57,631 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 04:17:58,075 INFO ]: Using library mode [2018-06-22 04:17:58,076 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:17:58 BoogieIcfgContainer [2018-06-22 04:17:58,077 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 04:17:58,079 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 04:17:58,079 INFO ]: Initializing TraceAbstraction... [2018-06-22 04:17:58,086 INFO ]: TraceAbstraction initialized [2018-06-22 04:17:58,086 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:17:57" (1/3) ... [2018-06-22 04:17:58,087 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6f6b53c5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:17:58, skipping insertion in model container [2018-06-22 04:17:58,087 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:17:57" (2/3) ... [2018-06-22 04:17:58,087 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6f6b53c5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:17:58, skipping insertion in model container [2018-06-22 04:17:58,087 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:17:58" (3/3) ... [2018-06-22 04:17:58,089 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 04:17:58,098 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 04:17:58,109 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 04:17:58,161 INFO ]: Using default assertion order modulation [2018-06-22 04:17:58,161 INFO ]: Interprodecural is true [2018-06-22 04:17:58,161 INFO ]: Hoare is false [2018-06-22 04:17:58,161 INFO ]: Compute interpolants for FPandBP [2018-06-22 04:17:58,161 INFO ]: Backedges is TWOTRACK [2018-06-22 04:17:58,161 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 04:17:58,161 INFO ]: Difference is false [2018-06-22 04:17:58,161 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 04:17:58,161 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 04:17:58,175 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 04:17:58,183 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 04:17:58,183 INFO ]: Found error trace [2018-06-22 04:17:58,184 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:17:58,184 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:17:58,188 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 04:17:58,189 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:17:58,190 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:17:58,225 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:17:58,225 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:17:58,225 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:17:58,292 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:17:58,400 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:17:58,403 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 04:17:58,403 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 04:17:58,405 INFO ]: Interpolant automaton has 3 states [2018-06-22 04:17:58,418 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 04:17:58,419 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:17:58,421 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 04:17:58,493 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:17:58,493 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 04:17:58,494 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 04:17:58,495 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 04:17:58,496 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:17:58,504 INFO ]: With dead ends: 9 [2018-06-22 04:17:58,504 INFO ]: Without dead ends: 9 [2018-06-22 04:17:58,506 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-22 04:17:58,522 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 04:17:58,541 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 04:17:58,542 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 04:17:58,542 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 04:17:58,544 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 04:17:58,544 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:17:58,544 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 04:17:58,544 INFO ]: Interpolant automaton has 3 states. [2018-06-22 04:17:58,544 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 04:17:58,544 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 04:17:58,544 INFO ]: Found error trace [2018-06-22 04:17:58,544 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:17:58,545 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:17:58,545 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 04:17:58,545 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:17:58,545 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:17:58,547 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:17:58,547 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:17:58,547 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:17:58,654 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:17:58,912 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:17:58,912 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:17:58,912 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 04:17:58,922 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:17:59,013 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:17:59,033 INFO ]: Computing forward predicates... [2018-06-22 04:18:00,333 WARN ]: Spent 549.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 13 [2018-06-22 04:18:00,346 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:00,368 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:18:00,368 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-22 04:18:00,369 INFO ]: Interpolant automaton has 6 states [2018-06-22 04:18:00,369 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 04:18:00,369 INFO ]: CoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 04:18:00,369 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 6 states. [2018-06-22 04:18:00,432 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:18:00,432 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 04:18:00,432 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 04:18:00,432 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-22 04:18:00,432 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:18:00,433 INFO ]: With dead ends: 11 [2018-06-22 04:18:00,433 INFO ]: Without dead ends: 11 [2018-06-22 04:18:00,433 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-22 04:18:00,434 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 04:18:00,435 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 04:18:00,435 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 04:18:00,435 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 04:18:00,435 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-22 04:18:00,435 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:18:00,435 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 04:18:00,435 INFO ]: Interpolant automaton has 6 states. [2018-06-22 04:18:00,435 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 04:18:00,435 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 04:18:00,436 INFO ]: Found error trace [2018-06-22 04:18:00,436 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:18:00,436 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:18:00,436 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 2 times [2018-06-22 04:18:00,436 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:18:00,436 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:18:00,436 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:00,436 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:18:00,437 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:00,628 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:01,107 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:01,107 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:18:01,107 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) [2018-06-22 04:18:01,124 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:18:01,250 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 04:18:01,250 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:01,261 INFO ]: Computing forward predicates... [2018-06-22 04:18:01,980 WARN ]: Spent 256.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 13 [2018-06-22 04:18:04,458 WARN ]: Spent 926.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 10 [2018-06-22 04:18:04,460 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:04,482 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:18:04,482 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-22 04:18:04,482 INFO ]: Interpolant automaton has 10 states [2018-06-22 04:18:04,482 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 04:18:04,482 INFO ]: CoverageRelationStatistics Valid=37, Invalid=53, Unknown=0, NotChecked=0, Total=90 [2018-06-22 04:18:04,482 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 10 states. [2018-06-22 04:18:04,506 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:18:04,506 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 04:18:04,506 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 04:18:04,506 INFO ]: Start accepts. Automaton has 10 states. Word has length 10 [2018-06-22 04:18:04,506 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:18:04,506 INFO ]: With dead ends: 12 [2018-06-22 04:18:04,507 INFO ]: Without dead ends: 12 [2018-06-22 04:18:04,507 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=37, Invalid=53, Unknown=0, NotChecked=0, Total=90 [2018-06-22 04:18:04,507 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 04:18:04,508 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 04:18:04,508 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 04:18:04,509 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 04:18:04,509 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-22 04:18:04,509 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:18:04,509 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 04:18:04,509 INFO ]: Interpolant automaton has 10 states. [2018-06-22 04:18:04,509 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 04:18:04,510 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 04:18:04,510 INFO ]: Found error trace [2018-06-22 04:18:04,510 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:18:04,510 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:18:04,510 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 3 times [2018-06-22 04:18:04,510 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:18:04,510 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:18:04,511 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:04,511 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:18:04,511 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:04,725 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:05,098 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:05,098 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:18:05,098 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 04:18:05,104 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 04:18:05,243 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 04:18:05,243 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:05,256 INFO ]: Computing forward predicates... [2018-06-22 04:18:06,042 WARN ]: Spent 140.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 13 [2018-06-22 04:18:06,829 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 20 [2018-06-22 04:18:08,964 WARN ]: Spent 759.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 12 [2018-06-22 04:18:08,983 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:09,017 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:18:09,017 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-22 04:18:09,017 INFO ]: Interpolant automaton has 12 states [2018-06-22 04:18:09,017 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 04:18:09,017 INFO ]: CoverageRelationStatistics Valid=52, Invalid=80, Unknown=0, NotChecked=0, Total=132 [2018-06-22 04:18:09,018 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 12 states. [2018-06-22 04:18:09,666 WARN ]: Spent 427.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 23 [2018-06-22 04:18:09,722 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:18:09,722 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 04:18:09,723 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 04:18:09,723 INFO ]: Start accepts. Automaton has 12 states. Word has length 11 [2018-06-22 04:18:09,723 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:18:09,723 INFO ]: With dead ends: 14 [2018-06-22 04:18:09,723 INFO ]: Without dead ends: 14 [2018-06-22 04:18:09,724 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=72, Invalid=110, Unknown=0, NotChecked=0, Total=182 [2018-06-22 04:18:09,724 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 04:18:09,725 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 04:18:09,725 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 04:18:09,726 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 04:18:09,726 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 11 [2018-06-22 04:18:09,726 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:18:09,726 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 04:18:09,726 INFO ]: Interpolant automaton has 12 states. [2018-06-22 04:18:09,726 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 04:18:09,726 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 04:18:09,726 INFO ]: Found error trace [2018-06-22 04:18:09,726 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:18:09,726 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:18:09,727 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 4 times [2018-06-22 04:18:09,727 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:18:09,727 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:18:09,727 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:09,727 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:18:09,727 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:10,030 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:10,754 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 11 [2018-06-22 04:18:10,844 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:10,844 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:18:10,844 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 04:18:10,852 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 04:18:11,065 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 04:18:11,065 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:11,076 INFO ]: Computing forward predicates... [2018-06-22 04:18:13,235 WARN ]: Spent 855.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 28 [2018-06-22 04:18:15,483 WARN ]: Spent 942.00 ms on a formula simplification. DAG size of input: 204 DAG size of output: 36 [2018-06-22 04:18:18,423 WARN ]: Spent 429.00 ms on a formula simplification. DAG size of input: 155 DAG size of output: 22 [2018-06-22 04:18:18,759 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:18,783 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:18:18,783 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-06-22 04:18:18,783 INFO ]: Interpolant automaton has 16 states [2018-06-22 04:18:18,784 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-22 04:18:18,784 INFO ]: CoverageRelationStatistics Valid=76, Invalid=164, Unknown=0, NotChecked=0, Total=240 [2018-06-22 04:18:18,784 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 16 states. [2018-06-22 04:18:18,969 WARN ]: Spent 159.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 30 [2018-06-22 04:18:19,195 WARN ]: Spent 208.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 36 [2018-06-22 04:18:19,367 WARN ]: Spent 121.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 37 [2018-06-22 04:18:19,762 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:18:19,762 INFO ]: Finished difference Result 18 states and 18 transitions. [2018-06-22 04:18:19,762 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 04:18:19,762 INFO ]: Start accepts. Automaton has 16 states. Word has length 13 [2018-06-22 04:18:19,762 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:18:19,762 INFO ]: With dead ends: 18 [2018-06-22 04:18:19,762 INFO ]: Without dead ends: 18 [2018-06-22 04:18:19,763 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 137 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=183, Invalid=369, Unknown=0, NotChecked=0, Total=552 [2018-06-22 04:18:19,763 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-22 04:18:19,765 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-06-22 04:18:19,765 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-22 04:18:19,765 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 18 transitions. [2018-06-22 04:18:19,765 INFO ]: Start accepts. Automaton has 18 states and 18 transitions. Word has length 13 [2018-06-22 04:18:19,765 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:18:19,765 INFO ]: Abstraction has 18 states and 18 transitions. [2018-06-22 04:18:19,765 INFO ]: Interpolant automaton has 16 states. [2018-06-22 04:18:19,765 INFO ]: Start isEmpty. Operand 18 states and 18 transitions. [2018-06-22 04:18:19,766 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 04:18:19,766 INFO ]: Found error trace [2018-06-22 04:18:19,766 INFO ]: trace histogram [10, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:18:19,766 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:18:19,766 INFO ]: Analyzing trace with hash -301900562, now seen corresponding path program 5 times [2018-06-22 04:18:19,766 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:18:19,766 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:18:19,769 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:19,769 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:18:19,769 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:20,250 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:21,465 WARN ]: Spent 676.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 10 [2018-06-22 04:18:21,659 WARN ]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 04:18:22,257 INFO ]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:22,258 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:18:22,258 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 04:18:22,270 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 04:18:22,563 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 04:18:22,563 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:22,581 INFO ]: Computing forward predicates... [2018-06-22 04:18:24,923 WARN ]: Spent 765.00 ms on a formula simplification. DAG size of input: 169 DAG size of output: 21 [2018-06-22 04:18:26,689 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 19 [2018-06-22 04:18:27,268 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 76 DAG size of output: 20 [2018-06-22 04:18:28,844 WARN ]: Spent 884.00 ms on a formula simplification. DAG size of input: 234 DAG size of output: 17 [2018-06-22 04:18:30,278 WARN ]: Spent 859.00 ms on a formula simplification. DAG size of input: 225 DAG size of output: 30 [2018-06-22 04:18:30,991 WARN ]: Spent 275.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 27 [2018-06-22 04:18:31,214 INFO ]: Checked inductivity of 55 backedges. 0 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:31,237 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:18:31,237 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 24 [2018-06-22 04:18:31,238 INFO ]: Interpolant automaton has 24 states [2018-06-22 04:18:31,238 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 04:18:31,238 INFO ]: CoverageRelationStatistics Valid=128, Invalid=424, Unknown=0, NotChecked=0, Total=552 [2018-06-22 04:18:31,238 INFO ]: Start difference. First operand 18 states and 18 transitions. Second operand 24 states. [2018-06-22 04:18:31,392 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 38 [2018-06-22 04:18:31,673 WARN ]: Spent 260.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 46 [2018-06-22 04:18:31,921 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 43 [2018-06-22 04:18:32,163 WARN ]: Spent 217.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 39 [2018-06-22 04:18:32,402 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 36 [2018-06-22 04:18:32,591 WARN ]: Spent 163.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 37 [2018-06-22 04:18:32,753 WARN ]: Spent 137.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 34 [2018-06-22 04:18:33,033 WARN ]: Spent 148.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 36 [2018-06-22 04:18:33,035 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:18:33,035 INFO ]: Finished difference Result 19 states and 19 transitions. [2018-06-22 04:18:33,035 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 04:18:33,035 INFO ]: Start accepts. Automaton has 24 states. Word has length 17 [2018-06-22 04:18:33,035 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:18:33,035 INFO ]: With dead ends: 19 [2018-06-22 04:18:33,035 INFO ]: Without dead ends: 19 [2018-06-22 04:18:33,036 INFO ]: 0 DeclaredPredicates, 38 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 300 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=295, Invalid=761, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 04:18:33,036 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 04:18:33,037 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 04:18:33,038 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 04:18:33,039 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-06-22 04:18:33,039 INFO ]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 17 [2018-06-22 04:18:33,039 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:18:33,039 INFO ]: Abstraction has 19 states and 19 transitions. [2018-06-22 04:18:33,039 INFO ]: Interpolant automaton has 24 states. [2018-06-22 04:18:33,039 INFO ]: Start isEmpty. Operand 19 states and 19 transitions. [2018-06-22 04:18:33,039 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-22 04:18:33,039 INFO ]: Found error trace [2018-06-22 04:18:33,039 INFO ]: trace histogram [11, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:18:33,039 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:18:33,039 INFO ]: Analyzing trace with hash -768154313, now seen corresponding path program 6 times [2018-06-22 04:18:33,040 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:18:33,040 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:18:33,040 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:33,040 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:18:33,040 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:33,410 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:33,835 WARN ]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-22 04:18:34,200 WARN ]: Spent 317.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 04:18:34,567 WARN ]: Spent 286.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 7 [2018-06-22 04:18:34,885 INFO ]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:34,885 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:18:34,885 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 04:18:34,893 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 04:18:35,140 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 04:18:35,140 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:35,156 INFO ]: Computing forward predicates... [2018-06-22 04:18:36,282 WARN ]: Spent 108.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 15 [2018-06-22 04:18:36,958 WARN ]: Spent 134.00 ms on a formula simplification. DAG size of input: 68 DAG size of output: 20 [2018-06-22 04:18:38,273 WARN ]: Spent 708.00 ms on a formula simplification. DAG size of input: 209 DAG size of output: 20 [2018-06-22 04:18:38,953 WARN ]: Spent 208.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 18 [2018-06-22 04:18:40,073 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 98 DAG size of output: 20 [2018-06-22 04:18:41,391 WARN ]: Spent 686.00 ms on a formula simplification. DAG size of input: 208 DAG size of output: 17 [2018-06-22 04:18:42,561 WARN ]: Spent 646.00 ms on a formula simplification. DAG size of input: 205 DAG size of output: 17 [2018-06-22 04:18:43,080 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 18 [2018-06-22 04:18:43,209 INFO ]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:43,233 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:18:43,233 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 26 [2018-06-22 04:18:43,233 INFO ]: Interpolant automaton has 26 states [2018-06-22 04:18:43,233 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 04:18:43,233 INFO ]: CoverageRelationStatistics Valid=134, Invalid=516, Unknown=0, NotChecked=0, Total=650 [2018-06-22 04:18:43,234 INFO ]: Start difference. First operand 19 states and 19 transitions. Second operand 26 states. [2018-06-22 04:18:43,590 WARN ]: Spent 237.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 39 [2018-06-22 04:18:43,839 WARN ]: Spent 230.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 36 [2018-06-22 04:18:44,079 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 36 [2018-06-22 04:18:44,263 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 32 [2018-06-22 04:18:44,412 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 28 [2018-06-22 04:18:44,896 WARN ]: Spent 187.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 40 [2018-06-22 04:18:44,897 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:18:44,897 INFO ]: Finished difference Result 20 states and 20 transitions. [2018-06-22 04:18:44,897 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 04:18:44,897 INFO ]: Start accepts. Automaton has 26 states. Word has length 18 [2018-06-22 04:18:44,898 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:18:44,898 INFO ]: With dead ends: 20 [2018-06-22 04:18:44,898 INFO ]: Without dead ends: 20 [2018-06-22 04:18:44,899 INFO ]: 0 DeclaredPredicates, 41 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 350 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=336, Invalid=924, Unknown=0, NotChecked=0, Total=1260 [2018-06-22 04:18:44,899 INFO ]: Start minimizeSevpa. Operand 20 states. [2018-06-22 04:18:44,900 INFO ]: Finished minimizeSevpa. Reduced states from 20 to 20. [2018-06-22 04:18:44,900 INFO ]: Start removeUnreachable. Operand 20 states. [2018-06-22 04:18:44,901 INFO ]: Finished removeUnreachable. Reduced from 20 states to 20 states and 20 transitions. [2018-06-22 04:18:44,901 INFO ]: Start accepts. Automaton has 20 states and 20 transitions. Word has length 18 [2018-06-22 04:18:44,901 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:18:44,901 INFO ]: Abstraction has 20 states and 20 transitions. [2018-06-22 04:18:44,901 INFO ]: Interpolant automaton has 26 states. [2018-06-22 04:18:44,901 INFO ]: Start isEmpty. Operand 20 states and 20 transitions. [2018-06-22 04:18:44,901 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-22 04:18:44,901 INFO ]: Found error trace [2018-06-22 04:18:44,901 INFO ]: trace histogram [12, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:18:44,901 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:18:44,902 INFO ]: Analyzing trace with hash 1957848590, now seen corresponding path program 7 times [2018-06-22 04:18:44,902 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:18:44,902 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:18:44,902 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:44,902 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:18:44,902 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:18:45,442 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:46,380 WARN ]: Spent 378.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 7 [2018-06-22 04:18:46,838 WARN ]: Spent 383.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 19 [2018-06-22 04:18:47,328 INFO ]: Checked inductivity of 78 backedges. 0 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 04:18:47,328 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:18:47,328 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:18:47,337 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:18:47,614 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:18:47,638 INFO ]: Computing forward predicates... [2018-06-22 04:18:48,006 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 23 [2018-06-22 04:18:49,356 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 74 DAG size of output: 23 [2018-06-22 04:18:52,083 WARN ]: Spent 157.00 ms on a formula simplification. DAG size of input: 75 DAG size of output: 28 [2018-06-22 04:18:52,807 WARN ]: Spent 345.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 24 Received shutdown request... [2018-06-22 04:18:52,852 INFO ]: Timeout while computing interpolants [2018-06-22 04:18:53,053 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 04:18:53,053 WARN ]: Verification canceled [2018-06-22 04:18:53,057 WARN ]: Timeout [2018-06-22 04:18:53,057 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:18:53 BoogieIcfgContainer [2018-06-22 04:18:53,057 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 04:18:53,058 INFO ]: Toolchain (without parser) took 55598.94 ms. Allocated memory was 307.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 248.2 MB in the beginning and 777.0 MB in the end (delta: -528.8 MB). Peak memory consumption was 663.4 MB. Max. memory is 3.6 GB. [2018-06-22 04:18:53,059 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 307.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 04:18:53,059 INFO ]: ChcToBoogie took 70.62 ms. Allocated memory is still 307.8 MB. Free memory was 248.2 MB in the beginning and 243.2 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:18:53,059 INFO ]: Boogie Preprocessor took 75.72 ms. Allocated memory is still 307.8 MB. Free memory was 243.2 MB in the beginning and 241.1 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 3.6 GB. [2018-06-22 04:18:53,060 INFO ]: RCFGBuilder took 465.53 ms. Allocated memory is still 307.8 MB. Free memory was 241.1 MB in the beginning and 218.1 MB in the end (delta: 23.0 MB). Peak memory consumption was 23.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:18:53,060 INFO ]: TraceAbstraction took 54978.36 ms. Allocated memory was 307.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 217.2 MB in the beginning and 777.0 MB in the end (delta: -559.9 MB). Peak memory consumption was 632.4 MB. Max. memory is 3.6 GB. [2018-06-22 04:18:53,062 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 307.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 70.62 ms. Allocated memory is still 307.8 MB. Free memory was 248.2 MB in the beginning and 243.2 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 75.72 ms. Allocated memory is still 307.8 MB. Free memory was 243.2 MB in the beginning and 241.1 MB in the end (delta: 2.1 MB). Peak memory consumption was 2.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 465.53 ms. Allocated memory is still 307.8 MB. Free memory was 241.1 MB in the beginning and 218.1 MB in the end (delta: 23.0 MB). Peak memory consumption was 23.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 54978.36 ms. Allocated memory was 307.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 217.2 MB in the beginning and 777.0 MB in the end (delta: -559.9 MB). Peak memory consumption was 632.4 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 20 with TraceHistMax 12, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 19 quantified variables from 11 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 54.9s OverallTime, 8 OverallIterations, 12 TraceHistogramMax, 5.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 49 SDtfs, 28 SDslu, 219 SDs, 0 SdLazy, 91 SolverSat, 62 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 156 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 858 ImplicationChecksByTransitivity, 21.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=20occurred 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.2s SsaConstructionTime, 2.5s SatisfiabilityAnalysisTime, 38.2s InterpolantComputationTime, 161 NumberOfCodeBlocks, 161 NumberOfCodeBlocksAsserted, 27 NumberOfCheckSat, 148 ConstructedInterpolants, 0 QuantifiedInterpolants, 23172 SizeOfPredicates, 24 NumberOfNonLiveVariables, 3028 ConjunctsInSsa, 383 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 0/318 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_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_04-18-53-074.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bubblesort_init-1.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_04-18-53-074.csv Completed graceful shutdown