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-1.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 04:16:27,939 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 04:16:27,941 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 04:16:27,953 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 04:16:27,953 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 04:16:27,954 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 04:16:27,956 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 04:16:27,959 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 04:16:27,961 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 04:16:27,963 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 04:16:27,964 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 04:16:27,964 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 04:16:27,965 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 04:16:27,966 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 04:16:27,970 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 04:16:27,971 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 04:16:27,973 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 04:16:27,986 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 04:16:27,988 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 04:16:27,989 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 04:16:27,990 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 04:16:27,994 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 04:16:27,994 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 04:16:27,995 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 04:16:27,995 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 04:16:27,996 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 04:16:27,997 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 04:16:27,997 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 04:16:27,998 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 04:16:27,999 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 04:16:27,999 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 04:16:28,000 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 04:16:28,000 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 04:16:28,001 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 04:16:28,001 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 04:16:28,001 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:16:28,020 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 04:16:28,020 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 04:16:28,020 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 04:16:28,020 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 04:16:28,021 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 04:16:28,022 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 04:16:28,022 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 04:16:28,022 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 04:16:28,022 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 04:16:28,022 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 04:16:28,023 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 04:16:28,023 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 04:16:28,023 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 04:16:28,023 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 04:16:28,023 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 04:16:28,024 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 04:16:28,024 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 04:16:28,025 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 04:16:28,025 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 04:16:28,079 INFO ]: Repository-Root is: /tmp [2018-06-22 04:16:28,095 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 04:16:28,100 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 04:16:28,101 INFO ]: Initializing SmtParser... [2018-06-22 04:16:28,101 INFO ]: SmtParser initialized [2018-06-22 04:16:28,102 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort-1.smt2 [2018-06-22 04:16:28,103 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:16:28,187 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort-1.smt2 unknown [2018-06-22 04:16:28,722 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/bubblesort-1.smt2 [2018-06-22 04:16:28,726 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 04:16:28,733 INFO ]: Walking toolchain with 4 elements. [2018-06-22 04:16:28,733 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 04:16:28,733 INFO ]: Initializing ChcToBoogie... [2018-06-22 04:16:28,733 INFO ]: ChcToBoogie initialized [2018-06-22 04:16:28,737 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:16:28" (1/1) ... [2018-06-22 04:16:28,808 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28 Unit [2018-06-22 04:16:28,808 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 04:16:28,808 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 04:16:28,809 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 04:16:28,809 INFO ]: Boogie Preprocessor initialized [2018-06-22 04:16:28,830 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28" (1/1) ... [2018-06-22 04:16:28,830 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28" (1/1) ... [2018-06-22 04:16:28,851 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28" (1/1) ... [2018-06-22 04:16:28,852 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28" (1/1) ... [2018-06-22 04:16:28,870 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28" (1/1) ... [2018-06-22 04:16:28,871 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28" (1/1) ... [2018-06-22 04:16:28,873 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28" (1/1) ... [2018-06-22 04:16:28,877 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 04:16:28,877 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 04:16:28,877 INFO ]: Initializing RCFGBuilder... [2018-06-22 04:16:28,877 INFO ]: RCFGBuilder initialized [2018-06-22 04:16:28,887 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28" (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:16:28,902 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 04:16:28,902 INFO ]: Found specification of procedure gotoProc [2018-06-22 04:16:28,902 INFO ]: Found implementation of procedure gotoProc [2018-06-22 04:16:28,902 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 04:16:28,903 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 04:16:28,903 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:16:29,319 INFO ]: Using library mode [2018-06-22 04:16:29,320 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:16:29 BoogieIcfgContainer [2018-06-22 04:16:29,320 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 04:16:29,321 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 04:16:29,321 INFO ]: Initializing TraceAbstraction... [2018-06-22 04:16:29,327 INFO ]: TraceAbstraction initialized [2018-06-22 04:16:29,327 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:16:28" (1/3) ... [2018-06-22 04:16:29,328 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@620d87be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:16:29, skipping insertion in model container [2018-06-22 04:16:29,328 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:16:28" (2/3) ... [2018-06-22 04:16:29,329 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@620d87be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:16:29, skipping insertion in model container [2018-06-22 04:16:29,329 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:16:29" (3/3) ... [2018-06-22 04:16:29,330 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 04:16:29,339 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 04:16:29,348 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 04:16:29,391 INFO ]: Using default assertion order modulation [2018-06-22 04:16:29,391 INFO ]: Interprodecural is true [2018-06-22 04:16:29,391 INFO ]: Hoare is false [2018-06-22 04:16:29,391 INFO ]: Compute interpolants for FPandBP [2018-06-22 04:16:29,391 INFO ]: Backedges is TWOTRACK [2018-06-22 04:16:29,391 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 04:16:29,391 INFO ]: Difference is false [2018-06-22 04:16:29,391 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 04:16:29,391 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 04:16:29,404 INFO ]: Start isEmpty. Operand 10 states. [2018-06-22 04:16:29,414 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-22 04:16:29,414 INFO ]: Found error trace [2018-06-22 04:16:29,415 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:16:29,416 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:16:29,422 INFO ]: Analyzing trace with hash 1284994894, now seen corresponding path program 1 times [2018-06-22 04:16:29,424 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:16:29,425 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:16:29,457 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:29,457 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:16:29,457 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:29,524 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:29,633 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:16:29,635 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 04:16:29,635 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-22 04:16:29,636 INFO ]: Interpolant automaton has 3 states [2018-06-22 04:16:29,646 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-22 04:16:29,647 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-22 04:16:29,648 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-22 04:16:29,724 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:16:29,724 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-22 04:16:29,724 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-22 04:16:29,726 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-22 04:16:29,726 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:16:29,737 INFO ]: With dead ends: 9 [2018-06-22 04:16:29,737 INFO ]: Without dead ends: 9 [2018-06-22 04:16:29,739 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:16:29,758 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-22 04:16:29,785 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-22 04:16:29,786 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-22 04:16:29,786 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-22 04:16:29,788 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-22 04:16:29,788 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:16:29,788 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-22 04:16:29,789 INFO ]: Interpolant automaton has 3 states. [2018-06-22 04:16:29,789 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-22 04:16:29,789 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-22 04:16:29,789 INFO ]: Found error trace [2018-06-22 04:16:29,789 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:16:29,789 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:16:29,789 INFO ]: Analyzing trace with hash 1180964567, now seen corresponding path program 1 times [2018-06-22 04:16:29,789 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:16:29,789 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:16:29,790 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:29,790 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:16:29,790 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:29,938 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:30,169 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:16:30,169 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:16:30,169 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:16:30,176 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:16:30,279 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:30,289 INFO ]: Computing forward predicates... [2018-06-22 04:16:31,594 WARN ]: Spent 444.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 12 [2018-06-22 04:16:31,612 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:16:31,634 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:16:31,634 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-22 04:16:31,634 INFO ]: Interpolant automaton has 5 states [2018-06-22 04:16:31,634 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 04:16:31,634 INFO ]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 04:16:31,635 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-22 04:16:31,688 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:16:31,688 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-22 04:16:31,689 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 04:16:31,689 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-22 04:16:31,689 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:16:31,689 INFO ]: With dead ends: 11 [2018-06-22 04:16:31,689 INFO ]: Without dead ends: 11 [2018-06-22 04:16:31,690 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-22 04:16:31,690 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-22 04:16:31,691 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-22 04:16:31,691 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-22 04:16:31,692 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-22 04:16:31,692 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-22 04:16:31,692 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:16:31,692 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-22 04:16:31,692 INFO ]: Interpolant automaton has 5 states. [2018-06-22 04:16:31,692 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-22 04:16:31,692 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-22 04:16:31,692 INFO ]: Found error trace [2018-06-22 04:16:31,692 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:16:31,692 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:16:31,692 INFO ]: Analyzing trace with hash 1062095287, now seen corresponding path program 2 times [2018-06-22 04:16:31,692 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:16:31,692 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:16:31,693 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:31,693 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 04:16:31,693 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:31,857 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:32,236 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 6 [2018-06-22 04:16:32,261 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:16:32,261 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:16:32,261 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 04:16:32,267 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 04:16:32,434 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 04:16:32,434 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:32,445 INFO ]: Computing forward predicates... [2018-06-22 04:16:33,033 WARN ]: Spent 377.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 11 [2018-06-22 04:16:35,302 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:16:35,339 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:16:35,339 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-22 04:16:35,339 INFO ]: Interpolant automaton has 8 states [2018-06-22 04:16:35,339 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-22 04:16:35,339 INFO ]: CoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-06-22 04:16:35,339 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 8 states. [2018-06-22 04:16:36,384 WARN ]: Spent 909.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 13 [2018-06-22 04:16:36,412 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:16:36,412 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-22 04:16:36,412 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 04:16:36,412 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-22 04:16:36,412 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:16:36,413 INFO ]: With dead ends: 12 [2018-06-22 04:16:36,413 INFO ]: Without dead ends: 12 [2018-06-22 04:16:36,413 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2018-06-22 04:16:36,413 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-22 04:16:36,414 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-22 04:16:36,414 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-22 04:16:36,415 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-22 04:16:36,415 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-22 04:16:36,415 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:16:36,415 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-22 04:16:36,415 INFO ]: Interpolant automaton has 8 states. [2018-06-22 04:16:36,415 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-22 04:16:36,415 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 04:16:36,415 INFO ]: Found error trace [2018-06-22 04:16:36,415 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:16:36,416 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:16:36,416 INFO ]: Analyzing trace with hash -1433955954, now seen corresponding path program 3 times [2018-06-22 04:16:36,416 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:16:36,416 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:16:36,417 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:36,417 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:16:36,417 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:36,664 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:37,142 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:16:37,142 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:16:37,142 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:16:37,153 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 04:16:37,302 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-22 04:16:37,302 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:37,314 INFO ]: Computing forward predicates... [2018-06-22 04:16:39,257 WARN ]: Spent 458.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 12 [2018-06-22 04:16:40,078 WARN ]: Spent 122.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 21 [2018-06-22 04:16:40,692 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:16:40,712 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:16:40,739 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2018-06-22 04:16:40,739 INFO ]: Interpolant automaton has 10 states [2018-06-22 04:16:40,739 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 04:16:40,739 INFO ]: CoverageRelationStatistics Valid=37, Invalid=53, Unknown=0, NotChecked=0, Total=90 [2018-06-22 04:16:40,740 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 10 states. [2018-06-22 04:16:40,857 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:16:40,857 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-22 04:16:40,857 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 04:16:40,857 INFO ]: Start accepts. Automaton has 10 states. Word has length 11 [2018-06-22 04:16:40,857 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:16:40,858 INFO ]: With dead ends: 14 [2018-06-22 04:16:40,858 INFO ]: Without dead ends: 14 [2018-06-22 04:16:40,858 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=62, Invalid=94, Unknown=0, NotChecked=0, Total=156 [2018-06-22 04:16:40,858 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-22 04:16:40,861 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-22 04:16:40,861 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-22 04:16:40,861 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-22 04:16:40,861 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 11 [2018-06-22 04:16:40,861 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:16:40,861 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-22 04:16:40,861 INFO ]: Interpolant automaton has 10 states. [2018-06-22 04:16:40,861 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-22 04:16:40,862 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 04:16:40,862 INFO ]: Found error trace [2018-06-22 04:16:40,862 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:16:40,862 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:16:40,862 INFO ]: Analyzing trace with hash 679342766, now seen corresponding path program 4 times [2018-06-22 04:16:40,862 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:16:40,862 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:16:40,862 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:40,862 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:16:40,862 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:41,090 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:41,508 WARN ]: Spent 113.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 04:16:41,788 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 7 [2018-06-22 04:16:42,381 WARN ]: Spent 525.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 12 [2018-06-22 04:16:42,550 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:16:42,550 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:16:42,550 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:16:42,562 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 04:16:42,774 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 04:16:42,774 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:42,786 INFO ]: Computing forward predicates... [2018-06-22 04:16:45,148 WARN ]: Spent 303.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 26 [2018-06-22 04:16:47,060 WARN ]: Spent 506.00 ms on a formula simplification. DAG size of input: 145 DAG size of output: 34 [2018-06-22 04:16:47,987 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 19 [2018-06-22 04:16:49,580 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:16:49,602 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:16:49,602 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2018-06-22 04:16:49,602 INFO ]: Interpolant automaton has 14 states [2018-06-22 04:16:49,602 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-22 04:16:49,602 INFO ]: CoverageRelationStatistics Valid=57, Invalid=125, Unknown=0, NotChecked=0, Total=182 [2018-06-22 04:16:49,603 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 14 states. [2018-06-22 04:16:49,909 WARN ]: Spent 153.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 41 [2018-06-22 04:16:50,103 WARN ]: Spent 176.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 43 [2018-06-22 04:16:50,657 WARN ]: Spent 284.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 43 [2018-06-22 04:16:50,658 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:16:50,658 INFO ]: Finished difference Result 18 states and 18 transitions. [2018-06-22 04:16:50,658 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 04:16:50,658 INFO ]: Start accepts. Automaton has 14 states. Word has length 13 [2018-06-22 04:16:50,659 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:16:50,659 INFO ]: With dead ends: 18 [2018-06-22 04:16:50,659 INFO ]: Without dead ends: 18 [2018-06-22 04:16:50,659 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 77 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=160, Invalid=302, Unknown=0, NotChecked=0, Total=462 [2018-06-22 04:16:50,659 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-22 04:16:50,661 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-06-22 04:16:50,661 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-22 04:16:50,662 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 18 transitions. [2018-06-22 04:16:50,662 INFO ]: Start accepts. Automaton has 18 states and 18 transitions. Word has length 13 [2018-06-22 04:16:50,662 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:16:50,662 INFO ]: Abstraction has 18 states and 18 transitions. [2018-06-22 04:16:50,662 INFO ]: Interpolant automaton has 14 states. [2018-06-22 04:16:50,662 INFO ]: Start isEmpty. Operand 18 states and 18 transitions. [2018-06-22 04:16:50,662 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 04:16:50,662 INFO ]: Found error trace [2018-06-22 04:16:50,662 INFO ]: trace histogram [10, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:16:50,662 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:16:50,662 INFO ]: Analyzing trace with hash -301900562, now seen corresponding path program 5 times [2018-06-22 04:16:50,662 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:16:50,662 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:16:50,663 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:50,663 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:16:50,663 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:16:51,466 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:51,971 WARN ]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 04:16:52,310 WARN ]: Spent 293.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-22 04:16:52,489 WARN ]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 04:16:52,854 WARN ]: Spent 270.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 12 [2018-06-22 04:16:53,218 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:16:53,218 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:16:53,218 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:16:53,231 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 04:16:53,578 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 04:16:53,578 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:16:53,602 INFO ]: Computing forward predicates... [2018-06-22 04:16:55,827 WARN ]: Spent 322.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 31 [2018-06-22 04:16:57,260 WARN ]: Spent 196.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 17 [2018-06-22 04:16:57,693 WARN ]: Spent 129.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 19 [2018-06-22 04:16:59,157 WARN ]: Spent 358.00 ms on a formula simplification. DAG size of input: 139 DAG size of output: 21 [2018-06-22 04:17:01,767 WARN ]: Spent 972.00 ms on a formula simplification. DAG size of input: 245 DAG size of output: 21 [2018-06-22 04:17:02,645 WARN ]: Spent 143.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 17 [2018-06-22 04:17:02,734 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:17:02,758 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:17:02,758 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 22 [2018-06-22 04:17:02,759 INFO ]: Interpolant automaton has 22 states [2018-06-22 04:17:02,759 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-22 04:17:02,759 INFO ]: CoverageRelationStatistics Valid=102, Invalid=360, Unknown=0, NotChecked=0, Total=462 [2018-06-22 04:17:02,759 INFO ]: Start difference. First operand 18 states and 18 transitions. Second operand 22 states. [2018-06-22 04:17:03,072 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 40 [2018-06-22 04:17:03,304 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 40 [2018-06-22 04:17:03,546 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 34 [2018-06-22 04:17:03,748 WARN ]: Spent 180.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 33 [2018-06-22 04:17:03,922 WARN ]: Spent 152.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 30 [2018-06-22 04:17:04,208 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 04:17:04,208 INFO ]: Finished difference Result 20 states and 20 transitions. [2018-06-22 04:17:04,209 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-22 04:17:04,209 INFO ]: Start accepts. Automaton has 22 states. Word has length 17 [2018-06-22 04:17:04,209 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 04:17:04,209 INFO ]: With dead ends: 20 [2018-06-22 04:17:04,209 INFO ]: Without dead ends: 20 [2018-06-22 04:17:04,210 INFO ]: 0 DeclaredPredicates, 40 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 256 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=310, Invalid=746, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 04:17:04,210 INFO ]: Start minimizeSevpa. Operand 20 states. [2018-06-22 04:17:04,211 INFO ]: Finished minimizeSevpa. Reduced states from 20 to 20. [2018-06-22 04:17:04,212 INFO ]: Start removeUnreachable. Operand 20 states. [2018-06-22 04:17:04,212 INFO ]: Finished removeUnreachable. Reduced from 20 states to 20 states and 20 transitions. [2018-06-22 04:17:04,212 INFO ]: Start accepts. Automaton has 20 states and 20 transitions. Word has length 17 [2018-06-22 04:17:04,212 INFO ]: Finished accepts. word is rejected. [2018-06-22 04:17:04,212 INFO ]: Abstraction has 20 states and 20 transitions. [2018-06-22 04:17:04,212 INFO ]: Interpolant automaton has 22 states. [2018-06-22 04:17:04,212 INFO ]: Start isEmpty. Operand 20 states and 20 transitions. [2018-06-22 04:17:04,213 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-22 04:17:04,213 INFO ]: Found error trace [2018-06-22 04:17:04,213 INFO ]: trace histogram [12, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 04:17:04,213 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 04:17:04,213 INFO ]: Analyzing trace with hash 1957848590, now seen corresponding path program 6 times [2018-06-22 04:17:04,213 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 04:17:04,213 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 04:17:04,214 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:17:04,214 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 04:17:04,214 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 04:17:04,974 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:17:05,481 WARN ]: Spent 114.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 04:17:06,079 WARN ]: Spent 551.00 ms on a formula simplification. DAG size of input: 20 DAG size of output: 9 [2018-06-22 04:17:06,551 WARN ]: Spent 404.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 13 [2018-06-22 04:17:06,950 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:17:06,950 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 04:17:06,950 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:17:06,958 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 04:17:07,300 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 04:17:07,300 INFO ]: Conjunction of SSA is unsat [2018-06-22 04:17:07,320 INFO ]: Computing forward predicates... [2018-06-22 04:17:07,716 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 26 [2018-06-22 04:17:14,217 WARN ]: Spent 179.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 26 [2018-06-22 04:17:14,866 WARN ]: Spent 216.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 23 [2018-06-22 04:17:16,290 WARN ]: Spent 377.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 21 [2018-06-22 04:17:16,822 WARN ]: Spent 117.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 17 [2018-06-22 04:17:17,188 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 19 [2018-06-22 04:17:18,303 WARN ]: Spent 345.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 21 [2018-06-22 04:17:22,224 WARN ]: Spent 995.00 ms on a formula simplification. DAG size of input: 248 DAG size of output: 21 [2018-06-22 04:17:22,962 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 17 [2018-06-22 04:17:23,137 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:17:23,162 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 04:17:23,162 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 26 [2018-06-22 04:17:23,162 INFO ]: Interpolant automaton has 26 states [2018-06-22 04:17:23,162 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-22 04:17:23,163 INFO ]: CoverageRelationStatistics Valid=88, Invalid=562, Unknown=0, NotChecked=0, Total=650 [2018-06-22 04:17:23,163 INFO ]: Start difference. First operand 20 states and 20 transitions. Second operand 26 states. [2018-06-22 04:17:23,501 WARN ]: Spent 299.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 43 [2018-06-22 04:17:23,852 WARN ]: Spent 335.00 ms on a formula simplification. DAG size of input: 70 DAG size of output: 49 [2018-06-22 04:17:24,227 WARN ]: Spent 348.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 49 [2018-06-22 04:17:24,579 WARN ]: Spent 333.00 ms on a formula simplification. DAG size of input: 60 DAG size of output: 49 [2018-06-22 04:17:24,896 WARN ]: Spent 295.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 45 [2018-06-22 04:17:25,143 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 52 DAG size of output: 36 [2018-06-22 04:17:25,347 WARN ]: Spent 180.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 33 Received shutdown request... [2018-06-22 04:17:25,416 WARN ]: Removed 11 from assertion stack [2018-06-22 04:17:25,417 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 04:17:25,417 WARN ]: Verification canceled [2018-06-22 04:17:25,421 WARN ]: Timeout [2018-06-22 04:17:25,422 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:17:25 BoogieIcfgContainer [2018-06-22 04:17:25,422 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 04:17:25,423 INFO ]: Toolchain (without parser) took 56695.97 ms. Allocated memory was 305.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 245.1 MB in the beginning and 1.2 GB in the end (delta: -905.5 MB). Peak memory consumption was 286.2 MB. Max. memory is 3.6 GB. [2018-06-22 04:17:25,424 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 305.7 MB. Free memory is still 271.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 04:17:25,424 INFO ]: ChcToBoogie took 75.00 ms. Allocated memory is still 305.7 MB. Free memory was 244.1 MB in the beginning and 242.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:17:25,424 INFO ]: Boogie Preprocessor took 68.39 ms. Allocated memory is still 305.7 MB. Free memory was 242.1 MB in the beginning and 240.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:17:25,424 INFO ]: RCFGBuilder took 442.31 ms. Allocated memory is still 305.7 MB. Free memory was 240.1 MB in the beginning and 213.9 MB in the end (delta: 26.2 MB). Peak memory consumption was 26.2 MB. Max. memory is 3.6 GB. [2018-06-22 04:17:25,425 INFO ]: TraceAbstraction took 56100.50 ms. Allocated memory was 305.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 213.9 MB in the beginning and 1.2 GB in the end (delta: -936.7 MB). Peak memory consumption was 255.0 MB. Max. memory is 3.6 GB. [2018-06-22 04:17:25,428 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 305.7 MB. Free memory is still 271.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 75.00 ms. Allocated memory is still 305.7 MB. Free memory was 244.1 MB in the beginning and 242.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 68.39 ms. Allocated memory is still 305.7 MB. Free memory was 242.1 MB in the beginning and 240.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 442.31 ms. Allocated memory is still 305.7 MB. Free memory was 240.1 MB in the beginning and 213.9 MB in the end (delta: 26.2 MB). Peak memory consumption was 26.2 MB. Max. memory is 3.6 GB. * TraceAbstraction took 56100.50 ms. Allocated memory was 305.7 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 213.9 MB in the beginning and 1.2 GB in the end (delta: -936.7 MB). Peak memory consumption was 255.0 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 constructing difference of abstraction (20states) and interpolant automaton (currently 10 states, 26 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 42. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 56.0s OverallTime, 7 OverallIterations, 12 TraceHistogramMax, 6.1s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 45 SDtfs, 15 SDslu, 164 SDs, 0 SdLazy, 68 SolverSat, 59 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 160 GetRequests, 50 SyntacticMatches, 5 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 491 ImplicationChecksByTransitivity, 19.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=20occurred in iteration=6, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 6 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 3.3s SatisfiabilityAnalysisTime, 45.7s InterpolantComputationTime, 163 NumberOfCodeBlocks, 163 NumberOfCodeBlocksAsserted, 27 NumberOfCheckSat, 150 ConstructedInterpolants, 0 QuantifiedInterpolants, 22153 SizeOfPredicates, 24 NumberOfNonLiveVariables, 3378 ConjunctsInSsa, 392 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 0/342 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-1.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_04-17-25-437.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/bubblesort-1.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_04-17-25-437.csv Completed graceful shutdown