java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data --generate-csv --csv-dir csv -tc ../../../trunk/examples/toolchains/AutomizerBplTransformed.xml -s ../../../trunk/examples/settings/heapseparator/heapsep-2018-09-18.epf -i ../../../trunk/examples/programs/20181010-MemSafetyPathprograms/count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-b8f97f7-m [2018-10-10 16:30:19,012 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-10 16:30:19,014 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-10 16:30:19,026 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-10 16:30:19,027 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-10 16:30:19,028 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-10 16:30:19,029 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-10 16:30:19,031 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-10 16:30:19,032 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-10 16:30:19,033 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-10 16:30:19,034 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-10 16:30:19,034 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-10 16:30:19,035 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-10 16:30:19,036 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-10 16:30:19,037 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-10 16:30:19,038 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-10 16:30:19,039 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-10 16:30:19,041 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-10 16:30:19,043 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-10 16:30:19,044 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-10 16:30:19,045 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-10 16:30:19,046 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-10 16:30:19,049 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-10 16:30:19,049 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-10 16:30:19,049 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-10 16:30:19,050 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-10 16:30:19,051 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-10 16:30:19,052 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-10 16:30:19,053 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-10 16:30:19,054 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-10 16:30:19,054 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-10 16:30:19,055 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-10 16:30:19,055 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-10 16:30:19,055 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-10 16:30:19,056 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-10 16:30:19,057 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-10 16:30:19,057 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/heapseparator/heapsep-2018-09-18.epf [2018-10-10 16:30:19,067 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-10 16:30:19,067 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-10 16:30:19,068 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-10 16:30:19,068 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-10 16:30:19,068 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-10 16:30:19,069 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-10 16:30:19,069 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-10 16:30:19,070 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-10 16:30:19,070 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-10 16:30:19,070 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-10 16:30:19,070 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-10 16:30:19,070 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-10 16:30:19,071 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-10 16:30:19,072 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-10 16:30:19,072 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-10 16:30:19,138 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-10 16:30:19,156 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-10 16:30:19,161 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-10 16:30:19,165 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-10 16:30:19,165 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-10 16:30:19,166 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl [2018-10-10 16:30:19,166 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl' [2018-10-10 16:30:19,241 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-10 16:30:19,242 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-10-10 16:30:19,243 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-10 16:30:19,243 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-10 16:30:19,244 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-10 16:30:19,272 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:30:19" (1/1) ... [2018-10-10 16:30:19,274 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:30:19" (1/1) ... [2018-10-10 16:30:19,289 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:30:19" (1/1) ... [2018-10-10 16:30:19,290 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:30:19" (1/1) ... [2018-10-10 16:30:19,295 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:30:19" (1/1) ... [2018-10-10 16:30:19,297 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:30:19" (1/1) ... [2018-10-10 16:30:19,298 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:30:19" (1/1) ... [2018-10-10 16:30:19,300 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-10 16:30:19,301 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-10 16:30:19,301 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-10 16:30:19,302 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-10 16:30:19,303 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:30:19" (1/1) ... No working directory specified, using /storage/repos/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-10-10 16:30:19,380 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2018-10-10 16:30:19,380 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-10 16:30:19,380 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-10 16:30:19,866 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-10 16:30:19,867 INFO L202 PluginConnector]: Adding new model count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 04:30:19 BoogieIcfgContainer [2018-10-10 16:30:19,867 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-10 16:30:19,868 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-10-10 16:30:19,868 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-10-10 16:30:19,869 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-10-10 16:30:19,873 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 04:30:19" (1/1) ... [2018-10-10 16:30:19,882 INFO L137 apSepIcfgTransformer]: HeapSepIcfgTransformer: Starting heap partitioning [2018-10-10 16:30:19,882 INFO L138 apSepIcfgTransformer]: To be partitioned heap arrays found [#memory_int] [2018-10-10 16:30:19,918 INFO L191 apSepIcfgTransformer]: Heap separator: starting loc-array-style preprocessing [2018-10-10 16:30:19,955 INFO L217 apSepIcfgTransformer]: finished MemlocArrayUpdater [2018-10-10 16:30:19,971 INFO L280 apSepIcfgTransformer]: finished preprocessing for the equality analysis [2018-10-10 16:30:20,036 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=1) [2018-10-10 16:30:24,082 INFO L315 AbstractInterpreter]: Visited 61 different actions 166 times. Merged at 34 different actions 99 times. Widened at 1 different actions 2 times. Found 4 fixpoints after 3 different actions. Largest state had 0 variables. [2018-10-10 16:30:24,085 INFO L304 apSepIcfgTransformer]: finished equality analysis [2018-10-10 16:30:24,089 INFO L316 apSepIcfgTransformer]: Finished detection of select terms ("array reads") [2018-10-10 16:30:24,098 WARN L152 HeapPartitionManager]: No literal set constraint found for loc-array access (select |#loc_#memory_int_(Array-Int-#locsort1)| |v_ULTIMATE.start_read~int_#ptr.base_7|) at (assume read~int_#value == #memory_int[read~int_#ptr.base][read~int_#ptr.offset];) [2018-10-10 16:30:24,100 WARN L152 HeapPartitionManager]: No literal set constraint found for loc-array access (select (select |#loc_#memory_int_(Array-Int-(Array-Int-#locsort2))| |v_ULTIMATE.start_read~int_#ptr.base_7|) |v_ULTIMATE.start_read~int_#ptr.offset_5|) at (assume read~int_#value == #memory_int[read~int_#ptr.base][read~int_#ptr.offset];) [2018-10-10 16:30:24,125 WARN L152 HeapPartitionManager]: No literal set constraint found for loc-array access (select |v_#locv_ULTIMATE.start_write~int_old_#memory_int_2_1_1| |v_ULTIMATE.start_write~int_#ptr.base_6|) at (assume #memory_int == write~int_old_#memory_int[write~int_#ptr.base := write~int_old_#memory_int[write~int_#ptr.base][write~int_#ptr.offset := write~int_#value]];) [2018-10-10 16:30:24,126 INFO L232 HeapPartitionManager]: partitioning result: [2018-10-10 16:30:24,127 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-10 16:30:24,127 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-10 16:30:24,127 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-10 16:30:24,128 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-10 16:30:24,128 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-10 16:30:24,128 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-10 16:30:24,128 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-10 16:30:24,129 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-10 16:30:24,129 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-10 16:30:24,129 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-10 16:30:24,129 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-10 16:30:24,129 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-10 16:30:24,130 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-10 16:30:24,130 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-10 16:30:24,131 INFO L145 ransitionTransformer]: executing heap partitioning transformation [2018-10-10 16:30:24,150 INFO L202 PluginConnector]: Adding new model count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 10.10 04:30:24 BasicIcfg [2018-10-10 16:30:24,150 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-10-10 16:30:24,151 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-10 16:30:24,151 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-10 16:30:24,154 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-10 16:30:24,155 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:30:19" (1/3) ... [2018-10-10 16:30:24,156 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63c8dedf and model type count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.10 04:30:24, skipping insertion in model container [2018-10-10 16:30:24,156 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 04:30:19" (2/3) ... [2018-10-10 16:30:24,157 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63c8dedf and model type count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 10.10 04:30:24, skipping insertion in model container [2018-10-10 16:30:24,157 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 10.10 04:30:24" (3/3) ... [2018-10-10 16:30:24,158 INFO L112 eAbstractionObserver]: Analyzing ICFG memPartitionedIcfg [2018-10-10 16:30:24,169 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-10 16:30:24,178 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-10 16:30:24,196 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-10 16:30:24,227 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-10 16:30:24,228 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-10 16:30:24,228 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-10 16:30:24,228 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-10 16:30:24,229 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-10 16:30:24,229 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-10 16:30:24,229 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-10 16:30:24,229 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-10 16:30:24,229 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-10 16:30:24,243 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states. [2018-10-10 16:30:24,250 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-10-10 16:30:24,250 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:24,252 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:24,253 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:24,258 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:24,259 INFO L82 PathProgramCache]: Analyzing trace with hash 964056693, now seen corresponding path program 1 times [2018-10-10 16:30:24,326 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:24,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:24,671 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:24,674 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-10 16:30:24,675 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-10 16:30:24,679 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-10 16:30:24,692 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-10 16:30:24,693 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-10 16:30:24,696 INFO L87 Difference]: Start difference. First operand 60 states. Second operand 4 states. [2018-10-10 16:30:24,955 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:24,956 INFO L93 Difference]: Finished difference Result 73 states and 74 transitions. [2018-10-10 16:30:24,957 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-10 16:30:24,958 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 32 [2018-10-10 16:30:24,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:25,044 INFO L225 Difference]: With dead ends: 73 [2018-10-10 16:30:25,044 INFO L226 Difference]: Without dead ends: 73 [2018-10-10 16:30:25,046 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-10 16:30:25,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2018-10-10 16:30:25,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 59. [2018-10-10 16:30:25,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2018-10-10 16:30:25,087 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 60 transitions. [2018-10-10 16:30:25,089 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 60 transitions. Word has length 32 [2018-10-10 16:30:25,089 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:25,089 INFO L481 AbstractCegarLoop]: Abstraction has 59 states and 60 transitions. [2018-10-10 16:30:25,089 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-10 16:30:25,090 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 60 transitions. [2018-10-10 16:30:25,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2018-10-10 16:30:25,093 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:25,093 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:25,094 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:25,094 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:25,094 INFO L82 PathProgramCache]: Analyzing trace with hash 575190275, now seen corresponding path program 1 times [2018-10-10 16:30:25,096 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:25,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:25,629 WARN L178 SmtUtils]: Spent 220.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 17 [2018-10-10 16:30:25,802 WARN L178 SmtUtils]: Spent 135.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 16 [2018-10-10 16:30:26,011 WARN L178 SmtUtils]: Spent 187.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 14 [2018-10-10 16:30:26,368 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:26,369 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:26,369 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-10-10 16:30:26,371 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-10 16:30:26,371 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-10 16:30:26,371 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2018-10-10 16:30:26,372 INFO L87 Difference]: Start difference. First operand 59 states and 60 transitions. Second operand 12 states. [2018-10-10 16:30:27,016 WARN L178 SmtUtils]: Spent 313.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 24 [2018-10-10 16:30:27,307 WARN L178 SmtUtils]: Spent 126.00 ms on a formula simplification that was a NOOP. DAG size: 28 [2018-10-10 16:30:27,490 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:27,490 INFO L93 Difference]: Finished difference Result 121 states and 123 transitions. [2018-10-10 16:30:27,490 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-10 16:30:27,490 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 48 [2018-10-10 16:30:27,491 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:27,494 INFO L225 Difference]: With dead ends: 121 [2018-10-10 16:30:27,494 INFO L226 Difference]: Without dead ends: 121 [2018-10-10 16:30:27,495 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2018-10-10 16:30:27,495 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2018-10-10 16:30:27,503 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 80. [2018-10-10 16:30:27,504 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-10-10 16:30:27,505 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 82 transitions. [2018-10-10 16:30:27,505 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 82 transitions. Word has length 48 [2018-10-10 16:30:27,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:27,506 INFO L481 AbstractCegarLoop]: Abstraction has 80 states and 82 transitions. [2018-10-10 16:30:27,506 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-10 16:30:27,506 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 82 transitions. [2018-10-10 16:30:27,508 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-10-10 16:30:27,508 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:27,509 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:27,509 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:27,509 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:27,510 INFO L82 PathProgramCache]: Analyzing trace with hash -1278790061, now seen corresponding path program 1 times [2018-10-10 16:30:27,511 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:27,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:27,698 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:27,698 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:27,699 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-10 16:30:27,699 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-10 16:30:27,700 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-10 16:30:27,700 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-10-10 16:30:27,700 INFO L87 Difference]: Start difference. First operand 80 states and 82 transitions. Second operand 9 states. [2018-10-10 16:30:27,975 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:27,976 INFO L93 Difference]: Finished difference Result 105 states and 106 transitions. [2018-10-10 16:30:27,976 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-10 16:30:27,976 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 62 [2018-10-10 16:30:27,977 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:27,979 INFO L225 Difference]: With dead ends: 105 [2018-10-10 16:30:27,979 INFO L226 Difference]: Without dead ends: 89 [2018-10-10 16:30:27,979 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2018-10-10 16:30:27,980 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-10-10 16:30:27,984 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 75. [2018-10-10 16:30:27,985 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-10-10 16:30:27,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 76 transitions. [2018-10-10 16:30:27,986 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 76 transitions. Word has length 62 [2018-10-10 16:30:27,986 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:27,986 INFO L481 AbstractCegarLoop]: Abstraction has 75 states and 76 transitions. [2018-10-10 16:30:27,987 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-10 16:30:27,987 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 76 transitions. [2018-10-10 16:30:27,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-10-10 16:30:27,989 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:27,989 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:27,989 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:27,989 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:27,990 INFO L82 PathProgramCache]: Analyzing trace with hash 1155020689, now seen corresponding path program 2 times [2018-10-10 16:30:27,992 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:28,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:28,280 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-10-10 16:30:28,281 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:28,281 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-10 16:30:28,281 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-10 16:30:28,282 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-10 16:30:28,282 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-10-10 16:30:28,282 INFO L87 Difference]: Start difference. First operand 75 states and 76 transitions. Second operand 9 states. [2018-10-10 16:30:28,636 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:28,637 INFO L93 Difference]: Finished difference Result 88 states and 89 transitions. [2018-10-10 16:30:28,637 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-10 16:30:28,638 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 64 [2018-10-10 16:30:28,638 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:28,639 INFO L225 Difference]: With dead ends: 88 [2018-10-10 16:30:28,639 INFO L226 Difference]: Without dead ends: 88 [2018-10-10 16:30:28,640 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2018-10-10 16:30:28,640 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2018-10-10 16:30:28,645 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 79. [2018-10-10 16:30:28,645 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-10-10 16:30:28,646 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 80 transitions. [2018-10-10 16:30:28,646 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 80 transitions. Word has length 64 [2018-10-10 16:30:28,647 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:28,647 INFO L481 AbstractCegarLoop]: Abstraction has 79 states and 80 transitions. [2018-10-10 16:30:28,647 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-10 16:30:28,647 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 80 transitions. [2018-10-10 16:30:28,650 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2018-10-10 16:30:28,650 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:28,650 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:28,650 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:28,651 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:28,651 INFO L82 PathProgramCache]: Analyzing trace with hash -205510559, now seen corresponding path program 2 times [2018-10-10 16:30:28,652 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:28,669 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:29,068 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:29,068 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:29,068 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-10 16:30:29,069 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-10 16:30:29,069 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-10 16:30:29,069 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-10-10 16:30:29,070 INFO L87 Difference]: Start difference. First operand 79 states and 80 transitions. Second operand 13 states. [2018-10-10 16:30:30,163 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:30,164 INFO L93 Difference]: Finished difference Result 174 states and 176 transitions. [2018-10-10 16:30:30,164 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-10 16:30:30,165 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 78 [2018-10-10 16:30:30,166 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:30,168 INFO L225 Difference]: With dead ends: 174 [2018-10-10 16:30:30,168 INFO L226 Difference]: Without dead ends: 174 [2018-10-10 16:30:30,169 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 184 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=135, Invalid=735, Unknown=0, NotChecked=0, Total=870 [2018-10-10 16:30:30,169 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-10-10 16:30:30,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 93. [2018-10-10 16:30:30,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-10-10 16:30:30,177 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 94 transitions. [2018-10-10 16:30:30,177 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 94 transitions. Word has length 78 [2018-10-10 16:30:30,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:30,178 INFO L481 AbstractCegarLoop]: Abstraction has 93 states and 94 transitions. [2018-10-10 16:30:30,178 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-10 16:30:30,178 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 94 transitions. [2018-10-10 16:30:30,180 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2018-10-10 16:30:30,180 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:30,180 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:30,180 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:30,181 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:30,181 INFO L82 PathProgramCache]: Analyzing trace with hash -1203081935, now seen corresponding path program 3 times [2018-10-10 16:30:30,182 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:30,200 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:30,360 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:30,361 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:30,361 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-10 16:30:30,361 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-10 16:30:30,361 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-10 16:30:30,362 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-10-10 16:30:30,362 INFO L87 Difference]: Start difference. First operand 93 states and 94 transitions. Second operand 13 states. [2018-10-10 16:30:30,996 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:30,997 INFO L93 Difference]: Finished difference Result 153 states and 154 transitions. [2018-10-10 16:30:30,997 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-10 16:30:30,997 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 92 [2018-10-10 16:30:30,999 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:31,000 INFO L225 Difference]: With dead ends: 153 [2018-10-10 16:30:31,000 INFO L226 Difference]: Without dead ends: 123 [2018-10-10 16:30:31,001 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=117, Invalid=483, Unknown=0, NotChecked=0, Total=600 [2018-10-10 16:30:31,002 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2018-10-10 16:30:31,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 109. [2018-10-10 16:30:31,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-10-10 16:30:31,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 110 transitions. [2018-10-10 16:30:31,009 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 110 transitions. Word has length 92 [2018-10-10 16:30:31,010 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:31,010 INFO L481 AbstractCegarLoop]: Abstraction has 109 states and 110 transitions. [2018-10-10 16:30:31,010 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-10 16:30:31,010 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 110 transitions. [2018-10-10 16:30:31,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2018-10-10 16:30:31,012 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:31,012 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:31,012 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:31,013 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:31,013 INFO L82 PathProgramCache]: Analyzing trace with hash -397749569, now seen corresponding path program 4 times [2018-10-10 16:30:31,014 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:31,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:31,383 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 0 proven. 73 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:31,384 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:31,384 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-10 16:30:31,384 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-10 16:30:31,385 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-10 16:30:31,385 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=238, Unknown=0, NotChecked=0, Total=272 [2018-10-10 16:30:31,385 INFO L87 Difference]: Start difference. First operand 109 states and 110 transitions. Second operand 17 states. [2018-10-10 16:30:32,840 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:32,841 INFO L93 Difference]: Finished difference Result 143 states and 144 transitions. [2018-10-10 16:30:32,841 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-10 16:30:32,842 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 108 [2018-10-10 16:30:32,842 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:32,843 INFO L225 Difference]: With dead ends: 143 [2018-10-10 16:30:32,843 INFO L226 Difference]: Without dead ends: 143 [2018-10-10 16:30:32,845 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=185, Invalid=1075, Unknown=0, NotChecked=0, Total=1260 [2018-10-10 16:30:32,845 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2018-10-10 16:30:32,850 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 123. [2018-10-10 16:30:32,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 123 states. [2018-10-10 16:30:32,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 124 transitions. [2018-10-10 16:30:32,856 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 124 transitions. Word has length 108 [2018-10-10 16:30:32,857 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:32,857 INFO L481 AbstractCegarLoop]: Abstraction has 123 states and 124 transitions. [2018-10-10 16:30:32,857 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-10 16:30:32,857 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 124 transitions. [2018-10-10 16:30:32,862 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2018-10-10 16:30:32,862 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:32,862 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:32,862 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:32,863 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:32,863 INFO L82 PathProgramCache]: Analyzing trace with hash -1502307569, now seen corresponding path program 5 times [2018-10-10 16:30:32,864 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:32,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:33,179 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 27 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:33,180 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:33,180 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-10 16:30:33,180 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-10 16:30:33,180 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-10 16:30:33,181 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2018-10-10 16:30:33,181 INFO L87 Difference]: Start difference. First operand 123 states and 124 transitions. Second operand 17 states. [2018-10-10 16:30:33,709 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:33,709 INFO L93 Difference]: Finished difference Result 197 states and 198 transitions. [2018-10-10 16:30:33,709 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-10 16:30:33,710 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 122 [2018-10-10 16:30:33,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:33,712 INFO L225 Difference]: With dead ends: 197 [2018-10-10 16:30:33,712 INFO L226 Difference]: Without dead ends: 153 [2018-10-10 16:30:33,713 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 216 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=198, Invalid=924, Unknown=0, NotChecked=0, Total=1122 [2018-10-10 16:30:33,713 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2018-10-10 16:30:33,718 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 139. [2018-10-10 16:30:33,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 139 states. [2018-10-10 16:30:33,719 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 140 transitions. [2018-10-10 16:30:33,719 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 140 transitions. Word has length 122 [2018-10-10 16:30:33,720 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:33,720 INFO L481 AbstractCegarLoop]: Abstraction has 139 states and 140 transitions. [2018-10-10 16:30:33,720 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-10 16:30:33,720 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 140 transitions. [2018-10-10 16:30:33,722 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2018-10-10 16:30:33,722 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:33,722 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:33,723 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:33,723 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:33,723 INFO L82 PathProgramCache]: Analyzing trace with hash 1184191517, now seen corresponding path program 6 times [2018-10-10 16:30:33,724 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:33,743 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:34,257 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 14 proven. 140 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:34,258 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:34,258 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-10 16:30:34,258 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-10 16:30:34,259 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-10 16:30:34,259 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=375, Unknown=0, NotChecked=0, Total=420 [2018-10-10 16:30:34,259 INFO L87 Difference]: Start difference. First operand 139 states and 140 transitions. Second operand 21 states. [2018-10-10 16:30:35,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:35,974 INFO L93 Difference]: Finished difference Result 173 states and 174 transitions. [2018-10-10 16:30:35,974 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-10 16:30:35,974 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 138 [2018-10-10 16:30:35,975 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:35,976 INFO L225 Difference]: With dead ends: 173 [2018-10-10 16:30:35,976 INFO L226 Difference]: Without dead ends: 173 [2018-10-10 16:30:35,978 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 330 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=259, Invalid=1721, Unknown=0, NotChecked=0, Total=1980 [2018-10-10 16:30:35,979 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2018-10-10 16:30:35,983 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 153. [2018-10-10 16:30:35,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 153 states. [2018-10-10 16:30:35,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 154 transitions. [2018-10-10 16:30:35,984 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 154 transitions. Word has length 138 [2018-10-10 16:30:35,984 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:35,985 INFO L481 AbstractCegarLoop]: Abstraction has 153 states and 154 transitions. [2018-10-10 16:30:35,985 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-10 16:30:35,985 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 154 transitions. [2018-10-10 16:30:35,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 153 [2018-10-10 16:30:35,986 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:35,987 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:35,987 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:35,987 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:35,987 INFO L82 PathProgramCache]: Analyzing trace with hash -900046867, now seen corresponding path program 7 times [2018-10-10 16:30:35,988 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:36,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:36,993 INFO L134 CoverageAnalysis]: Checked inductivity of 200 backedges. 60 proven. 140 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:36,994 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:36,994 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-10 16:30:36,994 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-10 16:30:36,994 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-10 16:30:36,995 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=354, Unknown=0, NotChecked=0, Total=420 [2018-10-10 16:30:36,995 INFO L87 Difference]: Start difference. First operand 153 states and 154 transitions. Second operand 21 states. [2018-10-10 16:30:37,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:37,651 INFO L93 Difference]: Finished difference Result 241 states and 242 transitions. [2018-10-10 16:30:37,651 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-10-10 16:30:37,652 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 152 [2018-10-10 16:30:37,652 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:37,653 INFO L225 Difference]: With dead ends: 241 [2018-10-10 16:30:37,653 INFO L226 Difference]: Without dead ends: 183 [2018-10-10 16:30:37,654 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 384 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=303, Invalid=1503, Unknown=0, NotChecked=0, Total=1806 [2018-10-10 16:30:37,655 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2018-10-10 16:30:37,658 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 169. [2018-10-10 16:30:37,658 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 169 states. [2018-10-10 16:30:37,659 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 170 transitions. [2018-10-10 16:30:37,659 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 170 transitions. Word has length 152 [2018-10-10 16:30:37,659 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:37,660 INFO L481 AbstractCegarLoop]: Abstraction has 169 states and 170 transitions. [2018-10-10 16:30:37,660 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-10 16:30:37,660 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 170 transitions. [2018-10-10 16:30:37,662 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 169 [2018-10-10 16:30:37,662 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:37,662 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:37,662 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:37,662 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:37,663 INFO L82 PathProgramCache]: Analyzing trace with hash -806597509, now seen corresponding path program 8 times [2018-10-10 16:30:37,663 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:37,681 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:38,379 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 44 proven. 221 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:38,379 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:38,379 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-10 16:30:38,380 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-10 16:30:38,380 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-10 16:30:38,380 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=542, Unknown=0, NotChecked=0, Total=600 [2018-10-10 16:30:38,380 INFO L87 Difference]: Start difference. First operand 169 states and 170 transitions. Second operand 25 states. [2018-10-10 16:30:40,434 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:40,434 INFO L93 Difference]: Finished difference Result 203 states and 204 transitions. [2018-10-10 16:30:40,435 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-10-10 16:30:40,435 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 168 [2018-10-10 16:30:40,436 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:40,436 INFO L225 Difference]: With dead ends: 203 [2018-10-10 16:30:40,437 INFO L226 Difference]: Without dead ends: 203 [2018-10-10 16:30:40,438 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 523 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=349, Invalid=2513, Unknown=0, NotChecked=0, Total=2862 [2018-10-10 16:30:40,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2018-10-10 16:30:40,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 183. [2018-10-10 16:30:40,442 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 183 states. [2018-10-10 16:30:40,442 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 184 transitions. [2018-10-10 16:30:40,443 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 184 transitions. Word has length 168 [2018-10-10 16:30:40,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:40,443 INFO L481 AbstractCegarLoop]: Abstraction has 183 states and 184 transitions. [2018-10-10 16:30:40,443 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-10 16:30:40,443 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 184 transitions. [2018-10-10 16:30:40,445 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2018-10-10 16:30:40,445 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:40,445 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:40,446 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:40,446 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:40,446 INFO L82 PathProgramCache]: Analyzing trace with hash -760194101, now seen corresponding path program 9 times [2018-10-10 16:30:40,447 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:40,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:41,163 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 107 proven. 218 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:41,163 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:41,163 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-10 16:30:41,164 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-10 16:30:41,164 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-10 16:30:41,164 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=510, Unknown=0, NotChecked=0, Total=600 [2018-10-10 16:30:41,165 INFO L87 Difference]: Start difference. First operand 183 states and 184 transitions. Second operand 25 states. [2018-10-10 16:30:41,895 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:41,896 INFO L93 Difference]: Finished difference Result 285 states and 286 transitions. [2018-10-10 16:30:41,896 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-10 16:30:41,897 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 182 [2018-10-10 16:30:41,897 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:41,899 INFO L225 Difference]: With dead ends: 285 [2018-10-10 16:30:41,899 INFO L226 Difference]: Without dead ends: 213 [2018-10-10 16:30:41,900 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 599 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=432, Invalid=2220, Unknown=0, NotChecked=0, Total=2652 [2018-10-10 16:30:41,901 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-10-10 16:30:41,903 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-10-10 16:30:41,904 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-10-10 16:30:41,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 200 transitions. [2018-10-10 16:30:41,905 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 200 transitions. Word has length 182 [2018-10-10 16:30:41,905 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:41,905 INFO L481 AbstractCegarLoop]: Abstraction has 199 states and 200 transitions. [2018-10-10 16:30:41,905 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-10 16:30:41,905 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 200 transitions. [2018-10-10 16:30:41,907 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-10-10 16:30:41,907 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:41,908 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:41,908 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:41,908 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:41,908 INFO L82 PathProgramCache]: Analyzing trace with hash -1237558311, now seen corresponding path program 10 times [2018-10-10 16:30:41,909 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:41,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:42,481 INFO L134 CoverageAnalysis]: Checked inductivity of 406 backedges. 128 proven. 278 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:42,481 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:42,481 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-10 16:30:42,482 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-10 16:30:42,482 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-10 16:30:42,482 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=721, Unknown=0, NotChecked=0, Total=812 [2018-10-10 16:30:42,482 INFO L87 Difference]: Start difference. First operand 199 states and 200 transitions. Second operand 29 states. [2018-10-10 16:30:45,376 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:45,377 INFO L93 Difference]: Finished difference Result 233 states and 234 transitions. [2018-10-10 16:30:45,382 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-10-10 16:30:45,382 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 198 [2018-10-10 16:30:45,383 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:45,384 INFO L225 Difference]: With dead ends: 233 [2018-10-10 16:30:45,384 INFO L226 Difference]: Without dead ends: 233 [2018-10-10 16:30:45,385 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 914 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=742, Invalid=3418, Unknown=0, NotChecked=0, Total=4160 [2018-10-10 16:30:45,386 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2018-10-10 16:30:45,389 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 213. [2018-10-10 16:30:45,389 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-10-10 16:30:45,390 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 214 transitions. [2018-10-10 16:30:45,390 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 214 transitions. Word has length 198 [2018-10-10 16:30:45,390 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:45,390 INFO L481 AbstractCegarLoop]: Abstraction has 213 states and 214 transitions. [2018-10-10 16:30:45,390 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-10 16:30:45,391 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 214 transitions. [2018-10-10 16:30:45,392 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-10-10 16:30:45,392 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:45,392 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:45,392 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:45,392 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:45,393 INFO L82 PathProgramCache]: Analyzing trace with hash 1187720873, now seen corresponding path program 11 times [2018-10-10 16:30:45,393 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:45,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:46,366 INFO L134 CoverageAnalysis]: Checked inductivity of 480 backedges. 168 proven. 312 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:46,366 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:46,366 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-10 16:30:46,367 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-10 16:30:46,367 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-10 16:30:46,367 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=694, Unknown=0, NotChecked=0, Total=812 [2018-10-10 16:30:46,367 INFO L87 Difference]: Start difference. First operand 213 states and 214 transitions. Second operand 29 states. [2018-10-10 16:30:47,624 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:47,625 INFO L93 Difference]: Finished difference Result 329 states and 330 transitions. [2018-10-10 16:30:47,625 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-10-10 16:30:47,625 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 212 [2018-10-10 16:30:47,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:47,628 INFO L225 Difference]: With dead ends: 329 [2018-10-10 16:30:47,628 INFO L226 Difference]: Without dead ends: 243 [2018-10-10 16:30:47,629 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 861 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=585, Invalid=3075, Unknown=0, NotChecked=0, Total=3660 [2018-10-10 16:30:47,630 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 243 states. [2018-10-10 16:30:47,633 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 243 to 229. [2018-10-10 16:30:47,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 229 states. [2018-10-10 16:30:47,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 230 transitions. [2018-10-10 16:30:47,634 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 230 transitions. Word has length 212 [2018-10-10 16:30:47,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:47,634 INFO L481 AbstractCegarLoop]: Abstraction has 229 states and 230 transitions. [2018-10-10 16:30:47,634 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-10 16:30:47,634 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 230 transitions. [2018-10-10 16:30:47,635 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 229 [2018-10-10 16:30:47,636 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:47,636 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:47,636 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:47,636 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:47,636 INFO L82 PathProgramCache]: Analyzing trace with hash -1844305353, now seen corresponding path program 12 times [2018-10-10 16:30:47,637 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:47,655 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:49,009 INFO L134 CoverageAnalysis]: Checked inductivity of 577 backedges. 200 proven. 377 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:49,009 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:49,009 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-10 16:30:49,010 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-10 16:30:49,010 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-10 16:30:49,011 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=948, Unknown=0, NotChecked=0, Total=1056 [2018-10-10 16:30:49,011 INFO L87 Difference]: Start difference. First operand 229 states and 230 transitions. Second operand 33 states. [2018-10-10 16:30:51,519 WARN L178 SmtUtils]: Spent 465.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 41 [2018-10-10 16:30:52,679 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:52,680 INFO L93 Difference]: Finished difference Result 263 states and 264 transitions. [2018-10-10 16:30:52,680 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2018-10-10 16:30:52,680 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 228 [2018-10-10 16:30:52,681 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:52,682 INFO L225 Difference]: With dead ends: 263 [2018-10-10 16:30:52,682 INFO L226 Difference]: Without dead ends: 263 [2018-10-10 16:30:52,685 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1181 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=869, Invalid=4387, Unknown=0, NotChecked=0, Total=5256 [2018-10-10 16:30:52,685 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 263 states. [2018-10-10 16:30:52,688 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 263 to 243. [2018-10-10 16:30:52,688 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 243 states. [2018-10-10 16:30:52,689 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 244 transitions. [2018-10-10 16:30:52,689 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 244 transitions. Word has length 228 [2018-10-10 16:30:52,690 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:52,690 INFO L481 AbstractCegarLoop]: Abstraction has 243 states and 244 transitions. [2018-10-10 16:30:52,690 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-10 16:30:52,690 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 244 transitions. [2018-10-10 16:30:52,691 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 243 [2018-10-10 16:30:52,691 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:52,692 INFO L375 BasicCegarLoop]: trace histogram [8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:52,692 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:52,692 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:52,692 INFO L82 PathProgramCache]: Analyzing trace with hash -56657785, now seen corresponding path program 13 times [2018-10-10 16:30:52,693 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:52,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:53,191 INFO L134 CoverageAnalysis]: Checked inductivity of 665 backedges. 243 proven. 422 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:53,191 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:53,191 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-10 16:30:53,192 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-10 16:30:53,192 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-10 16:30:53,192 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=906, Unknown=0, NotChecked=0, Total=1056 [2018-10-10 16:30:53,193 INFO L87 Difference]: Start difference. First operand 243 states and 244 transitions. Second operand 33 states. [2018-10-10 16:30:54,376 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:30:54,376 INFO L93 Difference]: Finished difference Result 373 states and 374 transitions. [2018-10-10 16:30:54,377 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-10-10 16:30:54,377 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 242 [2018-10-10 16:30:54,378 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:30:54,379 INFO L225 Difference]: With dead ends: 373 [2018-10-10 16:30:54,379 INFO L226 Difference]: Without dead ends: 273 [2018-10-10 16:30:54,381 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1170 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=762, Invalid=4068, Unknown=0, NotChecked=0, Total=4830 [2018-10-10 16:30:54,382 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 273 states. [2018-10-10 16:30:54,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 273 to 259. [2018-10-10 16:30:54,385 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 259 states. [2018-10-10 16:30:54,386 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 259 states to 259 states and 260 transitions. [2018-10-10 16:30:54,386 INFO L78 Accepts]: Start accepts. Automaton has 259 states and 260 transitions. Word has length 242 [2018-10-10 16:30:54,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:30:54,387 INFO L481 AbstractCegarLoop]: Abstraction has 259 states and 260 transitions. [2018-10-10 16:30:54,387 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-10 16:30:54,387 INFO L276 IsEmpty]: Start isEmpty. Operand 259 states and 260 transitions. [2018-10-10 16:30:54,388 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 259 [2018-10-10 16:30:54,388 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:30:54,389 INFO L375 BasicCegarLoop]: trace histogram [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:30:54,389 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:30:54,389 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:30:54,389 INFO L82 PathProgramCache]: Analyzing trace with hash 1486503829, now seen corresponding path program 14 times [2018-10-10 16:30:54,390 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:30:54,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:30:55,218 INFO L134 CoverageAnalysis]: Checked inductivity of 778 backedges. 288 proven. 490 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:30:55,218 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:30:55,218 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-10 16:30:55,219 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-10 16:30:55,219 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-10 16:30:55,219 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=1205, Unknown=0, NotChecked=0, Total=1332 [2018-10-10 16:30:55,219 INFO L87 Difference]: Start difference. First operand 259 states and 260 transitions. Second operand 37 states. [2018-10-10 16:30:59,236 WARN L178 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 41 [2018-10-10 16:31:00,031 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:00,032 INFO L93 Difference]: Finished difference Result 293 states and 294 transitions. [2018-10-10 16:31:00,032 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-10-10 16:31:00,032 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 258 [2018-10-10 16:31:00,033 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:00,034 INFO L225 Difference]: With dead ends: 293 [2018-10-10 16:31:00,034 INFO L226 Difference]: Without dead ends: 293 [2018-10-10 16:31:00,037 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1523 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=1031, Invalid=5611, Unknown=0, NotChecked=0, Total=6642 [2018-10-10 16:31:00,038 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-10-10 16:31:00,041 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 273. [2018-10-10 16:31:00,041 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 273 states. [2018-10-10 16:31:00,042 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 273 states to 273 states and 274 transitions. [2018-10-10 16:31:00,043 INFO L78 Accepts]: Start accepts. Automaton has 273 states and 274 transitions. Word has length 258 [2018-10-10 16:31:00,043 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:00,043 INFO L481 AbstractCegarLoop]: Abstraction has 273 states and 274 transitions. [2018-10-10 16:31:00,043 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-10 16:31:00,043 INFO L276 IsEmpty]: Start isEmpty. Operand 273 states and 274 transitions. [2018-10-10 16:31:00,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2018-10-10 16:31:00,045 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:00,046 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:00,046 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:00,046 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:00,046 INFO L82 PathProgramCache]: Analyzing trace with hash -1899898523, now seen corresponding path program 15 times [2018-10-10 16:31:00,047 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:00,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:00,912 INFO L134 CoverageAnalysis]: Checked inductivity of 880 backedges. 332 proven. 548 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:00,912 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:00,912 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-10 16:31:00,913 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-10 16:31:00,913 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-10 16:31:00,913 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=186, Invalid=1146, Unknown=0, NotChecked=0, Total=1332 [2018-10-10 16:31:00,913 INFO L87 Difference]: Start difference. First operand 273 states and 274 transitions. Second operand 37 states. [2018-10-10 16:31:02,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:02,420 INFO L93 Difference]: Finished difference Result 417 states and 418 transitions. [2018-10-10 16:31:02,421 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-10 16:31:02,421 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 272 [2018-10-10 16:31:02,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:02,423 INFO L225 Difference]: With dead ends: 417 [2018-10-10 16:31:02,424 INFO L226 Difference]: Without dead ends: 303 [2018-10-10 16:31:02,426 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1526 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=963, Invalid=5199, Unknown=0, NotChecked=0, Total=6162 [2018-10-10 16:31:02,426 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2018-10-10 16:31:02,430 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 289. [2018-10-10 16:31:02,430 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 289 states. [2018-10-10 16:31:02,431 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 289 states to 289 states and 290 transitions. [2018-10-10 16:31:02,431 INFO L78 Accepts]: Start accepts. Automaton has 289 states and 290 transitions. Word has length 272 [2018-10-10 16:31:02,431 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:02,431 INFO L481 AbstractCegarLoop]: Abstraction has 289 states and 290 transitions. [2018-10-10 16:31:02,432 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-10 16:31:02,432 INFO L276 IsEmpty]: Start isEmpty. Operand 289 states and 290 transitions. [2018-10-10 16:31:02,433 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 289 [2018-10-10 16:31:02,433 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:02,433 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:02,434 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:02,434 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:02,434 INFO L82 PathProgramCache]: Analyzing trace with hash 1369527283, now seen corresponding path program 16 times [2018-10-10 16:31:02,435 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:02,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:03,391 INFO L134 CoverageAnalysis]: Checked inductivity of 1009 backedges. 392 proven. 617 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:03,391 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:03,392 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-10 16:31:03,392 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-10 16:31:03,392 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-10 16:31:03,393 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=1492, Unknown=0, NotChecked=0, Total=1640 [2018-10-10 16:31:03,393 INFO L87 Difference]: Start difference. First operand 289 states and 290 transitions. Second operand 41 states. [2018-10-10 16:31:07,967 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:07,968 INFO L93 Difference]: Finished difference Result 323 states and 324 transitions. [2018-10-10 16:31:07,968 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-10-10 16:31:07,968 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 288 [2018-10-10 16:31:07,969 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:07,970 INFO L225 Difference]: With dead ends: 323 [2018-10-10 16:31:07,970 INFO L226 Difference]: Without dead ends: 323 [2018-10-10 16:31:07,974 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1906 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=1208, Invalid=6982, Unknown=0, NotChecked=0, Total=8190 [2018-10-10 16:31:07,975 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 323 states. [2018-10-10 16:31:07,979 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 323 to 303. [2018-10-10 16:31:07,979 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 303 states. [2018-10-10 16:31:07,980 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 303 states to 303 states and 304 transitions. [2018-10-10 16:31:07,980 INFO L78 Accepts]: Start accepts. Automaton has 303 states and 304 transitions. Word has length 288 [2018-10-10 16:31:07,981 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:07,981 INFO L481 AbstractCegarLoop]: Abstraction has 303 states and 304 transitions. [2018-10-10 16:31:07,981 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-10 16:31:07,981 INFO L276 IsEmpty]: Start isEmpty. Operand 303 states and 304 transitions. [2018-10-10 16:31:07,983 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 303 [2018-10-10 16:31:07,984 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:07,984 INFO L375 BasicCegarLoop]: trace histogram [10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:07,984 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:07,985 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:07,985 INFO L82 PathProgramCache]: Analyzing trace with hash -765005501, now seen corresponding path program 17 times [2018-10-10 16:31:07,986 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:08,011 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:09,354 INFO L134 CoverageAnalysis]: Checked inductivity of 1125 backedges. 435 proven. 690 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:09,355 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:09,355 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-10 16:31:09,356 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-10 16:31:09,356 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-10 16:31:09,356 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=226, Invalid=1414, Unknown=0, NotChecked=0, Total=1640 [2018-10-10 16:31:09,356 INFO L87 Difference]: Start difference. First operand 303 states and 304 transitions. Second operand 41 states. [2018-10-10 16:31:10,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:10,582 INFO L93 Difference]: Finished difference Result 461 states and 462 transitions. [2018-10-10 16:31:10,582 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2018-10-10 16:31:10,582 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 302 [2018-10-10 16:31:10,583 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:10,585 INFO L225 Difference]: With dead ends: 461 [2018-10-10 16:31:10,585 INFO L226 Difference]: Without dead ends: 333 [2018-10-10 16:31:10,586 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1929 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=1188, Invalid=6468, Unknown=0, NotChecked=0, Total=7656 [2018-10-10 16:31:10,586 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 333 states. [2018-10-10 16:31:10,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 333 to 319. [2018-10-10 16:31:10,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 319 states. [2018-10-10 16:31:10,591 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 319 states to 319 states and 320 transitions. [2018-10-10 16:31:10,592 INFO L78 Accepts]: Start accepts. Automaton has 319 states and 320 transitions. Word has length 302 [2018-10-10 16:31:10,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:10,592 INFO L481 AbstractCegarLoop]: Abstraction has 319 states and 320 transitions. [2018-10-10 16:31:10,592 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-10 16:31:10,592 INFO L276 IsEmpty]: Start isEmpty. Operand 319 states and 320 transitions. [2018-10-10 16:31:10,594 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 319 [2018-10-10 16:31:10,594 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:10,594 INFO L375 BasicCegarLoop]: trace histogram [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:10,594 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:10,595 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:10,595 INFO L82 PathProgramCache]: Analyzing trace with hash 227802961, now seen corresponding path program 18 times [2018-10-10 16:31:10,596 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:10,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:12,628 INFO L134 CoverageAnalysis]: Checked inductivity of 1270 backedges. 512 proven. 758 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:12,629 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:12,629 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-10 16:31:12,630 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-10 16:31:12,630 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-10 16:31:12,630 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=219, Invalid=1761, Unknown=0, NotChecked=0, Total=1980 [2018-10-10 16:31:12,631 INFO L87 Difference]: Start difference. First operand 319 states and 320 transitions. Second operand 45 states. [2018-10-10 16:31:17,712 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:17,713 INFO L93 Difference]: Finished difference Result 353 states and 354 transitions. [2018-10-10 16:31:17,713 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-10-10 16:31:17,713 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 318 [2018-10-10 16:31:17,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:17,715 INFO L225 Difference]: With dead ends: 353 [2018-10-10 16:31:17,715 INFO L226 Difference]: Without dead ends: 353 [2018-10-10 16:31:17,718 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2716 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=1920, Invalid=9000, Unknown=0, NotChecked=0, Total=10920 [2018-10-10 16:31:17,718 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2018-10-10 16:31:17,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 333. [2018-10-10 16:31:17,722 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 333 states. [2018-10-10 16:31:17,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 334 transitions. [2018-10-10 16:31:17,723 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 334 transitions. Word has length 318 [2018-10-10 16:31:17,723 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:17,723 INFO L481 AbstractCegarLoop]: Abstraction has 333 states and 334 transitions. [2018-10-10 16:31:17,723 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-10 16:31:17,723 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 334 transitions. [2018-10-10 16:31:17,725 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 333 [2018-10-10 16:31:17,725 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:17,725 INFO L375 BasicCegarLoop]: trace histogram [11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:17,725 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:17,726 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:17,726 INFO L82 PathProgramCache]: Analyzing trace with hash 1298358305, now seen corresponding path program 19 times [2018-10-10 16:31:17,726 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:17,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:18,871 INFO L134 CoverageAnalysis]: Checked inductivity of 1400 backedges. 552 proven. 848 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:18,872 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:18,872 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-10 16:31:18,872 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-10 16:31:18,873 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-10 16:31:18,873 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=270, Invalid=1710, Unknown=0, NotChecked=0, Total=1980 [2018-10-10 16:31:18,873 INFO L87 Difference]: Start difference. First operand 333 states and 334 transitions. Second operand 45 states. [2018-10-10 16:31:20,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:20,925 INFO L93 Difference]: Finished difference Result 505 states and 506 transitions. [2018-10-10 16:31:20,925 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-10-10 16:31:20,926 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 332 [2018-10-10 16:31:20,926 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:20,928 INFO L225 Difference]: With dead ends: 505 [2018-10-10 16:31:20,928 INFO L226 Difference]: Without dead ends: 363 [2018-10-10 16:31:20,930 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2379 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=1437, Invalid=7875, Unknown=0, NotChecked=0, Total=9312 [2018-10-10 16:31:20,930 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 363 states. [2018-10-10 16:31:20,934 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 363 to 349. [2018-10-10 16:31:20,934 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 349 states. [2018-10-10 16:31:20,935 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 349 states to 349 states and 350 transitions. [2018-10-10 16:31:20,935 INFO L78 Accepts]: Start accepts. Automaton has 349 states and 350 transitions. Word has length 332 [2018-10-10 16:31:20,935 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:20,935 INFO L481 AbstractCegarLoop]: Abstraction has 349 states and 350 transitions. [2018-10-10 16:31:20,935 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-10 16:31:20,935 INFO L276 IsEmpty]: Start isEmpty. Operand 349 states and 350 transitions. [2018-10-10 16:31:20,937 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 349 [2018-10-10 16:31:20,937 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:20,938 INFO L375 BasicCegarLoop]: trace histogram [11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:20,938 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:20,938 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:20,938 INFO L82 PathProgramCache]: Analyzing trace with hash 1535041967, now seen corresponding path program 20 times [2018-10-10 16:31:20,939 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:20,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:23,198 INFO L134 CoverageAnalysis]: Checked inductivity of 1561 backedges. 648 proven. 913 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:23,199 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:23,199 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-10 16:31:23,199 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-10 16:31:23,200 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-10 16:31:23,200 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=244, Invalid=2108, Unknown=0, NotChecked=0, Total=2352 [2018-10-10 16:31:23,200 INFO L87 Difference]: Start difference. First operand 349 states and 350 transitions. Second operand 49 states. [2018-10-10 16:31:29,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:29,298 INFO L93 Difference]: Finished difference Result 383 states and 384 transitions. [2018-10-10 16:31:29,298 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-10 16:31:29,298 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 348 [2018-10-10 16:31:29,299 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:29,300 INFO L225 Difference]: With dead ends: 383 [2018-10-10 16:31:29,300 INFO L226 Difference]: Without dead ends: 383 [2018-10-10 16:31:29,302 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3155 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=2127, Invalid=10529, Unknown=0, NotChecked=0, Total=12656 [2018-10-10 16:31:29,302 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 383 states. [2018-10-10 16:31:29,306 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 383 to 363. [2018-10-10 16:31:29,306 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 363 states. [2018-10-10 16:31:29,307 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 364 transitions. [2018-10-10 16:31:29,307 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 364 transitions. Word has length 348 [2018-10-10 16:31:29,307 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:29,307 INFO L481 AbstractCegarLoop]: Abstraction has 363 states and 364 transitions. [2018-10-10 16:31:29,308 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-10 16:31:29,308 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 364 transitions. [2018-10-10 16:31:29,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 363 [2018-10-10 16:31:29,310 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:29,310 INFO L375 BasicCegarLoop]: trace histogram [12, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:29,310 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:29,311 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:29,311 INFO L82 PathProgramCache]: Analyzing trace with hash -1406417409, now seen corresponding path program 21 times [2018-10-10 16:31:29,312 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:29,336 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:30,803 INFO L134 CoverageAnalysis]: Checked inductivity of 1705 backedges. 683 proven. 1022 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:30,803 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:30,803 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-10 16:31:30,804 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-10 16:31:30,804 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-10 16:31:30,804 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=318, Invalid=2034, Unknown=0, NotChecked=0, Total=2352 [2018-10-10 16:31:30,804 INFO L87 Difference]: Start difference. First operand 363 states and 364 transitions. Second operand 49 states. [2018-10-10 16:31:33,334 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:33,335 INFO L93 Difference]: Finished difference Result 549 states and 550 transitions. [2018-10-10 16:31:33,335 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 71 states. [2018-10-10 16:31:33,335 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 362 [2018-10-10 16:31:33,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:33,337 INFO L225 Difference]: With dead ends: 549 [2018-10-10 16:31:33,337 INFO L226 Difference]: Without dead ends: 393 [2018-10-10 16:31:33,338 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2876 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=1710, Invalid=9420, Unknown=0, NotChecked=0, Total=11130 [2018-10-10 16:31:33,339 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 393 states. [2018-10-10 16:31:33,343 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 393 to 379. [2018-10-10 16:31:33,343 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-10-10 16:31:33,344 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 380 transitions. [2018-10-10 16:31:33,344 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 380 transitions. Word has length 362 [2018-10-10 16:31:33,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:33,344 INFO L481 AbstractCegarLoop]: Abstraction has 379 states and 380 transitions. [2018-10-10 16:31:33,345 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-10 16:31:33,345 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 380 transitions. [2018-10-10 16:31:33,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 379 [2018-10-10 16:31:33,347 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:33,347 INFO L375 BasicCegarLoop]: trace histogram [12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:33,347 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:33,347 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:33,348 INFO L82 PathProgramCache]: Analyzing trace with hash 1057921805, now seen corresponding path program 22 times [2018-10-10 16:31:33,348 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:33,374 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:34,860 INFO L134 CoverageAnalysis]: Checked inductivity of 1882 backedges. 800 proven. 1082 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:34,860 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:34,860 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-10 16:31:34,861 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-10 16:31:34,861 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-10 16:31:34,861 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=271, Invalid=2485, Unknown=0, NotChecked=0, Total=2756 [2018-10-10 16:31:34,862 INFO L87 Difference]: Start difference. First operand 379 states and 380 transitions. Second operand 53 states. [2018-10-10 16:31:41,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:41,454 INFO L93 Difference]: Finished difference Result 413 states and 414 transitions. [2018-10-10 16:31:41,454 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-10 16:31:41,454 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 378 [2018-10-10 16:31:41,455 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:41,456 INFO L225 Difference]: With dead ends: 413 [2018-10-10 16:31:41,457 INFO L226 Difference]: Without dead ends: 413 [2018-10-10 16:31:41,458 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3697 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=2377, Invalid=12385, Unknown=0, NotChecked=0, Total=14762 [2018-10-10 16:31:41,459 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 413 states. [2018-10-10 16:31:41,463 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 413 to 393. [2018-10-10 16:31:41,463 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 393 states. [2018-10-10 16:31:41,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 393 states to 393 states and 394 transitions. [2018-10-10 16:31:41,464 INFO L78 Accepts]: Start accepts. Automaton has 393 states and 394 transitions. Word has length 378 [2018-10-10 16:31:41,464 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:41,465 INFO L481 AbstractCegarLoop]: Abstraction has 393 states and 394 transitions. [2018-10-10 16:31:41,465 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-10 16:31:41,465 INFO L276 IsEmpty]: Start isEmpty. Operand 393 states and 394 transitions. [2018-10-10 16:31:41,467 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 393 [2018-10-10 16:31:41,467 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:41,468 INFO L375 BasicCegarLoop]: trace histogram [13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:41,468 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:41,468 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:41,468 INFO L82 PathProgramCache]: Analyzing trace with hash 936690397, now seen corresponding path program 23 times [2018-10-10 16:31:41,469 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:41,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:42,799 INFO L134 CoverageAnalysis]: Checked inductivity of 2040 backedges. 828 proven. 1212 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:42,800 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:42,800 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-10 16:31:42,801 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-10 16:31:42,801 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-10 16:31:42,801 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=370, Invalid=2386, Unknown=0, NotChecked=0, Total=2756 [2018-10-10 16:31:42,802 INFO L87 Difference]: Start difference. First operand 393 states and 394 transitions. Second operand 53 states. [2018-10-10 16:31:45,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:45,439 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-10 16:31:45,439 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-10 16:31:45,439 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 392 [2018-10-10 16:31:45,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:45,442 INFO L225 Difference]: With dead ends: 593 [2018-10-10 16:31:45,442 INFO L226 Difference]: Without dead ends: 423 [2018-10-10 16:31:45,443 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3420 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=2007, Invalid=11103, Unknown=0, NotChecked=0, Total=13110 [2018-10-10 16:31:45,443 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 423 states. [2018-10-10 16:31:45,446 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 423 to 409. [2018-10-10 16:31:45,447 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 409 states. [2018-10-10 16:31:45,447 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 409 states to 409 states and 410 transitions. [2018-10-10 16:31:45,448 INFO L78 Accepts]: Start accepts. Automaton has 409 states and 410 transitions. Word has length 392 [2018-10-10 16:31:45,448 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:45,448 INFO L481 AbstractCegarLoop]: Abstraction has 409 states and 410 transitions. [2018-10-10 16:31:45,448 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-10 16:31:45,448 INFO L276 IsEmpty]: Start isEmpty. Operand 409 states and 410 transitions. [2018-10-10 16:31:45,450 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 409 [2018-10-10 16:31:45,450 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:45,451 INFO L375 BasicCegarLoop]: trace histogram [13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:45,451 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:45,451 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:45,451 INFO L82 PathProgramCache]: Analyzing trace with hash -426783893, now seen corresponding path program 24 times [2018-10-10 16:31:45,452 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:45,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:48,248 INFO L134 CoverageAnalysis]: Checked inductivity of 2233 backedges. 860 proven. 1373 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:48,248 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:48,249 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-10 16:31:48,249 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-10 16:31:48,249 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-10 16:31:48,250 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=234, Invalid=2958, Unknown=0, NotChecked=0, Total=3192 [2018-10-10 16:31:48,250 INFO L87 Difference]: Start difference. First operand 409 states and 410 transitions. Second operand 57 states. [2018-10-10 16:31:56,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:31:56,202 INFO L93 Difference]: Finished difference Result 443 states and 444 transitions. [2018-10-10 16:31:56,202 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-10-10 16:31:56,202 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 408 [2018-10-10 16:31:56,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:31:56,204 INFO L225 Difference]: With dead ends: 443 [2018-10-10 16:31:56,204 INFO L226 Difference]: Without dead ends: 443 [2018-10-10 16:31:56,205 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3543 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=1645, Invalid=14105, Unknown=0, NotChecked=0, Total=15750 [2018-10-10 16:31:56,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 443 states. [2018-10-10 16:31:56,209 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 443 to 423. [2018-10-10 16:31:56,209 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 423 states. [2018-10-10 16:31:56,210 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 423 states to 423 states and 424 transitions. [2018-10-10 16:31:56,210 INFO L78 Accepts]: Start accepts. Automaton has 423 states and 424 transitions. Word has length 408 [2018-10-10 16:31:56,211 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:31:56,211 INFO L481 AbstractCegarLoop]: Abstraction has 423 states and 424 transitions. [2018-10-10 16:31:56,211 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-10 16:31:56,211 INFO L276 IsEmpty]: Start isEmpty. Operand 423 states and 424 transitions. [2018-10-10 16:31:56,213 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 423 [2018-10-10 16:31:56,213 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:31:56,214 INFO L375 BasicCegarLoop]: trace histogram [14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:31:56,214 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:31:56,214 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:31:56,214 INFO L82 PathProgramCache]: Analyzing trace with hash 1276311227, now seen corresponding path program 25 times [2018-10-10 16:31:56,215 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:31:56,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:31:57,484 INFO L134 CoverageAnalysis]: Checked inductivity of 2405 backedges. 987 proven. 1418 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:31:57,485 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:31:57,485 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-10 16:31:57,485 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-10 16:31:57,486 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-10 16:31:57,486 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=426, Invalid=2766, Unknown=0, NotChecked=0, Total=3192 [2018-10-10 16:31:57,487 INFO L87 Difference]: Start difference. First operand 423 states and 424 transitions. Second operand 57 states. [2018-10-10 16:32:00,469 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:32:00,469 INFO L93 Difference]: Finished difference Result 637 states and 638 transitions. [2018-10-10 16:32:00,469 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-10 16:32:00,469 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 422 [2018-10-10 16:32:00,470 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:32:00,472 INFO L225 Difference]: With dead ends: 637 [2018-10-10 16:32:00,472 INFO L226 Difference]: Without dead ends: 453 [2018-10-10 16:32:00,473 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4011 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=2328, Invalid=12924, Unknown=0, NotChecked=0, Total=15252 [2018-10-10 16:32:00,474 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 453 states. [2018-10-10 16:32:00,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 453 to 439. [2018-10-10 16:32:00,478 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 439 states. [2018-10-10 16:32:00,479 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 439 states to 439 states and 440 transitions. [2018-10-10 16:32:00,479 INFO L78 Accepts]: Start accepts. Automaton has 439 states and 440 transitions. Word has length 422 [2018-10-10 16:32:00,479 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:32:00,480 INFO L481 AbstractCegarLoop]: Abstraction has 439 states and 440 transitions. [2018-10-10 16:32:00,480 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-10 16:32:00,480 INFO L276 IsEmpty]: Start isEmpty. Operand 439 states and 440 transitions. [2018-10-10 16:32:00,482 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 439 [2018-10-10 16:32:00,482 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:32:00,483 INFO L375 BasicCegarLoop]: trace histogram [14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:32:00,483 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:32:00,483 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:32:00,483 INFO L82 PathProgramCache]: Analyzing trace with hash -1594944823, now seen corresponding path program 26 times [2018-10-10 16:32:00,484 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:32:00,513 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:32:02,232 INFO L134 CoverageAnalysis]: Checked inductivity of 2614 backedges. 1152 proven. 1462 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:32:02,232 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:32:02,232 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-10 16:32:02,233 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-10 16:32:02,233 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-10 16:32:02,233 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=411, Invalid=3249, Unknown=0, NotChecked=0, Total=3660 [2018-10-10 16:32:02,234 INFO L87 Difference]: Start difference. First operand 439 states and 440 transitions. Second operand 61 states. [2018-10-10 16:32:10,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:32:10,421 INFO L93 Difference]: Finished difference Result 473 states and 474 transitions. [2018-10-10 16:32:10,421 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-10-10 16:32:10,421 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 438 [2018-10-10 16:32:10,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:32:10,423 INFO L225 Difference]: With dead ends: 473 [2018-10-10 16:32:10,423 INFO L226 Difference]: Without dead ends: 473 [2018-10-10 16:32:10,425 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5462 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=3658, Invalid=17222, Unknown=0, NotChecked=0, Total=20880 [2018-10-10 16:32:10,425 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 473 states. [2018-10-10 16:32:10,429 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 473 to 453. [2018-10-10 16:32:10,430 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 453 states. [2018-10-10 16:32:10,430 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 453 states to 453 states and 454 transitions. [2018-10-10 16:32:10,431 INFO L78 Accepts]: Start accepts. Automaton has 453 states and 454 transitions. Word has length 438 [2018-10-10 16:32:10,431 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:32:10,431 INFO L481 AbstractCegarLoop]: Abstraction has 453 states and 454 transitions. [2018-10-10 16:32:10,431 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-10 16:32:10,431 INFO L276 IsEmpty]: Start isEmpty. Operand 453 states and 454 transitions. [2018-10-10 16:32:10,434 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 453 [2018-10-10 16:32:10,434 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:32:10,435 INFO L375 BasicCegarLoop]: trace histogram [15, 15, 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:32:10,435 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:32:10,435 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:32:10,435 INFO L82 PathProgramCache]: Analyzing trace with hash -851770983, now seen corresponding path program 27 times [2018-10-10 16:32:10,436 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:32:10,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:32:11,945 INFO L134 CoverageAnalysis]: Checked inductivity of 2800 backedges. 1160 proven. 1640 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:32:11,946 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:32:11,946 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-10 16:32:11,947 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-10 16:32:11,947 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-10 16:32:11,947 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=486, Invalid=3174, Unknown=0, NotChecked=0, Total=3660 [2018-10-10 16:32:11,947 INFO L87 Difference]: Start difference. First operand 453 states and 454 transitions. Second operand 61 states. [2018-10-10 16:32:15,220 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:32:15,220 INFO L93 Difference]: Finished difference Result 681 states and 682 transitions. [2018-10-10 16:32:15,221 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-10-10 16:32:15,221 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 452 [2018-10-10 16:32:15,221 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:32:15,223 INFO L225 Difference]: With dead ends: 681 [2018-10-10 16:32:15,223 INFO L226 Difference]: Without dead ends: 483 [2018-10-10 16:32:15,225 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 131 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4649 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=2673, Invalid=14883, Unknown=0, NotChecked=0, Total=17556 [2018-10-10 16:32:15,225 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 483 states. [2018-10-10 16:32:15,229 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 483 to 469. [2018-10-10 16:32:15,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 469 states. [2018-10-10 16:32:15,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 469 states to 469 states and 470 transitions. [2018-10-10 16:32:15,230 INFO L78 Accepts]: Start accepts. Automaton has 469 states and 470 transitions. Word has length 452 [2018-10-10 16:32:15,230 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:32:15,230 INFO L481 AbstractCegarLoop]: Abstraction has 469 states and 470 transitions. [2018-10-10 16:32:15,230 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-10 16:32:15,230 INFO L276 IsEmpty]: Start isEmpty. Operand 469 states and 470 transitions. [2018-10-10 16:32:15,233 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 469 [2018-10-10 16:32:15,233 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:32:15,233 INFO L375 BasicCegarLoop]: trace histogram [15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:32:15,234 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:32:15,234 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:32:15,234 INFO L82 PathProgramCache]: Analyzing trace with hash -742846169, now seen corresponding path program 28 times [2018-10-10 16:32:15,235 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:32:15,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:32:17,170 INFO L134 CoverageAnalysis]: Checked inductivity of 3025 backedges. 1352 proven. 1673 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:32:17,170 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:32:17,171 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-10 16:32:17,171 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-10 16:32:17,171 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-10 16:32:17,172 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=444, Invalid=3716, Unknown=0, NotChecked=0, Total=4160 [2018-10-10 16:32:17,172 INFO L87 Difference]: Start difference. First operand 469 states and 470 transitions. Second operand 65 states. [2018-10-10 16:32:26,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:32:26,669 INFO L93 Difference]: Finished difference Result 503 states and 504 transitions. [2018-10-10 16:32:26,669 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 105 states. [2018-10-10 16:32:26,669 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 468 [2018-10-10 16:32:26,669 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:32:26,671 INFO L225 Difference]: With dead ends: 503 [2018-10-10 16:32:26,671 INFO L226 Difference]: Without dead ends: 503 [2018-10-10 16:32:26,673 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 151 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6073 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=3945, Invalid=19311, Unknown=0, NotChecked=0, Total=23256 [2018-10-10 16:32:26,673 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 503 states. [2018-10-10 16:32:26,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 503 to 483. [2018-10-10 16:32:26,676 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 483 states. [2018-10-10 16:32:26,677 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 483 states to 483 states and 484 transitions. [2018-10-10 16:32:26,677 INFO L78 Accepts]: Start accepts. Automaton has 483 states and 484 transitions. Word has length 468 [2018-10-10 16:32:26,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:32:26,678 INFO L481 AbstractCegarLoop]: Abstraction has 483 states and 484 transitions. [2018-10-10 16:32:26,678 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-10 16:32:26,678 INFO L276 IsEmpty]: Start isEmpty. Operand 483 states and 484 transitions. [2018-10-10 16:32:26,681 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 483 [2018-10-10 16:32:26,681 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:32:26,681 INFO L375 BasicCegarLoop]: trace histogram [16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:32:26,682 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:32:26,682 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:32:26,682 INFO L82 PathProgramCache]: Analyzing trace with hash -1639873673, now seen corresponding path program 29 times [2018-10-10 16:32:26,682 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:32:26,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:32:28,182 INFO L134 CoverageAnalysis]: Checked inductivity of 3225 backedges. 1347 proven. 1878 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:32:28,183 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:32:28,183 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-10 16:32:28,183 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-10 16:32:28,184 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-10 16:32:28,184 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=550, Invalid=3610, Unknown=0, NotChecked=0, Total=4160 [2018-10-10 16:32:28,184 INFO L87 Difference]: Start difference. First operand 483 states and 484 transitions. Second operand 65 states. [2018-10-10 16:32:31,986 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:32:31,986 INFO L93 Difference]: Finished difference Result 725 states and 726 transitions. [2018-10-10 16:32:31,986 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 95 states. [2018-10-10 16:32:31,986 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 482 [2018-10-10 16:32:31,987 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:32:31,989 INFO L225 Difference]: With dead ends: 725 [2018-10-10 16:32:31,989 INFO L226 Difference]: Without dead ends: 513 [2018-10-10 16:32:31,990 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5334 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=3042, Invalid=16980, Unknown=0, NotChecked=0, Total=20022 [2018-10-10 16:32:31,991 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 513 states. [2018-10-10 16:32:31,994 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 513 to 499. [2018-10-10 16:32:31,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 499 states. [2018-10-10 16:32:31,995 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 499 states to 499 states and 500 transitions. [2018-10-10 16:32:31,995 INFO L78 Accepts]: Start accepts. Automaton has 499 states and 500 transitions. Word has length 482 [2018-10-10 16:32:31,995 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:32:31,996 INFO L481 AbstractCegarLoop]: Abstraction has 499 states and 500 transitions. [2018-10-10 16:32:31,996 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-10 16:32:31,996 INFO L276 IsEmpty]: Start isEmpty. Operand 499 states and 500 transitions. [2018-10-10 16:32:31,998 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 499 [2018-10-10 16:32:31,999 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:32:31,999 INFO L375 BasicCegarLoop]: trace histogram [16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:32:31,999 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:32:31,999 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:32:31,999 INFO L82 PathProgramCache]: Analyzing trace with hash -249928059, now seen corresponding path program 30 times [2018-10-10 16:32:32,000 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:32:32,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:32:34,405 INFO L134 CoverageAnalysis]: Checked inductivity of 3466 backedges. 1568 proven. 1898 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:32:34,406 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:32:34,406 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-10 16:32:34,406 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-10 16:32:34,407 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-10 16:32:34,407 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=4213, Unknown=0, NotChecked=0, Total=4692 [2018-10-10 16:32:34,407 INFO L87 Difference]: Start difference. First operand 499 states and 500 transitions. Second operand 69 states. [2018-10-10 16:32:45,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:32:45,142 INFO L93 Difference]: Finished difference Result 533 states and 534 transitions. [2018-10-10 16:32:45,142 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 111 states. [2018-10-10 16:32:45,142 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 498 [2018-10-10 16:32:45,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:32:45,144 INFO L225 Difference]: With dead ends: 533 [2018-10-10 16:32:45,144 INFO L226 Difference]: Without dead ends: 533 [2018-10-10 16:32:45,146 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 160 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6815 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=4283, Invalid=21799, Unknown=0, NotChecked=0, Total=26082 [2018-10-10 16:32:45,147 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 533 states. [2018-10-10 16:32:45,150 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 533 to 513. [2018-10-10 16:32:45,150 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 513 states. [2018-10-10 16:32:45,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 513 states to 513 states and 514 transitions. [2018-10-10 16:32:45,151 INFO L78 Accepts]: Start accepts. Automaton has 513 states and 514 transitions. Word has length 498 [2018-10-10 16:32:45,152 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:32:45,152 INFO L481 AbstractCegarLoop]: Abstraction has 513 states and 514 transitions. [2018-10-10 16:32:45,152 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-10 16:32:45,152 INFO L276 IsEmpty]: Start isEmpty. Operand 513 states and 514 transitions. [2018-10-10 16:32:45,155 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 513 [2018-10-10 16:32:45,156 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:32:45,156 INFO L375 BasicCegarLoop]: trace histogram [17, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:32:45,156 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:32:45,156 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:32:45,157 INFO L82 PathProgramCache]: Analyzing trace with hash 381361237, now seen corresponding path program 31 times [2018-10-10 16:32:45,157 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:32:45,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:32:46,970 INFO L134 CoverageAnalysis]: Checked inductivity of 3680 backedges. 1548 proven. 2132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:32:46,970 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:32:46,970 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-10 16:32:46,971 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-10 16:32:46,971 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-10 16:32:46,971 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=618, Invalid=4074, Unknown=0, NotChecked=0, Total=4692 [2018-10-10 16:32:46,971 INFO L87 Difference]: Start difference. First operand 513 states and 514 transitions. Second operand 69 states. [2018-10-10 16:32:51,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:32:51,274 INFO L93 Difference]: Finished difference Result 769 states and 770 transitions. [2018-10-10 16:32:51,274 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 101 states. [2018-10-10 16:32:51,275 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 512 [2018-10-10 16:32:51,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:32:51,278 INFO L225 Difference]: With dead ends: 769 [2018-10-10 16:32:51,278 INFO L226 Difference]: Without dead ends: 543 [2018-10-10 16:32:51,279 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 149 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6066 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=3435, Invalid=19215, Unknown=0, NotChecked=0, Total=22650 [2018-10-10 16:32:51,280 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 543 states. [2018-10-10 16:32:51,283 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 543 to 529. [2018-10-10 16:32:51,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 529 states. [2018-10-10 16:32:51,284 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 529 states to 529 states and 530 transitions. [2018-10-10 16:32:51,284 INFO L78 Accepts]: Start accepts. Automaton has 529 states and 530 transitions. Word has length 512 [2018-10-10 16:32:51,285 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:32:51,285 INFO L481 AbstractCegarLoop]: Abstraction has 529 states and 530 transitions. [2018-10-10 16:32:51,285 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-10 16:32:51,285 INFO L276 IsEmpty]: Start isEmpty. Operand 529 states and 530 transitions. [2018-10-10 16:32:51,288 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 529 [2018-10-10 16:32:51,288 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:32:51,289 INFO L375 BasicCegarLoop]: trace histogram [17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:32:51,289 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:32:51,289 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:32:51,289 INFO L82 PathProgramCache]: Analyzing trace with hash 1843376867, now seen corresponding path program 32 times [2018-10-10 16:32:51,290 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:32:51,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:32:53,627 INFO L134 CoverageAnalysis]: Checked inductivity of 3937 backedges. 1800 proven. 2137 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:32:53,627 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:32:53,627 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-10 16:32:53,628 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-10 16:32:53,628 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-10 16:32:53,628 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=516, Invalid=4740, Unknown=0, NotChecked=0, Total=5256 [2018-10-10 16:32:53,628 INFO L87 Difference]: Start difference. First operand 529 states and 530 transitions. Second operand 73 states. [2018-10-10 16:33:05,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:33:05,834 INFO L93 Difference]: Finished difference Result 563 states and 564 transitions. [2018-10-10 16:33:05,834 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-10-10 16:33:05,834 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 528 [2018-10-10 16:33:05,835 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:33:05,836 INFO L225 Difference]: With dead ends: 563 [2018-10-10 16:33:05,836 INFO L226 Difference]: Without dead ends: 563 [2018-10-10 16:33:05,837 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 169 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7598 ImplicationChecksByTransitivity, 8.7s TimeCoverageRelationStatistics Valid=4636, Invalid=24434, Unknown=0, NotChecked=0, Total=29070 [2018-10-10 16:33:05,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 563 states. [2018-10-10 16:33:05,840 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 563 to 543. [2018-10-10 16:33:05,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 543 states. [2018-10-10 16:33:05,841 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 543 states to 543 states and 544 transitions. [2018-10-10 16:33:05,841 INFO L78 Accepts]: Start accepts. Automaton has 543 states and 544 transitions. Word has length 528 [2018-10-10 16:33:05,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:33:05,842 INFO L481 AbstractCegarLoop]: Abstraction has 543 states and 544 transitions. [2018-10-10 16:33:05,842 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-10 16:33:05,842 INFO L276 IsEmpty]: Start isEmpty. Operand 543 states and 544 transitions. [2018-10-10 16:33:05,845 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 543 [2018-10-10 16:33:05,845 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:33:05,845 INFO L375 BasicCegarLoop]: trace histogram [18, 18, 18, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:33:05,845 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:33:05,846 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:33:05,846 INFO L82 PathProgramCache]: Analyzing trace with hash 2027711539, now seen corresponding path program 33 times [2018-10-10 16:33:05,846 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:33:05,879 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:33:09,175 INFO L134 CoverageAnalysis]: Checked inductivity of 4165 backedges. 1763 proven. 2402 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:33:09,175 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:33:09,176 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-10 16:33:09,176 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-10 16:33:09,177 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-10 16:33:09,177 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=690, Invalid=4566, Unknown=0, NotChecked=0, Total=5256 [2018-10-10 16:33:09,177 INFO L87 Difference]: Start difference. First operand 543 states and 544 transitions. Second operand 73 states. [2018-10-10 16:33:13,816 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:33:13,816 INFO L93 Difference]: Finished difference Result 813 states and 814 transitions. [2018-10-10 16:33:13,816 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 107 states. [2018-10-10 16:33:13,817 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 542 [2018-10-10 16:33:13,817 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:33:13,819 INFO L225 Difference]: With dead ends: 813 [2018-10-10 16:33:13,819 INFO L226 Difference]: Without dead ends: 573 [2018-10-10 16:33:13,821 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 158 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6845 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=3852, Invalid=21588, Unknown=0, NotChecked=0, Total=25440 [2018-10-10 16:33:13,821 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 573 states. [2018-10-10 16:33:13,825 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 573 to 559. [2018-10-10 16:33:13,825 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 559 states. [2018-10-10 16:33:13,826 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 559 states to 559 states and 560 transitions. [2018-10-10 16:33:13,826 INFO L78 Accepts]: Start accepts. Automaton has 559 states and 560 transitions. Word has length 542 [2018-10-10 16:33:13,827 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:33:13,827 INFO L481 AbstractCegarLoop]: Abstraction has 559 states and 560 transitions. [2018-10-10 16:33:13,827 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-10 16:33:13,827 INFO L276 IsEmpty]: Start isEmpty. Operand 559 states and 560 transitions. [2018-10-10 16:33:13,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 559 [2018-10-10 16:33:13,831 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:33:13,831 INFO L375 BasicCegarLoop]: trace histogram [18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:33:13,831 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:33:13,831 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:33:13,831 INFO L82 PathProgramCache]: Analyzing trace with hash -1217030591, now seen corresponding path program 34 times [2018-10-10 16:33:13,832 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:33:13,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:33:16,889 INFO L134 CoverageAnalysis]: Checked inductivity of 4438 backedges. 2048 proven. 2390 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:33:16,889 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:33:16,889 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-10 16:33:16,890 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-10 16:33:16,890 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-10 16:33:16,891 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=667, Invalid=5185, Unknown=0, NotChecked=0, Total=5852 [2018-10-10 16:33:16,891 INFO L87 Difference]: Start difference. First operand 559 states and 560 transitions. Second operand 77 states. [2018-10-10 16:33:29,077 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:33:29,078 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-10 16:33:29,078 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-10-10 16:33:29,078 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 558 [2018-10-10 16:33:29,079 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:33:29,080 INFO L225 Difference]: With dead ends: 593 [2018-10-10 16:33:29,080 INFO L226 Difference]: Without dead ends: 593 [2018-10-10 16:33:29,082 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 183 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9152 ImplicationChecksByTransitivity, 9.6s TimeCoverageRelationStatistics Valid=5956, Invalid=28084, Unknown=0, NotChecked=0, Total=34040 [2018-10-10 16:33:29,082 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 593 states. [2018-10-10 16:33:29,085 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 593 to 573. [2018-10-10 16:33:29,085 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 573 states. [2018-10-10 16:33:29,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 573 states to 573 states and 574 transitions. [2018-10-10 16:33:29,086 INFO L78 Accepts]: Start accepts. Automaton has 573 states and 574 transitions. Word has length 558 [2018-10-10 16:33:29,086 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:33:29,086 INFO L481 AbstractCegarLoop]: Abstraction has 573 states and 574 transitions. [2018-10-10 16:33:29,087 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-10 16:33:29,087 INFO L276 IsEmpty]: Start isEmpty. Operand 573 states and 574 transitions. [2018-10-10 16:33:29,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 573 [2018-10-10 16:33:29,090 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:33:29,091 INFO L375 BasicCegarLoop]: trace histogram [19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:33:29,091 INFO L424 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:33:29,091 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:33:29,092 INFO L82 PathProgramCache]: Analyzing trace with hash 1736053521, now seen corresponding path program 35 times [2018-10-10 16:33:29,092 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:33:29,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:33:31,724 INFO L134 CoverageAnalysis]: Checked inductivity of 4680 backedges. 1992 proven. 2688 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:33:31,725 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:33:31,725 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-10 16:33:31,726 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-10 16:33:31,726 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-10 16:33:31,726 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=766, Invalid=5086, Unknown=0, NotChecked=0, Total=5852 [2018-10-10 16:33:31,727 INFO L87 Difference]: Start difference. First operand 573 states and 574 transitions. Second operand 77 states. [2018-10-10 16:33:37,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:33:37,019 INFO L93 Difference]: Finished difference Result 857 states and 858 transitions. [2018-10-10 16:33:37,019 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 113 states. [2018-10-10 16:33:37,019 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 572 [2018-10-10 16:33:37,020 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:33:37,022 INFO L225 Difference]: With dead ends: 857 [2018-10-10 16:33:37,022 INFO L226 Difference]: Without dead ends: 603 [2018-10-10 16:33:37,024 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 167 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7671 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=4293, Invalid=24099, Unknown=0, NotChecked=0, Total=28392 [2018-10-10 16:33:37,024 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 603 states. [2018-10-10 16:33:37,028 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 603 to 589. [2018-10-10 16:33:37,028 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 589 states. [2018-10-10 16:33:37,029 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 589 states to 589 states and 590 transitions. [2018-10-10 16:33:37,029 INFO L78 Accepts]: Start accepts. Automaton has 589 states and 590 transitions. Word has length 572 [2018-10-10 16:33:37,029 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:33:37,029 INFO L481 AbstractCegarLoop]: Abstraction has 589 states and 590 transitions. [2018-10-10 16:33:37,029 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-10 16:33:37,029 INFO L276 IsEmpty]: Start isEmpty. Operand 589 states and 590 transitions. [2018-10-10 16:33:37,033 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 589 [2018-10-10 16:33:37,033 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:33:37,033 INFO L375 BasicCegarLoop]: trace histogram [19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:33:37,033 INFO L424 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:33:37,034 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:33:37,034 INFO L82 PathProgramCache]: Analyzing trace with hash 703115423, now seen corresponding path program 36 times [2018-10-10 16:33:37,035 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:33:37,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:33:40,236 INFO L134 CoverageAnalysis]: Checked inductivity of 4969 backedges. 2312 proven. 2657 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:33:40,237 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:33:40,237 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-10 16:33:40,237 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-10 16:33:40,238 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-10 16:33:40,238 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=708, Invalid=5772, Unknown=0, NotChecked=0, Total=6480 [2018-10-10 16:33:40,238 INFO L87 Difference]: Start difference. First operand 589 states and 590 transitions. Second operand 81 states. [2018-10-10 16:33:53,441 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:33:53,441 INFO L93 Difference]: Finished difference Result 623 states and 624 transitions. [2018-10-10 16:33:53,441 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 133 states. [2018-10-10 16:33:53,442 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 588 [2018-10-10 16:33:53,442 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:33:53,444 INFO L225 Difference]: With dead ends: 623 [2018-10-10 16:33:53,444 INFO L226 Difference]: Without dead ends: 623 [2018-10-10 16:33:53,445 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 191 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9935 ImplicationChecksByTransitivity, 10.5s TimeCoverageRelationStatistics Valid=6323, Invalid=30733, Unknown=0, NotChecked=0, Total=37056 [2018-10-10 16:33:53,445 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 623 states. [2018-10-10 16:33:53,448 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 623 to 603. [2018-10-10 16:33:53,448 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 603 states. [2018-10-10 16:33:53,449 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 603 states to 603 states and 604 transitions. [2018-10-10 16:33:53,449 INFO L78 Accepts]: Start accepts. Automaton has 603 states and 604 transitions. Word has length 588 [2018-10-10 16:33:53,450 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:33:53,450 INFO L481 AbstractCegarLoop]: Abstraction has 603 states and 604 transitions. [2018-10-10 16:33:53,450 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-10 16:33:53,450 INFO L276 IsEmpty]: Start isEmpty. Operand 603 states and 604 transitions. [2018-10-10 16:33:53,453 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 603 [2018-10-10 16:33:53,453 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:33:53,454 INFO L375 BasicCegarLoop]: trace histogram [20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:33:53,454 INFO L424 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:33:53,454 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:33:53,454 INFO L82 PathProgramCache]: Analyzing trace with hash 1544073455, now seen corresponding path program 37 times [2018-10-10 16:33:53,455 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:33:53,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:33:56,043 INFO L134 CoverageAnalysis]: Checked inductivity of 5225 backedges. 2235 proven. 2990 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:33:56,043 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:33:56,043 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-10 16:33:56,044 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-10 16:33:56,044 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-10 16:33:56,044 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=846, Invalid=5634, Unknown=0, NotChecked=0, Total=6480 [2018-10-10 16:33:56,044 INFO L87 Difference]: Start difference. First operand 603 states and 604 transitions. Second operand 81 states. [2018-10-10 16:34:01,764 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:34:01,765 INFO L93 Difference]: Finished difference Result 901 states and 902 transitions. [2018-10-10 16:34:01,765 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 119 states. [2018-10-10 16:34:01,765 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 602 [2018-10-10 16:34:01,766 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:34:01,768 INFO L225 Difference]: With dead ends: 901 [2018-10-10 16:34:01,768 INFO L226 Difference]: Without dead ends: 633 [2018-10-10 16:34:01,770 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 176 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8544 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=4758, Invalid=26748, Unknown=0, NotChecked=0, Total=31506 [2018-10-10 16:34:01,770 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 633 states. [2018-10-10 16:34:01,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 633 to 619. [2018-10-10 16:34:01,773 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 619 states. [2018-10-10 16:34:01,774 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 619 states to 619 states and 620 transitions. [2018-10-10 16:34:01,774 INFO L78 Accepts]: Start accepts. Automaton has 619 states and 620 transitions. Word has length 602 [2018-10-10 16:34:01,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:34:01,775 INFO L481 AbstractCegarLoop]: Abstraction has 619 states and 620 transitions. [2018-10-10 16:34:01,775 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-10 16:34:01,775 INFO L276 IsEmpty]: Start isEmpty. Operand 619 states and 620 transitions. [2018-10-10 16:34:01,779 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 619 [2018-10-10 16:34:01,779 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:34:01,779 INFO L375 BasicCegarLoop]: trace histogram [20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:34:01,779 INFO L424 AbstractCegarLoop]: === Iteration 41 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:34:01,780 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:34:01,780 INFO L82 PathProgramCache]: Analyzing trace with hash 98935293, now seen corresponding path program 38 times [2018-10-10 16:34:01,780 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:34:01,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:34:04,927 INFO L134 CoverageAnalysis]: Checked inductivity of 5530 backedges. 2592 proven. 2938 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:34:04,928 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:34:04,928 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-10 16:34:04,928 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-10 16:34:04,929 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-10 16:34:04,929 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=751, Invalid=6389, Unknown=0, NotChecked=0, Total=7140 [2018-10-10 16:34:04,929 INFO L87 Difference]: Start difference. First operand 619 states and 620 transitions. Second operand 85 states. [2018-10-10 16:34:19,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:34:19,696 INFO L93 Difference]: Finished difference Result 653 states and 654 transitions. [2018-10-10 16:34:19,696 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 139 states. [2018-10-10 16:34:19,696 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 618 [2018-10-10 16:34:19,697 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:34:19,698 INFO L225 Difference]: With dead ends: 653 [2018-10-10 16:34:19,698 INFO L226 Difference]: Without dead ends: 653 [2018-10-10 16:34:19,700 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 206 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 200 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10877 ImplicationChecksByTransitivity, 11.3s TimeCoverageRelationStatistics Valid=6749, Invalid=33853, Unknown=0, NotChecked=0, Total=40602 [2018-10-10 16:34:19,701 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 653 states. [2018-10-10 16:34:19,705 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 653 to 633. [2018-10-10 16:34:19,705 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 633 states. [2018-10-10 16:34:19,706 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 633 states to 633 states and 634 transitions. [2018-10-10 16:34:19,706 INFO L78 Accepts]: Start accepts. Automaton has 633 states and 634 transitions. Word has length 618 [2018-10-10 16:34:19,706 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:34:19,706 INFO L481 AbstractCegarLoop]: Abstraction has 633 states and 634 transitions. [2018-10-10 16:34:19,706 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-10 16:34:19,706 INFO L276 IsEmpty]: Start isEmpty. Operand 633 states and 634 transitions. [2018-10-10 16:34:19,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 633 [2018-10-10 16:34:19,709 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:34:19,710 INFO L375 BasicCegarLoop]: trace histogram [21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:34:19,710 INFO L424 AbstractCegarLoop]: === Iteration 42 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:34:19,710 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:34:19,710 INFO L82 PathProgramCache]: Analyzing trace with hash 480044493, now seen corresponding path program 39 times [2018-10-10 16:34:19,711 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:34:19,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:34:22,618 INFO L134 CoverageAnalysis]: Checked inductivity of 5800 backedges. 2492 proven. 3308 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:34:22,618 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:34:22,618 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-10 16:34:22,619 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-10 16:34:22,619 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-10 16:34:22,619 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=930, Invalid=6210, Unknown=0, NotChecked=0, Total=7140 [2018-10-10 16:34:22,619 INFO L87 Difference]: Start difference. First operand 633 states and 634 transitions. Second operand 85 states. [2018-10-10 16:34:28,739 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:34:28,739 INFO L93 Difference]: Finished difference Result 945 states and 946 transitions. [2018-10-10 16:34:28,739 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 125 states. [2018-10-10 16:34:28,740 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 632 [2018-10-10 16:34:28,741 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:34:28,742 INFO L225 Difference]: With dead ends: 945 [2018-10-10 16:34:28,743 INFO L226 Difference]: Without dead ends: 663 [2018-10-10 16:34:28,744 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9464 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=5247, Invalid=29535, Unknown=0, NotChecked=0, Total=34782 [2018-10-10 16:34:28,744 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 663 states. [2018-10-10 16:34:28,748 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 663 to 649. [2018-10-10 16:34:28,748 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 649 states. [2018-10-10 16:34:28,748 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 649 states to 649 states and 650 transitions. [2018-10-10 16:34:28,749 INFO L78 Accepts]: Start accepts. Automaton has 649 states and 650 transitions. Word has length 632 [2018-10-10 16:34:28,749 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:34:28,749 INFO L481 AbstractCegarLoop]: Abstraction has 649 states and 650 transitions. [2018-10-10 16:34:28,749 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-10 16:34:28,749 INFO L276 IsEmpty]: Start isEmpty. Operand 649 states and 650 transitions. [2018-10-10 16:34:28,752 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 649 [2018-10-10 16:34:28,752 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:34:28,752 INFO L375 BasicCegarLoop]: trace histogram [21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:34:28,752 INFO L424 AbstractCegarLoop]: === Iteration 43 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:34:28,753 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:34:28,753 INFO L82 PathProgramCache]: Analyzing trace with hash 1723402843, now seen corresponding path program 40 times [2018-10-10 16:34:28,753 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:34:28,793 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:34:32,398 INFO L134 CoverageAnalysis]: Checked inductivity of 6121 backedges. 2888 proven. 3233 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:34:32,399 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:34:32,399 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-10 16:34:32,400 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-10 16:34:32,400 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-10 16:34:32,400 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=684, Invalid=7148, Unknown=0, NotChecked=0, Total=7832 [2018-10-10 16:34:32,401 INFO L87 Difference]: Start difference. First operand 649 states and 650 transitions. Second operand 89 states. [2018-10-10 16:34:44,583 WARN L178 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-10 16:34:44,773 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-10 16:34:45,248 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-10 16:34:45,428 WARN L178 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-10 16:34:45,845 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-10 16:34:46,032 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-10 16:34:46,484 WARN L178 SmtUtils]: Spent 128.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-10 16:34:46,718 WARN L178 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 43 [2018-10-10 16:34:47,171 WARN L178 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 42 [2018-10-10 16:34:50,549 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:34:50,549 INFO L93 Difference]: Finished difference Result 683 states and 684 transitions. [2018-10-10 16:34:50,550 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 141 states. [2018-10-10 16:34:50,550 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 648 [2018-10-10 16:34:50,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:34:50,552 INFO L225 Difference]: With dead ends: 683 [2018-10-10 16:34:50,552 INFO L226 Difference]: Without dead ends: 683 [2018-10-10 16:34:50,554 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 205 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11140 ImplicationChecksByTransitivity, 12.9s TimeCoverageRelationStatistics Valid=6198, Invalid=36444, Unknown=0, NotChecked=0, Total=42642 [2018-10-10 16:34:50,554 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 683 states. [2018-10-10 16:34:50,558 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 683 to 663. [2018-10-10 16:34:50,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 663 states. [2018-10-10 16:34:50,559 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 663 states to 663 states and 664 transitions. [2018-10-10 16:34:50,560 INFO L78 Accepts]: Start accepts. Automaton has 663 states and 664 transitions. Word has length 648 [2018-10-10 16:34:50,560 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:34:50,560 INFO L481 AbstractCegarLoop]: Abstraction has 663 states and 664 transitions. [2018-10-10 16:34:50,560 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-10 16:34:50,561 INFO L276 IsEmpty]: Start isEmpty. Operand 663 states and 664 transitions. [2018-10-10 16:34:50,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 663 [2018-10-10 16:34:50,564 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:34:50,564 INFO L375 BasicCegarLoop]: trace histogram [22, 22, 22, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:34:50,564 INFO L424 AbstractCegarLoop]: === Iteration 44 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:34:50,564 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:34:50,564 INFO L82 PathProgramCache]: Analyzing trace with hash 837505451, now seen corresponding path program 41 times [2018-10-10 16:34:50,565 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:34:50,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:34:53,871 INFO L134 CoverageAnalysis]: Checked inductivity of 6405 backedges. 2763 proven. 3642 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:34:53,871 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:34:53,872 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-10 16:34:53,872 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-10 16:34:53,873 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-10 16:34:53,873 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1018, Invalid=6814, Unknown=0, NotChecked=0, Total=7832 [2018-10-10 16:34:53,873 INFO L87 Difference]: Start difference. First operand 663 states and 664 transitions. Second operand 89 states. [2018-10-10 16:35:00,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:35:00,337 INFO L93 Difference]: Finished difference Result 989 states and 990 transitions. [2018-10-10 16:35:00,337 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-10-10 16:35:00,337 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 662 [2018-10-10 16:35:00,338 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:35:00,341 INFO L225 Difference]: With dead ends: 989 [2018-10-10 16:35:00,341 INFO L226 Difference]: Without dead ends: 693 [2018-10-10 16:35:00,343 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 194 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10431 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=5760, Invalid=32460, Unknown=0, NotChecked=0, Total=38220 [2018-10-10 16:35:00,343 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 693 states. [2018-10-10 16:35:00,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 693 to 679. [2018-10-10 16:35:00,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 679 states. [2018-10-10 16:35:00,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 679 states to 679 states and 680 transitions. [2018-10-10 16:35:00,348 INFO L78 Accepts]: Start accepts. Automaton has 679 states and 680 transitions. Word has length 662 [2018-10-10 16:35:00,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:35:00,348 INFO L481 AbstractCegarLoop]: Abstraction has 679 states and 680 transitions. [2018-10-10 16:35:00,348 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-10 16:35:00,349 INFO L276 IsEmpty]: Start isEmpty. Operand 679 states and 680 transitions. [2018-10-10 16:35:00,352 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 679 [2018-10-10 16:35:00,352 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:35:00,352 INFO L375 BasicCegarLoop]: trace histogram [22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:35:00,352 INFO L424 AbstractCegarLoop]: === Iteration 45 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:35:00,352 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:35:00,352 INFO L82 PathProgramCache]: Analyzing trace with hash 944736697, now seen corresponding path program 42 times [2018-10-10 16:35:00,353 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:35:00,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:35:04,588 INFO L134 CoverageAnalysis]: Checked inductivity of 6742 backedges. 3200 proven. 3542 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:35:04,588 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:35:04,589 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-10 16:35:04,589 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-10 16:35:04,590 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-10 16:35:04,590 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=987, Invalid=7569, Unknown=0, NotChecked=0, Total=8556 [2018-10-10 16:35:04,590 INFO L87 Difference]: Start difference. First operand 679 states and 680 transitions. Second operand 93 states. [2018-10-10 16:35:17,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:35:17,106 INFO L93 Difference]: Finished difference Result 713 states and 714 transitions. [2018-10-10 16:35:17,107 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 156 states. [2018-10-10 16:35:17,107 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 678 [2018-10-10 16:35:17,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:35:17,109 INFO L225 Difference]: With dead ends: 713 [2018-10-10 16:35:17,109 INFO L226 Difference]: Without dead ends: 713 [2018-10-10 16:35:17,111 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 223 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13786 ImplicationChecksByTransitivity, 13.2s TimeCoverageRelationStatistics Valid=8814, Invalid=41586, Unknown=0, NotChecked=0, Total=50400 [2018-10-10 16:35:17,111 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 713 states. [2018-10-10 16:35:17,115 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 713 to 693. [2018-10-10 16:35:17,115 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 693 states. [2018-10-10 16:35:17,116 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 693 states to 693 states and 694 transitions. [2018-10-10 16:35:17,116 INFO L78 Accepts]: Start accepts. Automaton has 693 states and 694 transitions. Word has length 678 [2018-10-10 16:35:17,116 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:35:17,116 INFO L481 AbstractCegarLoop]: Abstraction has 693 states and 694 transitions. [2018-10-10 16:35:17,116 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-10 16:35:17,116 INFO L276 IsEmpty]: Start isEmpty. Operand 693 states and 694 transitions. [2018-10-10 16:35:17,119 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 693 [2018-10-10 16:35:17,119 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:35:17,120 INFO L375 BasicCegarLoop]: trace histogram [23, 23, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:35:17,120 INFO L424 AbstractCegarLoop]: === Iteration 46 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:35:17,120 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:35:17,120 INFO L82 PathProgramCache]: Analyzing trace with hash 1565037705, now seen corresponding path program 43 times [2018-10-10 16:35:17,121 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:35:17,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:35:20,736 INFO L134 CoverageAnalysis]: Checked inductivity of 7040 backedges. 3048 proven. 3992 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:35:20,737 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:35:20,737 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-10 16:35:20,738 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-10 16:35:20,738 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-10 16:35:20,738 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1110, Invalid=7446, Unknown=0, NotChecked=0, Total=8556 [2018-10-10 16:35:20,738 INFO L87 Difference]: Start difference. First operand 693 states and 694 transitions. Second operand 93 states. [2018-10-10 16:35:28,206 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:35:28,206 INFO L93 Difference]: Finished difference Result 1033 states and 1034 transitions. [2018-10-10 16:35:28,207 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 137 states. [2018-10-10 16:35:28,207 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 692 [2018-10-10 16:35:28,208 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:35:28,210 INFO L225 Difference]: With dead ends: 1033 [2018-10-10 16:35:28,210 INFO L226 Difference]: Without dead ends: 723 [2018-10-10 16:35:28,212 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11445 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=6297, Invalid=35523, Unknown=0, NotChecked=0, Total=41820 [2018-10-10 16:35:28,212 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 723 states. [2018-10-10 16:35:28,216 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 723 to 709. [2018-10-10 16:35:28,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-10-10 16:35:28,217 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 710 transitions. [2018-10-10 16:35:28,217 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 710 transitions. Word has length 692 [2018-10-10 16:35:28,217 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:35:28,217 INFO L481 AbstractCegarLoop]: Abstraction has 709 states and 710 transitions. [2018-10-10 16:35:28,217 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-10 16:35:28,218 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 710 transitions. [2018-10-10 16:35:28,221 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 709 [2018-10-10 16:35:28,221 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:35:28,221 INFO L375 BasicCegarLoop]: trace histogram [23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:35:28,221 INFO L424 AbstractCegarLoop]: === Iteration 47 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:35:28,221 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:35:28,222 INFO L82 PathProgramCache]: Analyzing trace with hash 758497303, now seen corresponding path program 44 times [2018-10-10 16:35:28,222 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:35:28,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:35:32,391 INFO L134 CoverageAnalysis]: Checked inductivity of 7393 backedges. 3528 proven. 3865 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:35:32,391 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:35:32,391 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-10 16:35:32,392 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-10 16:35:32,392 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-10 16:35:32,392 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1036, Invalid=8276, Unknown=0, NotChecked=0, Total=9312 [2018-10-10 16:35:32,392 INFO L87 Difference]: Start difference. First operand 709 states and 710 transitions. Second operand 97 states. [2018-10-10 16:35:51,250 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:35:51,250 INFO L93 Difference]: Finished difference Result 743 states and 744 transitions. [2018-10-10 16:35:51,250 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-10 16:35:51,250 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 708 [2018-10-10 16:35:51,251 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:35:51,253 INFO L225 Difference]: With dead ends: 743 [2018-10-10 16:35:51,253 INFO L226 Difference]: Without dead ends: 743 [2018-10-10 16:35:51,254 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 231 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14741 ImplicationChecksByTransitivity, 14.3s TimeCoverageRelationStatistics Valid=9261, Invalid=44795, Unknown=0, NotChecked=0, Total=54056 [2018-10-10 16:35:51,255 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 743 states. [2018-10-10 16:35:51,259 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 743 to 723. [2018-10-10 16:35:51,259 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 723 states. [2018-10-10 16:35:51,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 723 states to 723 states and 724 transitions. [2018-10-10 16:35:51,260 INFO L78 Accepts]: Start accepts. Automaton has 723 states and 724 transitions. Word has length 708 [2018-10-10 16:35:51,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:35:51,261 INFO L481 AbstractCegarLoop]: Abstraction has 723 states and 724 transitions. [2018-10-10 16:35:51,261 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-10 16:35:51,261 INFO L276 IsEmpty]: Start isEmpty. Operand 723 states and 724 transitions. [2018-10-10 16:35:51,264 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 723 [2018-10-10 16:35:51,264 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:35:51,265 INFO L375 BasicCegarLoop]: trace histogram [24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:35:51,265 INFO L424 AbstractCegarLoop]: === Iteration 48 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:35:51,265 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:35:51,265 INFO L82 PathProgramCache]: Analyzing trace with hash 245976679, now seen corresponding path program 45 times [2018-10-10 16:35:51,266 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:35:51,305 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:35:54,737 INFO L134 CoverageAnalysis]: Checked inductivity of 7705 backedges. 3347 proven. 4358 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:35:54,738 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:35:54,738 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-10 16:35:54,739 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-10 16:35:54,739 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-10 16:35:54,739 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1206, Invalid=8106, Unknown=0, NotChecked=0, Total=9312 [2018-10-10 16:35:54,739 INFO L87 Difference]: Start difference. First operand 723 states and 724 transitions. Second operand 97 states. [2018-10-10 16:36:02,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:36:02,782 INFO L93 Difference]: Finished difference Result 1077 states and 1078 transitions. [2018-10-10 16:36:02,782 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 143 states. [2018-10-10 16:36:02,782 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 722 [2018-10-10 16:36:02,783 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:36:02,786 INFO L225 Difference]: With dead ends: 1077 [2018-10-10 16:36:02,786 INFO L226 Difference]: Without dead ends: 753 [2018-10-10 16:36:02,788 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 214 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 212 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12506 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=6858, Invalid=38724, Unknown=0, NotChecked=0, Total=45582 [2018-10-10 16:36:02,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 753 states. [2018-10-10 16:36:02,793 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 753 to 739. [2018-10-10 16:36:02,793 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-10-10 16:36:02,794 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 740 transitions. [2018-10-10 16:36:02,795 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 740 transitions. Word has length 722 [2018-10-10 16:36:02,795 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:36:02,795 INFO L481 AbstractCegarLoop]: Abstraction has 739 states and 740 transitions. [2018-10-10 16:36:02,795 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-10 16:36:02,795 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 740 transitions. [2018-10-10 16:36:02,799 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 739 [2018-10-10 16:36:02,799 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:36:02,799 INFO L375 BasicCegarLoop]: trace histogram [24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:36:02,799 INFO L424 AbstractCegarLoop]: === Iteration 49 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:36:02,799 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:36:02,800 INFO L82 PathProgramCache]: Analyzing trace with hash -1265087115, now seen corresponding path program 46 times [2018-10-10 16:36:02,800 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:36:02,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:36:07,241 INFO L134 CoverageAnalysis]: Checked inductivity of 8074 backedges. 3872 proven. 4202 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:36:07,242 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:36:07,242 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-10 16:36:07,243 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-10 16:36:07,243 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-10 16:36:07,243 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1087, Invalid=9013, Unknown=0, NotChecked=0, Total=10100 [2018-10-10 16:36:07,243 INFO L87 Difference]: Start difference. First operand 739 states and 740 transitions. Second operand 101 states. [2018-10-10 16:36:23,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:36:23,046 INFO L93 Difference]: Finished difference Result 773 states and 774 transitions. [2018-10-10 16:36:23,046 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-10 16:36:23,046 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 738 [2018-10-10 16:36:23,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:36:23,049 INFO L225 Difference]: With dead ends: 773 [2018-10-10 16:36:23,049 INFO L226 Difference]: Without dead ends: 773 [2018-10-10 16:36:23,050 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 240 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15883 ImplicationChecksByTransitivity, 15.6s TimeCoverageRelationStatistics Valid=9775, Invalid=48547, Unknown=0, NotChecked=0, Total=58322 [2018-10-10 16:36:23,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 773 states. [2018-10-10 16:36:23,054 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 773 to 753. [2018-10-10 16:36:23,054 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 753 states. [2018-10-10 16:36:23,055 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 753 states to 753 states and 754 transitions. [2018-10-10 16:36:23,055 INFO L78 Accepts]: Start accepts. Automaton has 753 states and 754 transitions. Word has length 738 [2018-10-10 16:36:23,056 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:36:23,056 INFO L481 AbstractCegarLoop]: Abstraction has 753 states and 754 transitions. [2018-10-10 16:36:23,056 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-10 16:36:23,056 INFO L276 IsEmpty]: Start isEmpty. Operand 753 states and 754 transitions. [2018-10-10 16:36:23,060 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 753 [2018-10-10 16:36:23,060 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:36:23,060 INFO L375 BasicCegarLoop]: trace histogram [25, 25, 25, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:36:23,060 INFO L424 AbstractCegarLoop]: === Iteration 50 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:36:23,061 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:36:23,061 INFO L82 PathProgramCache]: Analyzing trace with hash -626909371, now seen corresponding path program 47 times [2018-10-10 16:36:23,061 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:36:23,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:36:26,592 INFO L134 CoverageAnalysis]: Checked inductivity of 8400 backedges. 3660 proven. 4740 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:36:26,592 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:36:26,592 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-10 16:36:26,593 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-10 16:36:26,593 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-10 16:36:26,593 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1306, Invalid=8794, Unknown=0, NotChecked=0, Total=10100 [2018-10-10 16:36:26,594 INFO L87 Difference]: Start difference. First operand 753 states and 754 transitions. Second operand 101 states. [2018-10-10 16:36:35,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:36:35,530 INFO L93 Difference]: Finished difference Result 1121 states and 1122 transitions. [2018-10-10 16:36:35,530 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 149 states. [2018-10-10 16:36:35,530 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 752 [2018-10-10 16:36:35,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:36:35,534 INFO L225 Difference]: With dead ends: 1121 [2018-10-10 16:36:35,534 INFO L226 Difference]: Without dead ends: 783 [2018-10-10 16:36:35,537 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 221 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13614 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=7443, Invalid=42063, Unknown=0, NotChecked=0, Total=49506 [2018-10-10 16:36:35,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 783 states. [2018-10-10 16:36:35,543 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 783 to 769. [2018-10-10 16:36:35,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 769 states. [2018-10-10 16:36:35,544 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 769 states to 769 states and 770 transitions. [2018-10-10 16:36:35,544 INFO L78 Accepts]: Start accepts. Automaton has 769 states and 770 transitions. Word has length 752 [2018-10-10 16:36:35,545 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:36:35,545 INFO L481 AbstractCegarLoop]: Abstraction has 769 states and 770 transitions. [2018-10-10 16:36:35,545 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-10 16:36:35,545 INFO L276 IsEmpty]: Start isEmpty. Operand 769 states and 770 transitions. [2018-10-10 16:36:35,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 769 [2018-10-10 16:36:35,551 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:36:35,551 INFO L375 BasicCegarLoop]: trace histogram [25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:36:35,551 INFO L424 AbstractCegarLoop]: === Iteration 51 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:36:35,551 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:36:35,552 INFO L82 PathProgramCache]: Analyzing trace with hash -263990829, now seen corresponding path program 48 times [2018-10-10 16:36:35,552 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:36:35,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:36:39,871 INFO L134 CoverageAnalysis]: Checked inductivity of 8785 backedges. 4232 proven. 4553 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:36:39,871 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:36:39,871 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-10 16:36:39,872 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-10 16:36:39,872 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-10 16:36:39,873 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1140, Invalid=9780, Unknown=0, NotChecked=0, Total=10920 [2018-10-10 16:36:39,873 INFO L87 Difference]: Start difference. First operand 769 states and 770 transitions. Second operand 105 states. [2018-10-10 16:36:54,508 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 42 [2018-10-10 16:37:02,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:37:02,561 INFO L93 Difference]: Finished difference Result 803 states and 804 transitions. [2018-10-10 16:37:02,561 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 173 states. [2018-10-10 16:37:02,561 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 768 [2018-10-10 16:37:02,562 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:37:02,565 INFO L225 Difference]: With dead ends: 803 [2018-10-10 16:37:02,565 INFO L226 Difference]: Without dead ends: 803 [2018-10-10 16:37:02,567 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 255 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 249 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17066 ImplicationChecksByTransitivity, 16.9s TimeCoverageRelationStatistics Valid=10304, Invalid=52446, Unknown=0, NotChecked=0, Total=62750 [2018-10-10 16:37:02,568 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 803 states. [2018-10-10 16:37:02,572 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 803 to 783. [2018-10-10 16:37:02,572 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 783 states. [2018-10-10 16:37:02,573 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 783 states to 783 states and 784 transitions. [2018-10-10 16:37:02,573 INFO L78 Accepts]: Start accepts. Automaton has 783 states and 784 transitions. Word has length 768 [2018-10-10 16:37:02,574 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:37:02,574 INFO L481 AbstractCegarLoop]: Abstraction has 783 states and 784 transitions. [2018-10-10 16:37:02,574 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-10 16:37:02,574 INFO L276 IsEmpty]: Start isEmpty. Operand 783 states and 784 transitions. [2018-10-10 16:37:02,616 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 783 [2018-10-10 16:37:02,616 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:37:02,616 INFO L375 BasicCegarLoop]: trace histogram [26, 26, 26, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:37:02,617 INFO L424 AbstractCegarLoop]: === Iteration 52 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:37:02,617 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:37:02,617 INFO L82 PathProgramCache]: Analyzing trace with hash -261642461, now seen corresponding path program 49 times [2018-10-10 16:37:02,618 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:37:02,671 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:37:06,280 INFO L134 CoverageAnalysis]: Checked inductivity of 9125 backedges. 3987 proven. 5138 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:37:06,281 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:37:06,281 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-10 16:37:06,281 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-10 16:37:06,282 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-10 16:37:06,282 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1410, Invalid=9510, Unknown=0, NotChecked=0, Total=10920 [2018-10-10 16:37:06,283 INFO L87 Difference]: Start difference. First operand 783 states and 784 transitions. Second operand 105 states. [2018-10-10 16:37:15,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:37:15,718 INFO L93 Difference]: Finished difference Result 1165 states and 1166 transitions. [2018-10-10 16:37:15,719 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 155 states. [2018-10-10 16:37:15,719 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 782 [2018-10-10 16:37:15,720 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:37:15,722 INFO L225 Difference]: With dead ends: 1165 [2018-10-10 16:37:15,722 INFO L226 Difference]: Without dead ends: 813 [2018-10-10 16:37:15,724 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 232 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 230 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14769 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=8052, Invalid=45540, Unknown=0, NotChecked=0, Total=53592 [2018-10-10 16:37:15,724 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 813 states. [2018-10-10 16:37:15,729 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 813 to 799. [2018-10-10 16:37:15,729 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 799 states. [2018-10-10 16:37:15,729 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 799 states to 799 states and 800 transitions. [2018-10-10 16:37:15,730 INFO L78 Accepts]: Start accepts. Automaton has 799 states and 800 transitions. Word has length 782 [2018-10-10 16:37:15,730 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:37:15,730 INFO L481 AbstractCegarLoop]: Abstraction has 799 states and 800 transitions. [2018-10-10 16:37:15,730 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-10 16:37:15,730 INFO L276 IsEmpty]: Start isEmpty. Operand 799 states and 800 transitions. [2018-10-10 16:37:15,734 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 799 [2018-10-10 16:37:15,734 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:37:15,735 INFO L375 BasicCegarLoop]: trace histogram [26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:37:15,735 INFO L424 AbstractCegarLoop]: === Iteration 53 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:37:15,735 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:37:15,735 INFO L82 PathProgramCache]: Analyzing trace with hash -1432031951, now seen corresponding path program 50 times [2018-10-10 16:37:15,736 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:37:15,789 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:37:20,283 INFO L134 CoverageAnalysis]: Checked inductivity of 9526 backedges. 4608 proven. 4918 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:37:20,283 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:37:20,283 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-10 16:37:20,284 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-10 16:37:20,284 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-10 16:37:20,285 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1371, Invalid=10401, Unknown=0, NotChecked=0, Total=11772 [2018-10-10 16:37:20,285 INFO L87 Difference]: Start difference. First operand 799 states and 800 transitions. Second operand 109 states. [2018-10-10 16:37:38,774 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:37:38,774 INFO L93 Difference]: Finished difference Result 833 states and 834 transitions. [2018-10-10 16:37:38,774 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 184 states. [2018-10-10 16:37:38,774 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 798 [2018-10-10 16:37:38,775 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:37:38,777 INFO L225 Difference]: With dead ends: 833 [2018-10-10 16:37:38,777 INFO L226 Difference]: Without dead ends: 833 [2018-10-10 16:37:38,779 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 269 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 263 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19364 ImplicationChecksByTransitivity, 16.7s TimeCoverageRelationStatistics Valid=12232, Invalid=57728, Unknown=0, NotChecked=0, Total=69960 [2018-10-10 16:37:38,780 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 833 states. [2018-10-10 16:37:38,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 833 to 813. [2018-10-10 16:37:38,784 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 813 states. [2018-10-10 16:37:38,785 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 813 states to 813 states and 814 transitions. [2018-10-10 16:37:38,785 INFO L78 Accepts]: Start accepts. Automaton has 813 states and 814 transitions. Word has length 798 [2018-10-10 16:37:38,785 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:37:38,785 INFO L481 AbstractCegarLoop]: Abstraction has 813 states and 814 transitions. [2018-10-10 16:37:38,786 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-10 16:37:38,786 INFO L276 IsEmpty]: Start isEmpty. Operand 813 states and 814 transitions. [2018-10-10 16:37:38,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 813 [2018-10-10 16:37:38,790 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:37:38,790 INFO L375 BasicCegarLoop]: trace histogram [27, 27, 27, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:37:38,791 INFO L424 AbstractCegarLoop]: === Iteration 54 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:37:38,791 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:37:38,791 INFO L82 PathProgramCache]: Analyzing trace with hash -1882290687, now seen corresponding path program 51 times [2018-10-10 16:37:38,791 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:37:38,832 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:37:42,799 INFO L134 CoverageAnalysis]: Checked inductivity of 9880 backedges. 4328 proven. 5552 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:37:42,799 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:37:42,800 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-10 16:37:42,800 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-10 16:37:42,800 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-10 16:37:42,801 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1518, Invalid=10254, Unknown=0, NotChecked=0, Total=11772 [2018-10-10 16:37:42,801 INFO L87 Difference]: Start difference. First operand 813 states and 814 transitions. Second operand 109 states. [2018-10-10 16:37:53,166 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:37:53,167 INFO L93 Difference]: Finished difference Result 1209 states and 1210 transitions. [2018-10-10 16:37:53,167 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-10 16:37:53,167 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 812 [2018-10-10 16:37:53,168 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:37:53,170 INFO L225 Difference]: With dead ends: 1209 [2018-10-10 16:37:53,170 INFO L226 Difference]: Without dead ends: 843 [2018-10-10 16:37:53,172 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 239 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15971 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=8685, Invalid=49155, Unknown=0, NotChecked=0, Total=57840 [2018-10-10 16:37:53,173 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 843 states. [2018-10-10 16:37:53,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 843 to 829. [2018-10-10 16:37:53,177 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 829 states. [2018-10-10 16:37:53,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 829 states to 829 states and 830 transitions. [2018-10-10 16:37:53,178 INFO L78 Accepts]: Start accepts. Automaton has 829 states and 830 transitions. Word has length 812 [2018-10-10 16:37:53,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:37:53,178 INFO L481 AbstractCegarLoop]: Abstraction has 829 states and 830 transitions. [2018-10-10 16:37:53,178 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-10 16:37:53,178 INFO L276 IsEmpty]: Start isEmpty. Operand 829 states and 830 transitions. [2018-10-10 16:37:53,183 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 829 [2018-10-10 16:37:53,183 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:37:53,183 INFO L375 BasicCegarLoop]: trace histogram [27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:37:53,184 INFO L424 AbstractCegarLoop]: === Iteration 55 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:37:53,184 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:37:53,184 INFO L82 PathProgramCache]: Analyzing trace with hash 1288191887, now seen corresponding path program 52 times [2018-10-10 16:37:53,184 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:37:53,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:37:58,395 INFO L134 CoverageAnalysis]: Checked inductivity of 10297 backedges. 5000 proven. 5297 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:37:58,395 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:37:58,395 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-10 16:37:58,396 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-10 16:37:58,396 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-10 16:37:58,396 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1428, Invalid=11228, Unknown=0, NotChecked=0, Total=12656 [2018-10-10 16:37:58,396 INFO L87 Difference]: Start difference. First operand 829 states and 830 transitions. Second operand 113 states. [2018-10-10 16:38:23,281 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:38:23,281 INFO L93 Difference]: Finished difference Result 863 states and 864 transitions. [2018-10-10 16:38:23,281 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-10-10 16:38:23,281 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 828 [2018-10-10 16:38:23,282 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:38:23,284 INFO L225 Difference]: With dead ends: 863 [2018-10-10 16:38:23,284 INFO L226 Difference]: Without dead ends: 863 [2018-10-10 16:38:23,286 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 277 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 271 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20491 ImplicationChecksByTransitivity, 18.6s TimeCoverageRelationStatistics Valid=12759, Invalid=61497, Unknown=0, NotChecked=0, Total=74256 [2018-10-10 16:38:23,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 863 states. [2018-10-10 16:38:23,291 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 863 to 843. [2018-10-10 16:38:23,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 843 states. [2018-10-10 16:38:23,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 843 states to 843 states and 844 transitions. [2018-10-10 16:38:23,292 INFO L78 Accepts]: Start accepts. Automaton has 843 states and 844 transitions. Word has length 828 [2018-10-10 16:38:23,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:38:23,292 INFO L481 AbstractCegarLoop]: Abstraction has 843 states and 844 transitions. [2018-10-10 16:38:23,292 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-10 16:38:23,292 INFO L276 IsEmpty]: Start isEmpty. Operand 843 states and 844 transitions. [2018-10-10 16:38:23,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 843 [2018-10-10 16:38:23,296 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:38:23,297 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 28, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:38:23,297 INFO L424 AbstractCegarLoop]: === Iteration 56 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:38:23,297 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:38:23,297 INFO L82 PathProgramCache]: Analyzing trace with hash 2135645151, now seen corresponding path program 53 times [2018-10-10 16:38:23,298 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:38:23,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:38:27,437 INFO L134 CoverageAnalysis]: Checked inductivity of 10665 backedges. 4683 proven. 5982 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:38:27,437 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:38:27,437 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-10 16:38:27,438 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-10 16:38:27,439 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-10 16:38:27,439 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1630, Invalid=11026, Unknown=0, NotChecked=0, Total=12656 [2018-10-10 16:38:27,439 INFO L87 Difference]: Start difference. First operand 843 states and 844 transitions. Second operand 113 states. [2018-10-10 16:38:38,462 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:38:38,462 INFO L93 Difference]: Finished difference Result 1253 states and 1254 transitions. [2018-10-10 16:38:38,463 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-10 16:38:38,463 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 842 [2018-10-10 16:38:38,464 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:38:38,466 INFO L225 Difference]: With dead ends: 1253 [2018-10-10 16:38:38,466 INFO L226 Difference]: Without dead ends: 873 [2018-10-10 16:38:38,468 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 248 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17220 ImplicationChecksByTransitivity, 9.3s TimeCoverageRelationStatistics Valid=9342, Invalid=52908, Unknown=0, NotChecked=0, Total=62250 [2018-10-10 16:38:38,468 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 873 states. [2018-10-10 16:38:38,473 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 873 to 859. [2018-10-10 16:38:38,473 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 859 states. [2018-10-10 16:38:38,474 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 859 states to 859 states and 860 transitions. [2018-10-10 16:38:38,474 INFO L78 Accepts]: Start accepts. Automaton has 859 states and 860 transitions. Word has length 842 [2018-10-10 16:38:38,475 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:38:38,475 INFO L481 AbstractCegarLoop]: Abstraction has 859 states and 860 transitions. [2018-10-10 16:38:38,475 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-10 16:38:38,475 INFO L276 IsEmpty]: Start isEmpty. Operand 859 states and 860 transitions. [2018-10-10 16:38:38,479 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 859 [2018-10-10 16:38:38,479 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:38:38,480 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:38:38,480 INFO L424 AbstractCegarLoop]: === Iteration 57 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:38:38,480 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:38:38,480 INFO L82 PathProgramCache]: Analyzing trace with hash -732272403, now seen corresponding path program 54 times [2018-10-10 16:38:38,481 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:38:38,527 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:38:43,958 INFO L134 CoverageAnalysis]: Checked inductivity of 11098 backedges. 5408 proven. 5690 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:38:43,958 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:38:43,959 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [117] total 117 [2018-10-10 16:38:43,959 INFO L460 AbstractCegarLoop]: Interpolant automaton has 117 states [2018-10-10 16:38:43,959 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 117 interpolants. [2018-10-10 16:38:43,960 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1487, Invalid=12085, Unknown=0, NotChecked=0, Total=13572 [2018-10-10 16:38:43,960 INFO L87 Difference]: Start difference. First operand 859 states and 860 transitions. Second operand 117 states.