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/hcai-bench/arrays_orig/array_reverse_once1_abstracted.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 01:37:16,585 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 01:37:16,587 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 01:37:16,602 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 01:37:16,602 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 01:37:16,603 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 01:37:16,604 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 01:37:16,612 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 01:37:16,614 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 01:37:16,614 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 01:37:16,615 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 01:37:16,615 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 01:37:16,616 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 01:37:16,617 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 01:37:16,618 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 01:37:16,619 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 01:37:16,621 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 01:37:16,623 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 01:37:16,624 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 01:37:16,625 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 01:37:16,626 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 01:37:16,629 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 01:37:16,629 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 01:37:16,629 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 01:37:16,630 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 01:37:16,631 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 01:37:16,632 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 01:37:16,633 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 01:37:16,634 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 01:37:16,634 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 01:37:16,635 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 01:37:16,636 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 01:37:16,636 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 01:37:16,637 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 01:37:16,637 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 01:37:16,638 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-22 01:37:16,651 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 01:37:16,651 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 01:37:16,652 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 01:37:16,652 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 01:37:16,653 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 01:37:16,653 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 01:37:16,654 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 01:37:16,654 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 01:37:16,654 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:37:16,654 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 01:37:16,655 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 01:37:16,655 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 01:37:16,655 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 01:37:16,655 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 01:37:16,656 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 01:37:16,656 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 01:37:16,656 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 01:37:16,657 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 01:37:16,658 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 01:37:16,691 INFO ]: Repository-Root is: /tmp [2018-06-22 01:37:16,705 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 01:37:16,708 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 01:37:16,710 INFO ]: Initializing SmtParser... [2018-06-22 01:37:16,710 INFO ]: SmtParser initialized [2018-06-22 01:37:16,710 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hcai-bench/arrays_orig/array_reverse_once1_abstracted.smt2 [2018-06-22 01:37:16,712 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 01:37:16,805 INFO ]: Executing SMT file /storage/chc-comp/hcai-bench/arrays_orig/array_reverse_once1_abstracted.smt2 unknown [2018-06-22 01:37:17,069 INFO ]: Succesfully executed SMT file /storage/chc-comp/hcai-bench/arrays_orig/array_reverse_once1_abstracted.smt2 [2018-06-22 01:37:17,074 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 01:37:17,083 INFO ]: Walking toolchain with 4 elements. [2018-06-22 01:37:17,084 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 01:37:17,084 INFO ]: Initializing ChcToBoogie... [2018-06-22 01:37:17,084 INFO ]: ChcToBoogie initialized [2018-06-22 01:37:17,087 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:37:17" (1/1) ... [2018-06-22 01:37:17,138 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17 Unit [2018-06-22 01:37:17,138 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 01:37:17,138 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 01:37:17,138 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 01:37:17,138 INFO ]: Boogie Preprocessor initialized [2018-06-22 01:37:17,159 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17" (1/1) ... [2018-06-22 01:37:17,159 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17" (1/1) ... [2018-06-22 01:37:17,167 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17" (1/1) ... [2018-06-22 01:37:17,167 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17" (1/1) ... [2018-06-22 01:37:17,171 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17" (1/1) ... [2018-06-22 01:37:17,182 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17" (1/1) ... [2018-06-22 01:37:17,183 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17" (1/1) ... [2018-06-22 01:37:17,185 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 01:37:17,186 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 01:37:17,186 INFO ]: Initializing RCFGBuilder... [2018-06-22 01:37:17,186 INFO ]: RCFGBuilder initialized [2018-06-22 01:37:17,186 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17" (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) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 01:37:17,206 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-22 01:37:17,206 INFO ]: Found specification of procedure gotoProc [2018-06-22 01:37:17,206 INFO ]: Found implementation of procedure gotoProc [2018-06-22 01:37:17,206 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 01:37:17,206 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 01:37:17,206 INFO ]: Found implementation of procedure Ultimate.START [2018-06-22 01:37:17,565 INFO ]: Using library mode [2018-06-22 01:37:17,566 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:37:17 BoogieIcfgContainer [2018-06-22 01:37:17,566 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 01:37:17,567 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 01:37:17,567 INFO ]: Initializing TraceAbstraction... [2018-06-22 01:37:17,572 INFO ]: TraceAbstraction initialized [2018-06-22 01:37:17,572 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 01:37:17" (1/3) ... [2018-06-22 01:37:17,573 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19c01e26 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 01:37:17, skipping insertion in model container [2018-06-22 01:37:17,573 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 01:37:17" (2/3) ... [2018-06-22 01:37:17,574 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@19c01e26 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 01:37:17, skipping insertion in model container [2018-06-22 01:37:17,574 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 01:37:17" (3/3) ... [2018-06-22 01:37:17,575 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 01:37:17,582 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 01:37:17,588 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 01:37:17,622 INFO ]: Using default assertion order modulation [2018-06-22 01:37:17,622 INFO ]: Interprodecural is true [2018-06-22 01:37:17,622 INFO ]: Hoare is false [2018-06-22 01:37:17,622 INFO ]: Compute interpolants for FPandBP [2018-06-22 01:37:17,623 INFO ]: Backedges is TWOTRACK [2018-06-22 01:37:17,623 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 01:37:17,623 INFO ]: Difference is false [2018-06-22 01:37:17,623 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 01:37:17,623 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 01:37:17,637 INFO ]: Start isEmpty. Operand 23 states. [2018-06-22 01:37:17,646 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 01:37:17,647 INFO ]: Found error trace [2018-06-22 01:37:17,647 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:17,648 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:17,652 INFO ]: Analyzing trace with hash -1897800257, now seen corresponding path program 1 times [2018-06-22 01:37:17,654 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:17,654 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:17,690 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:17,690 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:17,690 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:17,726 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:17,815 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:37:17,817 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:37:17,817 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:37:17,818 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:37:17,828 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:37:17,828 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:37:17,830 INFO ]: Start difference. First operand 23 states. Second operand 4 states. [2018-06-22 01:37:18,133 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:18,134 INFO ]: Finished difference Result 39 states and 57 transitions. [2018-06-22 01:37:18,134 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:37:18,135 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 01:37:18,135 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:18,143 INFO ]: With dead ends: 39 [2018-06-22 01:37:18,144 INFO ]: Without dead ends: 39 [2018-06-22 01:37:18,145 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:37:18,159 INFO ]: Start minimizeSevpa. Operand 39 states. [2018-06-22 01:37:18,184 INFO ]: Finished minimizeSevpa. Reduced states from 39 to 39. [2018-06-22 01:37:18,185 INFO ]: Start removeUnreachable. Operand 39 states. [2018-06-22 01:37:18,187 INFO ]: Finished removeUnreachable. Reduced from 39 states to 39 states and 57 transitions. [2018-06-22 01:37:18,188 INFO ]: Start accepts. Automaton has 39 states and 57 transitions. Word has length 9 [2018-06-22 01:37:18,189 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:18,189 INFO ]: Abstraction has 39 states and 57 transitions. [2018-06-22 01:37:18,189 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:37:18,189 INFO ]: Start isEmpty. Operand 39 states and 57 transitions. [2018-06-22 01:37:18,191 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:37:18,191 INFO ]: Found error trace [2018-06-22 01:37:18,191 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:18,191 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:18,191 INFO ]: Analyzing trace with hash 1748653349, now seen corresponding path program 1 times [2018-06-22 01:37:18,191 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:18,191 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:18,192 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:18,192 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:18,192 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:18,199 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:18,236 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:37:18,236 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:37:18,236 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:37:18,237 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:37:18,237 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:37:18,237 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:37:18,237 INFO ]: Start difference. First operand 39 states and 57 transitions. Second operand 4 states. [2018-06-22 01:37:18,400 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:18,400 INFO ]: Finished difference Result 57 states and 84 transitions. [2018-06-22 01:37:18,401 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:37:18,401 INFO ]: Start accepts. Automaton has 4 states. Word has length 11 [2018-06-22 01:37:18,401 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:18,404 INFO ]: With dead ends: 57 [2018-06-22 01:37:18,404 INFO ]: Without dead ends: 57 [2018-06-22 01:37:18,405 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:37:18,405 INFO ]: Start minimizeSevpa. Operand 57 states. [2018-06-22 01:37:18,416 INFO ]: Finished minimizeSevpa. Reduced states from 57 to 57. [2018-06-22 01:37:18,416 INFO ]: Start removeUnreachable. Operand 57 states. [2018-06-22 01:37:18,418 INFO ]: Finished removeUnreachable. Reduced from 57 states to 57 states and 84 transitions. [2018-06-22 01:37:18,418 INFO ]: Start accepts. Automaton has 57 states and 84 transitions. Word has length 11 [2018-06-22 01:37:18,418 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:18,418 INFO ]: Abstraction has 57 states and 84 transitions. [2018-06-22 01:37:18,418 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:37:18,418 INFO ]: Start isEmpty. Operand 57 states and 84 transitions. [2018-06-22 01:37:18,419 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:37:18,419 INFO ]: Found error trace [2018-06-22 01:37:18,419 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:18,419 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:18,419 INFO ]: Analyzing trace with hash 1573310567, now seen corresponding path program 1 times [2018-06-22 01:37:18,419 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:18,420 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:18,420 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:18,420 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:18,420 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:18,439 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:18,624 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:37:18,624 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:37:18,624 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-22 01:37:18,624 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:37:18,625 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:37:18,625 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:37:18,625 INFO ]: Start difference. First operand 57 states and 84 transitions. Second operand 5 states. [2018-06-22 01:37:18,973 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:18,973 INFO ]: Finished difference Result 132 states and 252 transitions. [2018-06-22 01:37:18,973 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:37:18,974 INFO ]: Start accepts. Automaton has 5 states. Word has length 11 [2018-06-22 01:37:18,974 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:18,980 INFO ]: With dead ends: 132 [2018-06-22 01:37:18,980 INFO ]: Without dead ends: 132 [2018-06-22 01:37:18,980 INFO ]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:37:18,980 INFO ]: Start minimizeSevpa. Operand 132 states. [2018-06-22 01:37:19,008 INFO ]: Finished minimizeSevpa. Reduced states from 132 to 63. [2018-06-22 01:37:19,009 INFO ]: Start removeUnreachable. Operand 63 states. [2018-06-22 01:37:19,011 INFO ]: Finished removeUnreachable. Reduced from 63 states to 63 states and 93 transitions. [2018-06-22 01:37:19,011 INFO ]: Start accepts. Automaton has 63 states and 93 transitions. Word has length 11 [2018-06-22 01:37:19,012 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:19,012 INFO ]: Abstraction has 63 states and 93 transitions. [2018-06-22 01:37:19,012 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:37:19,012 INFO ]: Start isEmpty. Operand 63 states and 93 transitions. [2018-06-22 01:37:19,013 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-22 01:37:19,013 INFO ]: Found error trace [2018-06-22 01:37:19,013 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:19,013 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:19,013 INFO ]: Analyzing trace with hash 1573340358, now seen corresponding path program 1 times [2018-06-22 01:37:19,013 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:19,013 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:19,014 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:19,014 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:19,014 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:19,024 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:19,064 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:37:19,064 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:37:19,065 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-22 01:37:19,065 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:37:19,065 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:37:19,065 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:37:19,065 INFO ]: Start difference. First operand 63 states and 93 transitions. Second operand 5 states. [2018-06-22 01:37:19,429 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:19,429 INFO ]: Finished difference Result 116 states and 191 transitions. [2018-06-22 01:37:19,429 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:37:19,429 INFO ]: Start accepts. Automaton has 5 states. Word has length 11 [2018-06-22 01:37:19,429 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:19,434 INFO ]: With dead ends: 116 [2018-06-22 01:37:19,434 INFO ]: Without dead ends: 113 [2018-06-22 01:37:19,434 INFO ]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-22 01:37:19,434 INFO ]: Start minimizeSevpa. Operand 113 states. [2018-06-22 01:37:19,445 INFO ]: Finished minimizeSevpa. Reduced states from 113 to 60. [2018-06-22 01:37:19,445 INFO ]: Start removeUnreachable. Operand 60 states. [2018-06-22 01:37:19,447 INFO ]: Finished removeUnreachable. Reduced from 60 states to 60 states and 87 transitions. [2018-06-22 01:37:19,447 INFO ]: Start accepts. Automaton has 60 states and 87 transitions. Word has length 11 [2018-06-22 01:37:19,447 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:19,447 INFO ]: Abstraction has 60 states and 87 transitions. [2018-06-22 01:37:19,447 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:37:19,447 INFO ]: Start isEmpty. Operand 60 states and 87 transitions. [2018-06-22 01:37:19,450 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 01:37:19,450 INFO ]: Found error trace [2018-06-22 01:37:19,450 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:19,450 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:19,450 INFO ]: Analyzing trace with hash -28485805, now seen corresponding path program 1 times [2018-06-22 01:37:19,450 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:19,450 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:19,451 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:19,451 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:19,451 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:19,478 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:19,523 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 01:37:19,523 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:37:19,523 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:37:19,523 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:37:19,523 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:37:19,523 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:37:19,523 INFO ]: Start difference. First operand 60 states and 87 transitions. Second operand 4 states. [2018-06-22 01:37:19,633 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:19,633 INFO ]: Finished difference Result 102 states and 160 transitions. [2018-06-22 01:37:19,633 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 01:37:19,633 INFO ]: Start accepts. Automaton has 4 states. Word has length 17 [2018-06-22 01:37:19,633 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:19,635 INFO ]: With dead ends: 102 [2018-06-22 01:37:19,635 INFO ]: Without dead ends: 99 [2018-06-22 01:37:19,635 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:37:19,635 INFO ]: Start minimizeSevpa. Operand 99 states. [2018-06-22 01:37:19,645 INFO ]: Finished minimizeSevpa. Reduced states from 99 to 63. [2018-06-22 01:37:19,645 INFO ]: Start removeUnreachable. Operand 63 states. [2018-06-22 01:37:19,646 INFO ]: Finished removeUnreachable. Reduced from 63 states to 63 states and 90 transitions. [2018-06-22 01:37:19,646 INFO ]: Start accepts. Automaton has 63 states and 90 transitions. Word has length 17 [2018-06-22 01:37:19,646 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:19,646 INFO ]: Abstraction has 63 states and 90 transitions. [2018-06-22 01:37:19,646 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:37:19,647 INFO ]: Start isEmpty. Operand 63 states and 90 transitions. [2018-06-22 01:37:19,649 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-22 01:37:19,649 INFO ]: Found error trace [2018-06-22 01:37:19,649 INFO ]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:19,649 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:19,649 INFO ]: Analyzing trace with hash 66760537, now seen corresponding path program 1 times [2018-06-22 01:37:19,649 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:19,649 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:19,650 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:19,650 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:19,650 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:19,687 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:19,880 INFO ]: Checked inductivity of 9 backedges. 5 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:37:19,880 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:37:19,880 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 01:37:19,898 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:19,964 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:19,976 INFO ]: Computing forward predicates... [2018-06-22 01:37:20,456 INFO ]: Checked inductivity of 9 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:37:20,484 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:37:20,484 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 15] total 24 [2018-06-22 01:37:20,485 INFO ]: Interpolant automaton has 24 states [2018-06-22 01:37:20,485 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-22 01:37:20,485 INFO ]: CoverageRelationStatistics Valid=54, Invalid=498, Unknown=0, NotChecked=0, Total=552 [2018-06-22 01:37:20,486 INFO ]: Start difference. First operand 63 states and 90 transitions. Second operand 24 states. [2018-06-22 01:37:22,453 WARN ]: Spent 207.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 40 [2018-06-22 01:37:24,435 WARN ]: Spent 108.00 ms on a formula simplification that was a NOOP. DAG size: 34 [2018-06-22 01:37:25,016 WARN ]: Spent 271.00 ms on a formula simplification that was a NOOP. DAG size: 34 [2018-06-22 01:37:29,148 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:29,148 INFO ]: Finished difference Result 543 states and 1785 transitions. [2018-06-22 01:37:29,149 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 99 states. [2018-06-22 01:37:29,149 INFO ]: Start accepts. Automaton has 24 states. Word has length 26 [2018-06-22 01:37:29,149 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:29,172 INFO ]: With dead ends: 543 [2018-06-22 01:37:29,172 INFO ]: Without dead ends: 460 [2018-06-22 01:37:29,177 INFO ]: 0 DeclaredPredicates, 153 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4503 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=2080, Invalid=11030, Unknown=0, NotChecked=0, Total=13110 [2018-06-22 01:37:29,177 INFO ]: Start minimizeSevpa. Operand 460 states. [2018-06-22 01:37:29,332 INFO ]: Finished minimizeSevpa. Reduced states from 460 to 99. [2018-06-22 01:37:29,333 INFO ]: Start removeUnreachable. Operand 99 states. [2018-06-22 01:37:29,335 INFO ]: Finished removeUnreachable. Reduced from 99 states to 99 states and 145 transitions. [2018-06-22 01:37:29,335 INFO ]: Start accepts. Automaton has 99 states and 145 transitions. Word has length 26 [2018-06-22 01:37:29,335 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:29,335 INFO ]: Abstraction has 99 states and 145 transitions. [2018-06-22 01:37:29,335 INFO ]: Interpolant automaton has 24 states. [2018-06-22 01:37:29,335 INFO ]: Start isEmpty. Operand 99 states and 145 transitions. [2018-06-22 01:37:29,343 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-22 01:37:29,343 INFO ]: Found error trace [2018-06-22 01:37:29,343 INFO ]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:29,343 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:29,344 INFO ]: Analyzing trace with hash 66790328, now seen corresponding path program 1 times [2018-06-22 01:37:29,344 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:29,344 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:29,344 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:29,345 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:29,345 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:29,380 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:29,590 INFO ]: Checked inductivity of 9 backedges. 5 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 01:37:29,590 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:37:29,590 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 01:37:29,601 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:29,625 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:29,628 INFO ]: Computing forward predicates... [2018-06-22 01:37:29,633 INFO ]: Checked inductivity of 9 backedges. 5 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 01:37:29,652 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:37:29,652 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-22 01:37:29,652 INFO ]: Interpolant automaton has 10 states [2018-06-22 01:37:29,652 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-22 01:37:29,652 INFO ]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-06-22 01:37:29,653 INFO ]: Start difference. First operand 99 states and 145 transitions. Second operand 10 states. [2018-06-22 01:37:30,074 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:30,074 INFO ]: Finished difference Result 217 states and 394 transitions. [2018-06-22 01:37:30,074 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 01:37:30,075 INFO ]: Start accepts. Automaton has 10 states. Word has length 26 [2018-06-22 01:37:30,075 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:30,078 INFO ]: With dead ends: 217 [2018-06-22 01:37:30,078 INFO ]: Without dead ends: 214 [2018-06-22 01:37:30,079 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 35 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=136, Invalid=284, Unknown=0, NotChecked=0, Total=420 [2018-06-22 01:37:30,079 INFO ]: Start minimizeSevpa. Operand 214 states. [2018-06-22 01:37:30,089 INFO ]: Finished minimizeSevpa. Reduced states from 214 to 93. [2018-06-22 01:37:30,089 INFO ]: Start removeUnreachable. Operand 93 states. [2018-06-22 01:37:30,090 INFO ]: Finished removeUnreachable. Reduced from 93 states to 93 states and 136 transitions. [2018-06-22 01:37:30,090 INFO ]: Start accepts. Automaton has 93 states and 136 transitions. Word has length 26 [2018-06-22 01:37:30,091 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:30,091 INFO ]: Abstraction has 93 states and 136 transitions. [2018-06-22 01:37:30,091 INFO ]: Interpolant automaton has 10 states. [2018-06-22 01:37:30,091 INFO ]: Start isEmpty. Operand 93 states and 136 transitions. [2018-06-22 01:37:30,092 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-22 01:37:30,092 INFO ]: Found error trace [2018-06-22 01:37:30,092 INFO ]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:30,092 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:30,092 INFO ]: Analyzing trace with hash -1622183205, now seen corresponding path program 1 times [2018-06-22 01:37:30,092 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:30,092 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:30,093 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:30,093 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:30,093 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:30,128 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:30,358 INFO ]: Checked inductivity of 9 backedges. 2 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-22 01:37:30,358 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:37:30,358 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 01:37:30,377 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:30,424 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:30,427 INFO ]: Computing forward predicates... [2018-06-22 01:37:30,594 INFO ]: Checked inductivity of 9 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-22 01:37:30,614 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:37:30,614 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [15] total 17 [2018-06-22 01:37:30,614 INFO ]: Interpolant automaton has 17 states [2018-06-22 01:37:30,614 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 01:37:30,614 INFO ]: CoverageRelationStatistics Valid=33, Invalid=239, Unknown=0, NotChecked=0, Total=272 [2018-06-22 01:37:30,614 INFO ]: Start difference. First operand 93 states and 136 transitions. Second operand 17 states. [2018-06-22 01:37:31,217 WARN ]: Spent 191.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2018-06-22 01:37:34,713 WARN ]: Spent 166.00 ms on a formula simplification that was a NOOP. DAG size: 25 [2018-06-22 01:37:35,144 WARN ]: Spent 196.00 ms on a formula simplification that was a NOOP. DAG size: 28 [2018-06-22 01:37:35,890 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:35,890 INFO ]: Finished difference Result 509 states and 1784 transitions. [2018-06-22 01:37:35,891 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 107 states. [2018-06-22 01:37:35,891 INFO ]: Start accepts. Automaton has 17 states. Word has length 26 [2018-06-22 01:37:35,891 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:35,906 INFO ]: With dead ends: 509 [2018-06-22 01:37:35,906 INFO ]: Without dead ends: 509 [2018-06-22 01:37:35,910 INFO ]: 0 DeclaredPredicates, 145 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4770 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=1482, Invalid=11628, Unknown=0, NotChecked=0, Total=13110 [2018-06-22 01:37:35,910 INFO ]: Start minimizeSevpa. Operand 509 states. [2018-06-22 01:37:36,013 INFO ]: Finished minimizeSevpa. Reduced states from 509 to 99. [2018-06-22 01:37:36,014 INFO ]: Start removeUnreachable. Operand 99 states. [2018-06-22 01:37:36,014 INFO ]: Finished removeUnreachable. Reduced from 99 states to 99 states and 145 transitions. [2018-06-22 01:37:36,014 INFO ]: Start accepts. Automaton has 99 states and 145 transitions. Word has length 26 [2018-06-22 01:37:36,014 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:36,015 INFO ]: Abstraction has 99 states and 145 transitions. [2018-06-22 01:37:36,015 INFO ]: Interpolant automaton has 17 states. [2018-06-22 01:37:36,015 INFO ]: Start isEmpty. Operand 99 states and 145 transitions. [2018-06-22 01:37:36,016 INFO ]: Finished isEmpty. Found accepting run of length 29 [2018-06-22 01:37:36,016 INFO ]: Found error trace [2018-06-22 01:37:36,016 INFO ]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:36,016 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:36,016 INFO ]: Analyzing trace with hash -1495126807, now seen corresponding path program 1 times [2018-06-22 01:37:36,016 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:36,016 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:36,017 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:36,017 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:36,017 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:36,035 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:36,174 INFO ]: Checked inductivity of 11 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-22 01:37:36,174 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:37:36,174 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:37:36,175 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:37:36,175 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:37:36,175 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:37:36,175 INFO ]: Start difference. First operand 99 states and 145 transitions. Second operand 4 states. [2018-06-22 01:37:36,226 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:36,226 INFO ]: Finished difference Result 258 states and 456 transitions. [2018-06-22 01:37:36,227 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:37:36,227 INFO ]: Start accepts. Automaton has 4 states. Word has length 28 [2018-06-22 01:37:36,227 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:36,231 INFO ]: With dead ends: 258 [2018-06-22 01:37:36,231 INFO ]: Without dead ends: 258 [2018-06-22 01:37:36,231 INFO ]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:37:36,231 INFO ]: Start minimizeSevpa. Operand 258 states. [2018-06-22 01:37:36,243 INFO ]: Finished minimizeSevpa. Reduced states from 258 to 120. [2018-06-22 01:37:36,243 INFO ]: Start removeUnreachable. Operand 120 states. [2018-06-22 01:37:36,244 INFO ]: Finished removeUnreachable. Reduced from 120 states to 120 states and 178 transitions. [2018-06-22 01:37:36,244 INFO ]: Start accepts. Automaton has 120 states and 178 transitions. Word has length 28 [2018-06-22 01:37:36,244 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:36,244 INFO ]: Abstraction has 120 states and 178 transitions. [2018-06-22 01:37:36,244 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:37:36,244 INFO ]: Start isEmpty. Operand 120 states and 178 transitions. [2018-06-22 01:37:36,248 INFO ]: Finished isEmpty. Found accepting run of length 29 [2018-06-22 01:37:36,248 INFO ]: Found error trace [2018-06-22 01:37:36,248 INFO ]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:36,248 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:36,248 INFO ]: Analyzing trace with hash -677478357, now seen corresponding path program 1 times [2018-06-22 01:37:36,248 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:36,248 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:36,249 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:36,249 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:36,249 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:36,270 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:36,581 INFO ]: Checked inductivity of 11 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 01:37:36,581 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:37:36,581 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-22 01:37:36,581 INFO ]: Interpolant automaton has 5 states [2018-06-22 01:37:36,581 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-22 01:37:36,581 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:37:36,582 INFO ]: Start difference. First operand 120 states and 178 transitions. Second operand 5 states. [2018-06-22 01:37:36,736 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:36,736 INFO ]: Finished difference Result 238 states and 416 transitions. [2018-06-22 01:37:36,736 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 01:37:36,736 INFO ]: Start accepts. Automaton has 5 states. Word has length 28 [2018-06-22 01:37:36,736 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:36,738 INFO ]: With dead ends: 238 [2018-06-22 01:37:36,738 INFO ]: Without dead ends: 198 [2018-06-22 01:37:36,738 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-06-22 01:37:36,738 INFO ]: Start minimizeSevpa. Operand 198 states. [2018-06-22 01:37:36,745 INFO ]: Finished minimizeSevpa. Reduced states from 198 to 120. [2018-06-22 01:37:36,745 INFO ]: Start removeUnreachable. Operand 120 states. [2018-06-22 01:37:36,746 INFO ]: Finished removeUnreachable. Reduced from 120 states to 120 states and 178 transitions. [2018-06-22 01:37:36,746 INFO ]: Start accepts. Automaton has 120 states and 178 transitions. Word has length 28 [2018-06-22 01:37:36,746 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:36,746 INFO ]: Abstraction has 120 states and 178 transitions. [2018-06-22 01:37:36,747 INFO ]: Interpolant automaton has 5 states. [2018-06-22 01:37:36,747 INFO ]: Start isEmpty. Operand 120 states and 178 transitions. [2018-06-22 01:37:36,750 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 01:37:36,750 INFO ]: Found error trace [2018-06-22 01:37:36,750 INFO ]: trace histogram [3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:36,750 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:36,750 INFO ]: Analyzing trace with hash 479310105, now seen corresponding path program 1 times [2018-06-22 01:37:36,750 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:36,750 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:36,751 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:36,751 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:36,751 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:36,773 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:36,946 INFO ]: Checked inductivity of 26 backedges. 12 proven. 7 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:37:36,946 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:37:36,946 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 01:37:36,952 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:37,003 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:37,011 INFO ]: Computing forward predicates... [2018-06-22 01:37:37,174 INFO ]: Checked inductivity of 26 backedges. 12 proven. 7 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:37:37,194 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:37:37,194 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 15 [2018-06-22 01:37:37,194 INFO ]: Interpolant automaton has 15 states [2018-06-22 01:37:37,194 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 01:37:37,194 INFO ]: CoverageRelationStatistics Valid=29, Invalid=181, Unknown=0, NotChecked=0, Total=210 [2018-06-22 01:37:37,194 INFO ]: Start difference. First operand 120 states and 178 transitions. Second operand 15 states. [2018-06-22 01:37:37,905 WARN ]: Spent 169.00 ms on a formula simplification that was a NOOP. DAG size: 20 [2018-06-22 01:37:38,313 WARN ]: Spent 230.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2018-06-22 01:37:38,763 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:38,763 INFO ]: Finished difference Result 445 states and 1101 transitions. [2018-06-22 01:37:38,763 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-06-22 01:37:38,763 INFO ]: Start accepts. Automaton has 15 states. Word has length 37 [2018-06-22 01:37:38,764 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:38,776 INFO ]: With dead ends: 445 [2018-06-22 01:37:38,777 INFO ]: Without dead ends: 445 [2018-06-22 01:37:38,777 INFO ]: 0 DeclaredPredicates, 62 GetRequests, 34 SyntacticMatches, 2 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=120, Invalid=636, Unknown=0, NotChecked=0, Total=756 [2018-06-22 01:37:38,777 INFO ]: Start minimizeSevpa. Operand 445 states. [2018-06-22 01:37:38,834 INFO ]: Finished minimizeSevpa. Reduced states from 445 to 171. [2018-06-22 01:37:38,834 INFO ]: Start removeUnreachable. Operand 171 states. [2018-06-22 01:37:38,836 INFO ]: Finished removeUnreachable. Reduced from 171 states to 171 states and 281 transitions. [2018-06-22 01:37:38,837 INFO ]: Start accepts. Automaton has 171 states and 281 transitions. Word has length 37 [2018-06-22 01:37:38,837 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:38,837 INFO ]: Abstraction has 171 states and 281 transitions. [2018-06-22 01:37:38,837 INFO ]: Interpolant automaton has 15 states. [2018-06-22 01:37:38,837 INFO ]: Start isEmpty. Operand 171 states and 281 transitions. [2018-06-22 01:37:38,842 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 01:37:38,842 INFO ]: Found error trace [2018-06-22 01:37:38,842 INFO ]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:38,842 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:38,843 INFO ]: Analyzing trace with hash 1832619802, now seen corresponding path program 1 times [2018-06-22 01:37:38,843 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:38,843 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:38,843 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:38,843 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:38,843 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:38,853 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:39,009 INFO ]: Checked inductivity of 26 backedges. 12 proven. 7 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:37:39,009 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:37:39,009 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 01:37:39,015 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:39,061 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:39,064 INFO ]: Computing forward predicates... [2018-06-22 01:37:39,115 INFO ]: Checked inductivity of 26 backedges. 12 proven. 7 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-22 01:37:39,134 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:37:39,134 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 13 [2018-06-22 01:37:39,134 INFO ]: Interpolant automaton has 13 states [2018-06-22 01:37:39,134 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 01:37:39,134 INFO ]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-06-22 01:37:39,134 INFO ]: Start difference. First operand 171 states and 281 transitions. Second operand 13 states. [2018-06-22 01:37:40,085 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:40,085 INFO ]: Finished difference Result 458 states and 1214 transitions. [2018-06-22 01:37:40,085 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-06-22 01:37:40,085 INFO ]: Start accepts. Automaton has 13 states. Word has length 37 [2018-06-22 01:37:40,085 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:40,095 INFO ]: With dead ends: 458 [2018-06-22 01:37:40,095 INFO ]: Without dead ends: 458 [2018-06-22 01:37:40,096 INFO ]: 0 DeclaredPredicates, 75 GetRequests, 32 SyntacticMatches, 6 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 305 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=280, Invalid=1202, Unknown=0, NotChecked=0, Total=1482 [2018-06-22 01:37:40,096 INFO ]: Start minimizeSevpa. Operand 458 states. [2018-06-22 01:37:40,154 INFO ]: Finished minimizeSevpa. Reduced states from 458 to 193. [2018-06-22 01:37:40,154 INFO ]: Start removeUnreachable. Operand 193 states. [2018-06-22 01:37:40,156 INFO ]: Finished removeUnreachable. Reduced from 193 states to 193 states and 343 transitions. [2018-06-22 01:37:40,156 INFO ]: Start accepts. Automaton has 193 states and 343 transitions. Word has length 37 [2018-06-22 01:37:40,156 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:40,156 INFO ]: Abstraction has 193 states and 343 transitions. [2018-06-22 01:37:40,156 INFO ]: Interpolant automaton has 13 states. [2018-06-22 01:37:40,157 INFO ]: Start isEmpty. Operand 193 states and 343 transitions. [2018-06-22 01:37:40,164 INFO ]: Finished isEmpty. Found accepting run of length 40 [2018-06-22 01:37:40,164 INFO ]: Found error trace [2018-06-22 01:37:40,164 INFO ]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:40,164 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:40,164 INFO ]: Analyzing trace with hash -854982029, now seen corresponding path program 1 times [2018-06-22 01:37:40,165 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:40,165 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:40,165 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:40,165 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:40,165 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:40,177 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:40,331 INFO ]: Checked inductivity of 30 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 01:37:40,331 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 01:37:40,331 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 01:37:40,332 INFO ]: Interpolant automaton has 4 states [2018-06-22 01:37:40,332 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 01:37:40,332 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 01:37:40,332 INFO ]: Start difference. First operand 193 states and 343 transitions. Second operand 4 states. [2018-06-22 01:37:40,500 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:40,500 INFO ]: Finished difference Result 220 states and 386 transitions. [2018-06-22 01:37:40,500 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-22 01:37:40,500 INFO ]: Start accepts. Automaton has 4 states. Word has length 39 [2018-06-22 01:37:40,500 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:40,502 INFO ]: With dead ends: 220 [2018-06-22 01:37:40,502 INFO ]: Without dead ends: 193 [2018-06-22 01:37:40,502 INFO ]: 0 DeclaredPredicates, 6 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-22 01:37:40,503 INFO ]: Start minimizeSevpa. Operand 193 states. [2018-06-22 01:37:40,513 INFO ]: Finished minimizeSevpa. Reduced states from 193 to 193. [2018-06-22 01:37:40,513 INFO ]: Start removeUnreachable. Operand 193 states. [2018-06-22 01:37:40,516 INFO ]: Finished removeUnreachable. Reduced from 193 states to 193 states and 341 transitions. [2018-06-22 01:37:40,516 INFO ]: Start accepts. Automaton has 193 states and 341 transitions. Word has length 39 [2018-06-22 01:37:40,516 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:40,516 INFO ]: Abstraction has 193 states and 341 transitions. [2018-06-22 01:37:40,516 INFO ]: Interpolant automaton has 4 states. [2018-06-22 01:37:40,517 INFO ]: Start isEmpty. Operand 193 states and 341 transitions. [2018-06-22 01:37:40,524 INFO ]: Finished isEmpty. Found accepting run of length 47 [2018-06-22 01:37:40,524 INFO ]: Found error trace [2018-06-22 01:37:40,524 INFO ]: trace histogram [4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:40,524 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:40,524 INFO ]: Analyzing trace with hash -302174831, now seen corresponding path program 1 times [2018-06-22 01:37:40,524 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:40,524 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:40,525 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:40,525 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:40,525 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:40,567 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:40,790 WARN ]: Spent 126.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-22 01:37:40,937 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-06-22 01:37:41,163 WARN ]: Spent 124.00 ms on a formula simplification that was a NOOP. DAG size: 19 [2018-06-22 01:37:41,774 INFO ]: Checked inductivity of 50 backedges. 6 proven. 31 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-06-22 01:37:41,774 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:37:41,774 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 01:37:41,780 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:41,816 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:41,821 INFO ]: Computing forward predicates... [2018-06-22 01:37:42,446 WARN ]: Spent 151.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-22 01:37:43,666 INFO ]: Checked inductivity of 50 backedges. 17 proven. 20 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-06-22 01:37:43,685 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:37:43,685 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 40 [2018-06-22 01:37:43,685 INFO ]: Interpolant automaton has 40 states [2018-06-22 01:37:43,685 INFO ]: Constructing interpolant automaton starting with 40 interpolants. [2018-06-22 01:37:43,686 INFO ]: CoverageRelationStatistics Valid=95, Invalid=1465, Unknown=0, NotChecked=0, Total=1560 [2018-06-22 01:37:43,686 INFO ]: Start difference. First operand 193 states and 341 transitions. Second operand 40 states. [2018-06-22 01:37:46,197 WARN ]: Spent 228.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 20 [2018-06-22 01:37:46,367 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 81 [2018-06-22 01:37:46,867 WARN ]: Spent 140.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 93 [2018-06-22 01:37:47,034 WARN ]: Spent 117.00 ms on a formula simplification. DAG size of input: 88 DAG size of output: 82 [2018-06-22 01:37:47,911 WARN ]: Spent 113.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 83 [2018-06-22 01:37:48,103 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 87 [2018-06-22 01:37:48,252 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 77 [2018-06-22 01:37:48,536 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 84 [2018-06-22 01:37:49,173 WARN ]: Spent 116.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 79 [2018-06-22 01:37:49,810 WARN ]: Spent 150.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 86 [2018-06-22 01:37:50,087 WARN ]: Spent 165.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 75 [2018-06-22 01:37:51,355 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:51,355 INFO ]: Finished difference Result 745 states and 2992 transitions. [2018-06-22 01:37:51,355 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-06-22 01:37:51,355 INFO ]: Start accepts. Automaton has 40 states. Word has length 46 [2018-06-22 01:37:51,356 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:51,376 INFO ]: With dead ends: 745 [2018-06-22 01:37:51,376 INFO ]: Without dead ends: 745 [2018-06-22 01:37:51,378 INFO ]: 0 DeclaredPredicates, 114 GetRequests, 28 SyntacticMatches, 2 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1545 ImplicationChecksByTransitivity, 7.4s TimeCoverageRelationStatistics Valid=747, Invalid=6563, Unknown=0, NotChecked=0, Total=7310 [2018-06-22 01:37:51,378 INFO ]: Start minimizeSevpa. Operand 745 states. [2018-06-22 01:37:51,471 INFO ]: Finished minimizeSevpa. Reduced states from 745 to 250. [2018-06-22 01:37:51,471 INFO ]: Start removeUnreachable. Operand 250 states. [2018-06-22 01:37:51,475 INFO ]: Finished removeUnreachable. Reduced from 250 states to 250 states and 466 transitions. [2018-06-22 01:37:51,475 INFO ]: Start accepts. Automaton has 250 states and 466 transitions. Word has length 46 [2018-06-22 01:37:51,475 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:51,475 INFO ]: Abstraction has 250 states and 466 transitions. [2018-06-22 01:37:51,475 INFO ]: Interpolant automaton has 40 states. [2018-06-22 01:37:51,475 INFO ]: Start isEmpty. Operand 250 states and 466 transitions. [2018-06-22 01:37:51,482 INFO ]: Finished isEmpty. Found accepting run of length 47 [2018-06-22 01:37:51,482 INFO ]: Found error trace [2018-06-22 01:37:51,482 INFO ]: trace histogram [4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:51,482 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:51,482 INFO ]: Analyzing trace with hash -498688336, now seen corresponding path program 1 times [2018-06-22 01:37:51,482 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:51,482 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:51,483 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:51,483 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:51,483 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:51,493 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:51,643 INFO ]: Checked inductivity of 50 backedges. 29 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-22 01:37:51,643 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:37:51,643 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 01:37:51,649 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:51,685 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:51,689 INFO ]: Computing forward predicates... [2018-06-22 01:37:52,114 INFO ]: Checked inductivity of 50 backedges. 29 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-22 01:37:52,137 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:37:52,137 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 12 [2018-06-22 01:37:52,137 INFO ]: Interpolant automaton has 12 states [2018-06-22 01:37:52,137 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-22 01:37:52,137 INFO ]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2018-06-22 01:37:52,137 INFO ]: Start difference. First operand 250 states and 466 transitions. Second operand 12 states. [2018-06-22 01:37:52,702 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:52,702 INFO ]: Finished difference Result 420 states and 973 transitions. [2018-06-22 01:37:52,702 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2018-06-22 01:37:52,702 INFO ]: Start accepts. Automaton has 12 states. Word has length 46 [2018-06-22 01:37:52,703 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:52,707 INFO ]: With dead ends: 420 [2018-06-22 01:37:52,707 INFO ]: Without dead ends: 420 [2018-06-22 01:37:52,711 INFO ]: 0 DeclaredPredicates, 98 GetRequests, 56 SyntacticMatches, 4 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 364 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=317, Invalid=1243, Unknown=0, NotChecked=0, Total=1560 [2018-06-22 01:37:52,712 INFO ]: Start minimizeSevpa. Operand 420 states. [2018-06-22 01:37:52,731 INFO ]: Finished minimizeSevpa. Reduced states from 420 to 259. [2018-06-22 01:37:52,731 INFO ]: Start removeUnreachable. Operand 259 states. [2018-06-22 01:37:52,736 INFO ]: Finished removeUnreachable. Reduced from 259 states to 259 states and 475 transitions. [2018-06-22 01:37:52,736 INFO ]: Start accepts. Automaton has 259 states and 475 transitions. Word has length 46 [2018-06-22 01:37:52,736 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:52,736 INFO ]: Abstraction has 259 states and 475 transitions. [2018-06-22 01:37:52,736 INFO ]: Interpolant automaton has 12 states. [2018-06-22 01:37:52,736 INFO ]: Start isEmpty. Operand 259 states and 475 transitions. [2018-06-22 01:37:52,744 INFO ]: Finished isEmpty. Found accepting run of length 47 [2018-06-22 01:37:52,744 INFO ]: Found error trace [2018-06-22 01:37:52,744 INFO ]: trace histogram [4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:52,744 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:52,744 INFO ]: Analyzing trace with hash -710969265, now seen corresponding path program 2 times [2018-06-22 01:37:52,744 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:52,744 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:52,745 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:52,745 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:37:52,745 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:52,760 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:53,216 INFO ]: Checked inductivity of 50 backedges. 18 proven. 4 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 01:37:53,216 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:37:53,216 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:37:53,222 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:37:53,258 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:37:53,258 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:53,261 INFO ]: Computing forward predicates... [2018-06-22 01:37:53,668 INFO ]: Checked inductivity of 50 backedges. 36 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2018-06-22 01:37:53,687 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:37:53,687 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 18 [2018-06-22 01:37:53,687 INFO ]: Interpolant automaton has 18 states [2018-06-22 01:37:53,687 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 01:37:53,687 INFO ]: CoverageRelationStatistics Valid=34, Invalid=272, Unknown=0, NotChecked=0, Total=306 [2018-06-22 01:37:53,687 INFO ]: Start difference. First operand 259 states and 475 transitions. Second operand 18 states. [2018-06-22 01:37:56,946 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:37:56,946 INFO ]: Finished difference Result 961 states and 3824 transitions. [2018-06-22 01:37:56,946 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-06-22 01:37:56,946 INFO ]: Start accepts. Automaton has 18 states. Word has length 46 [2018-06-22 01:37:56,947 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:37:56,994 INFO ]: With dead ends: 961 [2018-06-22 01:37:56,994 INFO ]: Without dead ends: 958 [2018-06-22 01:37:56,996 INFO ]: 0 DeclaredPredicates, 175 GetRequests, 74 SyntacticMatches, 2 SemanticMatches, 99 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3346 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=1454, Invalid=8646, Unknown=0, NotChecked=0, Total=10100 [2018-06-22 01:37:56,997 INFO ]: Start minimizeSevpa. Operand 958 states. [2018-06-22 01:37:57,112 INFO ]: Finished minimizeSevpa. Reduced states from 958 to 315. [2018-06-22 01:37:57,112 INFO ]: Start removeUnreachable. Operand 315 states. [2018-06-22 01:37:57,115 INFO ]: Finished removeUnreachable. Reduced from 315 states to 315 states and 623 transitions. [2018-06-22 01:37:57,115 INFO ]: Start accepts. Automaton has 315 states and 623 transitions. Word has length 46 [2018-06-22 01:37:57,115 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:37:57,115 INFO ]: Abstraction has 315 states and 623 transitions. [2018-06-22 01:37:57,115 INFO ]: Interpolant automaton has 18 states. [2018-06-22 01:37:57,115 INFO ]: Start isEmpty. Operand 315 states and 623 transitions. [2018-06-22 01:37:57,126 INFO ]: Finished isEmpty. Found accepting run of length 47 [2018-06-22 01:37:57,126 INFO ]: Found error trace [2018-06-22 01:37:57,126 INFO ]: trace histogram [4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:37:57,126 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:37:57,126 INFO ]: Analyzing trace with hash -271155024, now seen corresponding path program 3 times [2018-06-22 01:37:57,126 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:37:57,126 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:37:57,127 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:57,127 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:37:57,127 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:37:57,143 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:57,445 INFO ]: Checked inductivity of 50 backedges. 19 proven. 18 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-06-22 01:37:57,446 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:37:57,446 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:37:57,458 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 01:37:57,498 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 01:37:57,498 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:37:57,503 INFO ]: Computing forward predicates... [2018-06-22 01:37:57,910 INFO ]: Checked inductivity of 50 backedges. 9 proven. 28 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-06-22 01:37:57,930 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:37:57,930 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 23] total 34 [2018-06-22 01:37:57,930 INFO ]: Interpolant automaton has 34 states [2018-06-22 01:37:57,930 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-22 01:37:57,931 INFO ]: CoverageRelationStatistics Valid=75, Invalid=1047, Unknown=0, NotChecked=0, Total=1122 [2018-06-22 01:37:57,931 INFO ]: Start difference. First operand 315 states and 623 transitions. Second operand 34 states. [2018-06-22 01:38:04,334 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:38:04,334 INFO ]: Finished difference Result 994 states and 3401 transitions. [2018-06-22 01:38:04,334 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 73 states. [2018-06-22 01:38:04,334 INFO ]: Start accepts. Automaton has 34 states. Word has length 46 [2018-06-22 01:38:04,334 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:38:04,359 INFO ]: With dead ends: 994 [2018-06-22 01:38:04,359 INFO ]: Without dead ends: 994 [2018-06-22 01:38:04,363 INFO ]: 0 DeclaredPredicates, 136 GetRequests, 39 SyntacticMatches, 1 SemanticMatches, 96 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2095 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=1189, Invalid=8317, Unknown=0, NotChecked=0, Total=9506 [2018-06-22 01:38:04,364 INFO ]: Start minimizeSevpa. Operand 994 states. [2018-06-22 01:38:04,455 INFO ]: Finished minimizeSevpa. Reduced states from 994 to 333. [2018-06-22 01:38:04,455 INFO ]: Start removeUnreachable. Operand 333 states. [2018-06-22 01:38:04,459 INFO ]: Finished removeUnreachable. Reduced from 333 states to 333 states and 639 transitions. [2018-06-22 01:38:04,459 INFO ]: Start accepts. Automaton has 333 states and 639 transitions. Word has length 46 [2018-06-22 01:38:04,459 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:38:04,459 INFO ]: Abstraction has 333 states and 639 transitions. [2018-06-22 01:38:04,459 INFO ]: Interpolant automaton has 34 states. [2018-06-22 01:38:04,459 INFO ]: Start isEmpty. Operand 333 states and 639 transitions. [2018-06-22 01:38:04,468 INFO ]: Finished isEmpty. Found accepting run of length 53 [2018-06-22 01:38:04,468 INFO ]: Found error trace [2018-06-22 01:38:04,468 INFO ]: trace histogram [5, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:38:04,468 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:38:04,469 INFO ]: Analyzing trace with hash 338552203, now seen corresponding path program 1 times [2018-06-22 01:38:04,469 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:38:04,469 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:38:04,469 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:38:04,469 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:38:04,469 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:38:04,486 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:38:04,623 INFO ]: Checked inductivity of 64 backedges. 23 proven. 19 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-22 01:38:04,623 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:38:04,623 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:38:04,629 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:38:04,678 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:38:04,682 INFO ]: Computing forward predicates... [2018-06-22 01:38:04,735 INFO ]: Checked inductivity of 64 backedges. 43 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 01:38:04,755 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-22 01:38:04,755 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [14] total 18 [2018-06-22 01:38:04,755 INFO ]: Interpolant automaton has 18 states [2018-06-22 01:38:04,755 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-22 01:38:04,755 INFO ]: CoverageRelationStatistics Valid=36, Invalid=270, Unknown=0, NotChecked=0, Total=306 [2018-06-22 01:38:04,755 INFO ]: Start difference. First operand 333 states and 639 transitions. Second operand 18 states. [2018-06-22 01:38:06,320 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:38:06,320 INFO ]: Finished difference Result 1037 states and 2218 transitions. [2018-06-22 01:38:06,321 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 58 states. [2018-06-22 01:38:06,321 INFO ]: Start accepts. Automaton has 18 states. Word has length 52 [2018-06-22 01:38:06,321 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:38:06,324 INFO ]: With dead ends: 1037 [2018-06-22 01:38:06,324 INFO ]: Without dead ends: 350 [2018-06-22 01:38:06,325 INFO ]: 0 DeclaredPredicates, 143 GetRequests, 75 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1347 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=968, Invalid=3862, Unknown=0, NotChecked=0, Total=4830 [2018-06-22 01:38:06,325 INFO ]: Start minimizeSevpa. Operand 350 states. [2018-06-22 01:38:06,340 INFO ]: Finished minimizeSevpa. Reduced states from 350 to 237. [2018-06-22 01:38:06,340 INFO ]: Start removeUnreachable. Operand 237 states. [2018-06-22 01:38:06,341 INFO ]: Finished removeUnreachable. Reduced from 237 states to 237 states and 385 transitions. [2018-06-22 01:38:06,341 INFO ]: Start accepts. Automaton has 237 states and 385 transitions. Word has length 52 [2018-06-22 01:38:06,341 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:38:06,341 INFO ]: Abstraction has 237 states and 385 transitions. [2018-06-22 01:38:06,341 INFO ]: Interpolant automaton has 18 states. [2018-06-22 01:38:06,341 INFO ]: Start isEmpty. Operand 237 states and 385 transitions. [2018-06-22 01:38:06,345 INFO ]: Finished isEmpty. Found accepting run of length 53 [2018-06-22 01:38:06,345 INFO ]: Found error trace [2018-06-22 01:38:06,345 INFO ]: trace histogram [5, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:38:06,345 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:38:06,345 INFO ]: Analyzing trace with hash -1022720337, now seen corresponding path program 2 times [2018-06-22 01:38:06,345 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:38:06,345 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:38:06,345 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:38:06,345 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:38:06,345 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:38:06,361 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:38:06,971 INFO ]: Checked inductivity of 64 backedges. 38 proven. 9 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-22 01:38:06,971 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:38:06,971 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:38:06,977 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 01:38:07,021 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 01:38:07,022 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:38:07,024 INFO ]: Computing forward predicates... [2018-06-22 01:38:07,150 INFO ]: Checked inductivity of 64 backedges. 36 proven. 14 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2018-06-22 01:38:07,169 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:38:07,169 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 8] total 21 [2018-06-22 01:38:07,169 INFO ]: Interpolant automaton has 21 states [2018-06-22 01:38:07,169 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 01:38:07,170 INFO ]: CoverageRelationStatistics Valid=46, Invalid=374, Unknown=0, NotChecked=0, Total=420 [2018-06-22 01:38:07,170 INFO ]: Start difference. First operand 237 states and 385 transitions. Second operand 21 states. [2018-06-22 01:38:09,767 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 01:38:09,767 INFO ]: Finished difference Result 575 states and 1143 transitions. [2018-06-22 01:38:09,767 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-06-22 01:38:09,767 INFO ]: Start accepts. Automaton has 21 states. Word has length 52 [2018-06-22 01:38:09,767 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 01:38:09,773 INFO ]: With dead ends: 575 [2018-06-22 01:38:09,773 INFO ]: Without dead ends: 524 [2018-06-22 01:38:09,773 INFO ]: 0 DeclaredPredicates, 141 GetRequests, 65 SyntacticMatches, 6 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1277 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=761, Invalid=4351, Unknown=0, NotChecked=0, Total=5112 [2018-06-22 01:38:09,773 INFO ]: Start minimizeSevpa. Operand 524 states. [2018-06-22 01:38:09,796 INFO ]: Finished minimizeSevpa. Reduced states from 524 to 306. [2018-06-22 01:38:09,796 INFO ]: Start removeUnreachable. Operand 306 states. [2018-06-22 01:38:09,798 INFO ]: Finished removeUnreachable. Reduced from 306 states to 306 states and 542 transitions. [2018-06-22 01:38:09,798 INFO ]: Start accepts. Automaton has 306 states and 542 transitions. Word has length 52 [2018-06-22 01:38:09,799 INFO ]: Finished accepts. word is rejected. [2018-06-22 01:38:09,799 INFO ]: Abstraction has 306 states and 542 transitions. [2018-06-22 01:38:09,799 INFO ]: Interpolant automaton has 21 states. [2018-06-22 01:38:09,799 INFO ]: Start isEmpty. Operand 306 states and 542 transitions. [2018-06-22 01:38:09,803 INFO ]: Finished isEmpty. Found accepting run of length 62 [2018-06-22 01:38:09,803 INFO ]: Found error trace [2018-06-22 01:38:09,803 INFO ]: trace histogram [6, 5, 5, 5, 5, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 01:38:09,803 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 01:38:09,803 INFO ]: Analyzing trace with hash 432649751, now seen corresponding path program 1 times [2018-06-22 01:38:09,803 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 01:38:09,803 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 01:38:09,804 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:38:09,804 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 01:38:09,804 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 01:38:09,819 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:38:10,247 INFO ]: Checked inductivity of 99 backedges. 37 proven. 35 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2018-06-22 01:38:10,247 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 01:38:10,247 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 01:38:10,254 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 01:38:10,304 INFO ]: Conjunction of SSA is unsat [2018-06-22 01:38:10,308 INFO ]: Computing forward predicates... [2018-06-22 01:38:10,638 INFO ]: Checked inductivity of 99 backedges. 30 proven. 45 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2018-06-22 01:38:10,657 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 01:38:10,657 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 17] total 30 [2018-06-22 01:38:10,657 INFO ]: Interpolant automaton has 30 states [2018-06-22 01:38:10,658 INFO ]: Constructing interpolant automaton starting with 30 interpolants. [2018-06-22 01:38:10,658 INFO ]: CoverageRelationStatistics Valid=64, Invalid=806, Unknown=0, NotChecked=0, Total=870 [2018-06-22 01:38:10,658 INFO ]: Start difference. First operand 306 states and 542 transitions. Second operand 30 states. Received shutdown request... [2018-06-22 01:38:16,514 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 145 states. [2018-06-22 01:38:16,514 WARN ]: Verification canceled [2018-06-22 01:38:16,518 WARN ]: Timeout [2018-06-22 01:38:16,518 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 01:38:16 BoogieIcfgContainer [2018-06-22 01:38:16,518 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 01:38:16,518 INFO ]: Toolchain (without parser) took 59443.81 ms. Allocated memory was 309.3 MB in the beginning and 697.8 MB in the end (delta: 388.5 MB). Free memory was 263.7 MB in the beginning and 606.4 MB in the end (delta: -342.6 MB). Peak memory consumption was 45.9 MB. Max. memory is 3.6 GB. [2018-06-22 01:38:16,519 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 01:38:16,519 INFO ]: ChcToBoogie took 54.31 ms. Allocated memory is still 309.3 MB. Free memory was 262.7 MB in the beginning and 260.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:38:16,519 INFO ]: Boogie Preprocessor took 46.57 ms. Allocated memory is still 309.3 MB. Free memory was 260.7 MB in the beginning and 259.6 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. [2018-06-22 01:38:16,520 INFO ]: RCFGBuilder took 380.12 ms. Allocated memory is still 309.3 MB. Free memory was 259.6 MB in the beginning and 245.6 MB in the end (delta: 14.0 MB). Peak memory consumption was 14.0 MB. Max. memory is 3.6 GB. [2018-06-22 01:38:16,520 INFO ]: TraceAbstraction took 58950.73 ms. Allocated memory was 309.3 MB in the beginning and 697.8 MB in the end (delta: 388.5 MB). Free memory was 244.6 MB in the beginning and 606.4 MB in the end (delta: -361.8 MB). Peak memory consumption was 26.7 MB. Max. memory is 3.6 GB. [2018-06-22 01:38:16,522 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 309.3 MB. Free memory is still 274.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 54.31 ms. Allocated memory is still 309.3 MB. Free memory was 262.7 MB in the beginning and 260.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 46.57 ms. Allocated memory is still 309.3 MB. Free memory was 260.7 MB in the beginning and 259.6 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 380.12 ms. Allocated memory is still 309.3 MB. Free memory was 259.6 MB in the beginning and 245.6 MB in the end (delta: 14.0 MB). Peak memory consumption was 14.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 58950.73 ms. Allocated memory was 309.3 MB in the beginning and 697.8 MB in the end (delta: 388.5 MB). Free memory was 244.6 MB in the beginning and 606.4 MB in the end (delta: -361.8 MB). Peak memory consumption was 26.7 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was constructing difference of abstraction (306states) and interpolant automaton (currently 145 states, 30 states before enhancement), while ReachableStatesComputation was computing reachable states (614 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 23 locations, 1 error locations. TIMEOUT Result, 58.9s OverallTime, 20 OverallIterations, 6 TraceHistogramMax, 46.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 2420 SDtfs, 5465 SDslu, 22296 SDs, 0 SdLazy, 24732 SolverSat, 5185 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 18.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1602 GetRequests, 616 SyntacticMatches, 24 SemanticMatches, 962 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29256 ImplicationChecksByTransitivity, 33.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=333occurred in iteration=17, 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.9s AutomataMinimizationTime, 19 MinimizatonAttempts, 4096 StatesRemovedByMinimization, 16 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 9.7s InterpolantComputationTime, 1156 NumberOfCodeBlocks, 1156 NumberOfCodeBlocksAsserted, 37 NumberOfCheckSat, 1124 ConstructedInterpolants, 8 QuantifiedInterpolants, 167795 SizeOfPredicates, 251 NumberOfNonLiveVariables, 4330 ConjunctsInSsa, 501 ConjunctsInUnsatCore, 32 InterpolantComputations, 10 PerfectInterpolantSequences, 792/1065 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/array_reverse_once1_abstracted.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_01-38-16-618.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/array_reverse_once1_abstracted.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_01-38-16-618.csv Completed graceful shutdown