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-093a8c0 [2018-10-14 18:15:48,371 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-14 18:15:48,374 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-14 18:15:48,386 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-14 18:15:48,386 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-14 18:15:48,388 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-14 18:15:48,389 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-14 18:15:48,391 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-14 18:15:48,392 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-14 18:15:48,393 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-14 18:15:48,394 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-14 18:15:48,394 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-14 18:15:48,395 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-14 18:15:48,396 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-14 18:15:48,397 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-14 18:15:48,398 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-14 18:15:48,399 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-14 18:15:48,401 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-14 18:15:48,403 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-14 18:15:48,404 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-14 18:15:48,406 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-14 18:15:48,407 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-14 18:15:48,411 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-14 18:15:48,412 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-14 18:15:48,412 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-14 18:15:48,414 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-14 18:15:48,415 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-14 18:15:48,416 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-14 18:15:48,420 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-14 18:15:48,422 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-14 18:15:48,422 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-14 18:15:48,422 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-14 18:15:48,424 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-14 18:15:48,424 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-14 18:15:48,425 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-14 18:15:48,428 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-14 18:15:48,428 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-14 18:15:48,447 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-14 18:15:48,447 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-14 18:15:48,449 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-14 18:15:48,450 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-14 18:15:48,450 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-14 18:15:48,450 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-14 18:15:48,451 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-14 18:15:48,451 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-14 18:15:48,451 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-14 18:15:48,452 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-14 18:15:48,452 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-14 18:15:48,452 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-14 18:15:48,452 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-14 18:15:48,454 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-14 18:15:48,454 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-14 18:15:48,513 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-14 18:15:48,528 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-14 18:15:48,534 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-14 18:15:48,536 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-14 18:15:48,537 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-14 18:15:48,538 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-14 18:15:48,538 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-14 18:15:48,607 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-14 18:15:48,608 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-10-14 18:15:48,609 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-14 18:15:48,609 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-14 18:15:48,609 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-14 18:15:48,637 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 14.10 06:15:48" (1/1) ... [2018-10-14 18:15:48,639 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 14.10 06:15:48" (1/1) ... [2018-10-14 18:15:48,655 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 14.10 06:15:48" (1/1) ... [2018-10-14 18:15:48,655 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 14.10 06:15:48" (1/1) ... [2018-10-14 18:15:48,662 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 14.10 06:15:48" (1/1) ... [2018-10-14 18:15:48,664 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 14.10 06:15:48" (1/1) ... [2018-10-14 18:15:48,665 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 14.10 06:15:48" (1/1) ... [2018-10-14 18:15:48,674 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-14 18:15:48,675 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-14 18:15:48,675 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-14 18:15:48,675 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-14 18:15:48,676 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 14.10 06:15:48" (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-14 18:15:48,756 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2018-10-14 18:15:48,756 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-14 18:15:48,756 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-14 18:15:49,316 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-14 18:15:49,316 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 14.10 06:15:49 BoogieIcfgContainer [2018-10-14 18:15:49,317 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-14 18:15:49,317 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-10-14 18:15:49,317 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-10-14 18:15:49,318 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-10-14 18:15:49,321 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 14.10 06:15:49" (1/1) ... [2018-10-14 18:15:49,330 INFO L137 apSepIcfgTransformer]: HeapSepIcfgTransformer: Starting heap partitioning [2018-10-14 18:15:49,330 INFO L138 apSepIcfgTransformer]: To be partitioned heap arrays found [#memory_int] [2018-10-14 18:15:49,366 INFO L191 apSepIcfgTransformer]: Heap separator: starting loc-array-style preprocessing [2018-10-14 18:15:49,409 INFO L219 apSepIcfgTransformer]: finished MemlocArrayUpdater [2018-10-14 18:15:49,424 INFO L282 apSepIcfgTransformer]: finished preprocessing for the equality analysis [2018-10-14 18:15:49,487 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=1) [2018-10-14 18:15:53,534 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-14 18:15:53,537 INFO L306 apSepIcfgTransformer]: finished equality analysis [2018-10-14 18:15:53,542 INFO L318 apSepIcfgTransformer]: Finished detection of select terms ("array reads") [2018-10-14 18:15:53,554 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-14 18:15:53,556 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-14 18:15:53,582 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-14 18:15:53,583 INFO L232 HeapPartitionManager]: partitioning result: [2018-10-14 18:15:53,584 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-14 18:15:53,585 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-14 18:15:53,586 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-14 18:15:53,586 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-14 18:15:53,586 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-14 18:15:53,587 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-14 18:15:53,587 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-14 18:15:53,587 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-14 18:15:53,587 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-14 18:15:53,587 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-14 18:15:53,588 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-14 18:15:53,588 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-14 18:15:53,588 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-14 18:15:53,590 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-14 18:15:53,592 INFO L145 ransitionTransformer]: executing heap partitioning transformation [2018-10-14 18:15:53,617 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 14.10 06:15:53 BasicIcfg [2018-10-14 18:15:53,617 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-10-14 18:15:53,618 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-14 18:15:53,618 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-14 18:15:53,622 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-14 18:15:53,622 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 14.10 06:15:48" (1/3) ... [2018-10-14 18:15:53,624 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ab98cc5 and model type count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.10 06:15:53, skipping insertion in model container [2018-10-14 18:15:53,624 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 14.10 06:15:49" (2/3) ... [2018-10-14 18:15:53,624 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ab98cc5 and model type count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 14.10 06:15:53, skipping insertion in model container [2018-10-14 18:15:53,624 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 14.10 06:15:53" (3/3) ... [2018-10-14 18:15:53,626 INFO L112 eAbstractionObserver]: Analyzing ICFG memPartitionedIcfg [2018-10-14 18:15:53,638 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-14 18:15:53,647 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-14 18:15:53,668 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-14 18:15:53,703 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-14 18:15:53,704 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-14 18:15:53,704 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-14 18:15:53,704 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-14 18:15:53,705 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-14 18:15:53,705 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-14 18:15:53,705 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-14 18:15:53,705 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-14 18:15:53,706 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-14 18:15:53,722 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states. [2018-10-14 18:15:53,733 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-10-14 18:15:53,734 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:15:53,735 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-14 18:15:53,736 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:15:53,742 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:15:53,743 INFO L82 PathProgramCache]: Analyzing trace with hash 964056693, now seen corresponding path program 1 times [2018-10-14 18:15:53,814 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:15:53,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:15:54,146 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-14 18:15:54,149 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-14 18:15:54,150 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-14 18:15:54,156 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-14 18:15:54,169 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-14 18:15:54,170 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-14 18:15:54,173 INFO L87 Difference]: Start difference. First operand 60 states. Second operand 4 states. [2018-10-14 18:15:54,436 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:15:54,436 INFO L93 Difference]: Finished difference Result 73 states and 74 transitions. [2018-10-14 18:15:54,437 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-14 18:15:54,439 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 32 [2018-10-14 18:15:54,439 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:15:54,514 INFO L225 Difference]: With dead ends: 73 [2018-10-14 18:15:54,514 INFO L226 Difference]: Without dead ends: 73 [2018-10-14 18:15:54,518 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-14 18:15:54,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2018-10-14 18:15:54,557 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 59. [2018-10-14 18:15:54,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2018-10-14 18:15:54,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 60 transitions. [2018-10-14 18:15:54,563 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 60 transitions. Word has length 32 [2018-10-14 18:15:54,564 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:15:54,564 INFO L481 AbstractCegarLoop]: Abstraction has 59 states and 60 transitions. [2018-10-14 18:15:54,564 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-14 18:15:54,564 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 60 transitions. [2018-10-14 18:15:54,566 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2018-10-14 18:15:54,568 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:15:54,568 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-14 18:15:54,568 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:15:54,569 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:15:54,569 INFO L82 PathProgramCache]: Analyzing trace with hash 575190275, now seen corresponding path program 1 times [2018-10-14 18:15:54,570 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:15:54,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:15:55,153 WARN L179 SmtUtils]: Spent 187.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 16 [2018-10-14 18:15:55,557 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-14 18:15:55,558 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:15:55,558 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-10-14 18:15:55,560 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-14 18:15:55,560 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-14 18:15:55,560 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2018-10-14 18:15:55,561 INFO L87 Difference]: Start difference. First operand 59 states and 60 transitions. Second operand 12 states. [2018-10-14 18:15:56,530 WARN L179 SmtUtils]: Spent 128.00 ms on a formula simplification that was a NOOP. DAG size: 28 [2018-10-14 18:15:56,978 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:15:56,979 INFO L93 Difference]: Finished difference Result 121 states and 123 transitions. [2018-10-14 18:15:56,980 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-14 18:15:56,981 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 48 [2018-10-14 18:15:56,982 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:15:56,984 INFO L225 Difference]: With dead ends: 121 [2018-10-14 18:15:56,984 INFO L226 Difference]: Without dead ends: 121 [2018-10-14 18:15:56,986 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2018-10-14 18:15:56,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2018-10-14 18:15:56,999 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 80. [2018-10-14 18:15:57,000 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-10-14 18:15:57,003 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 82 transitions. [2018-10-14 18:15:57,003 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 82 transitions. Word has length 48 [2018-10-14 18:15:57,004 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:15:57,004 INFO L481 AbstractCegarLoop]: Abstraction has 80 states and 82 transitions. [2018-10-14 18:15:57,004 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-14 18:15:57,004 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 82 transitions. [2018-10-14 18:15:57,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-10-14 18:15:57,008 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:15:57,008 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-14 18:15:57,008 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:15:57,008 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:15:57,012 INFO L82 PathProgramCache]: Analyzing trace with hash -1278790061, now seen corresponding path program 1 times [2018-10-14 18:15:57,013 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:15:57,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:15:57,242 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-14 18:15:57,242 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:15:57,242 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-14 18:15:57,243 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-14 18:15:57,243 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-14 18:15:57,243 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-10-14 18:15:57,244 INFO L87 Difference]: Start difference. First operand 80 states and 82 transitions. Second operand 9 states. [2018-10-14 18:15:57,552 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:15:57,553 INFO L93 Difference]: Finished difference Result 105 states and 106 transitions. [2018-10-14 18:15:57,556 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-14 18:15:57,556 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 62 [2018-10-14 18:15:57,557 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:15:57,558 INFO L225 Difference]: With dead ends: 105 [2018-10-14 18:15:57,558 INFO L226 Difference]: Without dead ends: 89 [2018-10-14 18:15:57,558 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-14 18:15:57,559 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-10-14 18:15:57,563 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 75. [2018-10-14 18:15:57,564 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-10-14 18:15:57,564 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 76 transitions. [2018-10-14 18:15:57,565 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 76 transitions. Word has length 62 [2018-10-14 18:15:57,565 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:15:57,565 INFO L481 AbstractCegarLoop]: Abstraction has 75 states and 76 transitions. [2018-10-14 18:15:57,565 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-14 18:15:57,566 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 76 transitions. [2018-10-14 18:15:57,567 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-10-14 18:15:57,567 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:15:57,567 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-14 18:15:57,567 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:15:57,567 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:15:57,568 INFO L82 PathProgramCache]: Analyzing trace with hash 1155020689, now seen corresponding path program 2 times [2018-10-14 18:15:57,568 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:15:57,587 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:15:57,889 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-14 18:15:57,890 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:15:57,890 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-14 18:15:57,890 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-14 18:15:57,890 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-14 18:15:57,891 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-10-14 18:15:57,891 INFO L87 Difference]: Start difference. First operand 75 states and 76 transitions. Second operand 9 states. [2018-10-14 18:15:58,231 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:15:58,232 INFO L93 Difference]: Finished difference Result 88 states and 89 transitions. [2018-10-14 18:15:58,233 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-14 18:15:58,233 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 64 [2018-10-14 18:15:58,234 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:15:58,234 INFO L225 Difference]: With dead ends: 88 [2018-10-14 18:15:58,235 INFO L226 Difference]: Without dead ends: 88 [2018-10-14 18:15:58,235 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2018-10-14 18:15:58,235 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2018-10-14 18:15:58,240 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 79. [2018-10-14 18:15:58,240 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-10-14 18:15:58,241 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 80 transitions. [2018-10-14 18:15:58,242 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 80 transitions. Word has length 64 [2018-10-14 18:15:58,242 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:15:58,242 INFO L481 AbstractCegarLoop]: Abstraction has 79 states and 80 transitions. [2018-10-14 18:15:58,242 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-14 18:15:58,242 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 80 transitions. [2018-10-14 18:15:58,244 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2018-10-14 18:15:58,244 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:15:58,245 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-14 18:15:58,245 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:15:58,245 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:15:58,245 INFO L82 PathProgramCache]: Analyzing trace with hash -205510559, now seen corresponding path program 2 times [2018-10-14 18:15:58,246 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:15:58,275 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:15:58,544 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-14 18:15:58,545 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:15:58,545 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-14 18:15:58,545 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-14 18:15:58,545 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-14 18:15:58,546 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-10-14 18:15:58,546 INFO L87 Difference]: Start difference. First operand 79 states and 80 transitions. Second operand 13 states. [2018-10-14 18:15:59,777 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:15:59,778 INFO L93 Difference]: Finished difference Result 174 states and 176 transitions. [2018-10-14 18:15:59,779 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-14 18:15:59,780 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 78 [2018-10-14 18:15:59,780 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:15:59,782 INFO L225 Difference]: With dead ends: 174 [2018-10-14 18:15:59,782 INFO L226 Difference]: Without dead ends: 174 [2018-10-14 18:15:59,783 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-14 18:15:59,783 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-10-14 18:15:59,790 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 93. [2018-10-14 18:15:59,790 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-10-14 18:15:59,791 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 94 transitions. [2018-10-14 18:15:59,791 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 94 transitions. Word has length 78 [2018-10-14 18:15:59,791 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:15:59,792 INFO L481 AbstractCegarLoop]: Abstraction has 93 states and 94 transitions. [2018-10-14 18:15:59,792 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-14 18:15:59,792 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 94 transitions. [2018-10-14 18:15:59,793 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2018-10-14 18:15:59,793 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:15:59,793 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-14 18:15:59,794 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:15:59,794 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:15:59,794 INFO L82 PathProgramCache]: Analyzing trace with hash -1203081935, now seen corresponding path program 3 times [2018-10-14 18:15:59,795 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:15:59,813 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:00,008 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-14 18:16:00,008 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:00,008 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-14 18:16:00,009 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-14 18:16:00,009 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-14 18:16:00,009 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-10-14 18:16:00,009 INFO L87 Difference]: Start difference. First operand 93 states and 94 transitions. Second operand 13 states. [2018-10-14 18:16:00,428 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:00,429 INFO L93 Difference]: Finished difference Result 153 states and 154 transitions. [2018-10-14 18:16:00,429 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-14 18:16:00,429 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 92 [2018-10-14 18:16:00,430 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:00,431 INFO L225 Difference]: With dead ends: 153 [2018-10-14 18:16:00,432 INFO L226 Difference]: Without dead ends: 123 [2018-10-14 18:16:00,433 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=117, Invalid=483, Unknown=0, NotChecked=0, Total=600 [2018-10-14 18:16:00,433 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2018-10-14 18:16:00,441 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 109. [2018-10-14 18:16:00,444 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-10-14 18:16:00,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 110 transitions. [2018-10-14 18:16:00,445 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 110 transitions. Word has length 92 [2018-10-14 18:16:00,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:00,446 INFO L481 AbstractCegarLoop]: Abstraction has 109 states and 110 transitions. [2018-10-14 18:16:00,446 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-14 18:16:00,446 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 110 transitions. [2018-10-14 18:16:00,448 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2018-10-14 18:16:00,448 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:00,448 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-14 18:16:00,448 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:00,449 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:00,449 INFO L82 PathProgramCache]: Analyzing trace with hash -397749569, now seen corresponding path program 4 times [2018-10-14 18:16:00,450 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:00,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:00,913 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-14 18:16:00,913 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:00,913 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-14 18:16:00,914 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-14 18:16:00,914 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-14 18:16:00,914 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=238, Unknown=0, NotChecked=0, Total=272 [2018-10-14 18:16:00,915 INFO L87 Difference]: Start difference. First operand 109 states and 110 transitions. Second operand 17 states. [2018-10-14 18:16:02,380 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:02,380 INFO L93 Difference]: Finished difference Result 143 states and 144 transitions. [2018-10-14 18:16:02,380 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-14 18:16:02,381 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 108 [2018-10-14 18:16:02,381 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:02,382 INFO L225 Difference]: With dead ends: 143 [2018-10-14 18:16:02,382 INFO L226 Difference]: Without dead ends: 143 [2018-10-14 18:16:02,384 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=185, Invalid=1075, Unknown=0, NotChecked=0, Total=1260 [2018-10-14 18:16:02,384 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2018-10-14 18:16:02,390 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 123. [2018-10-14 18:16:02,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 123 states. [2018-10-14 18:16:02,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 124 transitions. [2018-10-14 18:16:02,391 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 124 transitions. Word has length 108 [2018-10-14 18:16:02,391 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:02,392 INFO L481 AbstractCegarLoop]: Abstraction has 123 states and 124 transitions. [2018-10-14 18:16:02,392 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-14 18:16:02,392 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 124 transitions. [2018-10-14 18:16:02,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2018-10-14 18:16:02,394 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:02,394 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-14 18:16:02,394 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:02,395 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:02,395 INFO L82 PathProgramCache]: Analyzing trace with hash -1502307569, now seen corresponding path program 5 times [2018-10-14 18:16:02,396 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:02,412 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:02,673 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-14 18:16:02,674 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:02,674 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-14 18:16:02,674 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-14 18:16:02,675 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-14 18:16:02,675 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2018-10-14 18:16:02,675 INFO L87 Difference]: Start difference. First operand 123 states and 124 transitions. Second operand 17 states. [2018-10-14 18:16:03,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:03,183 INFO L93 Difference]: Finished difference Result 197 states and 198 transitions. [2018-10-14 18:16:03,187 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-14 18:16:03,187 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 122 [2018-10-14 18:16:03,188 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:03,189 INFO L225 Difference]: With dead ends: 197 [2018-10-14 18:16:03,189 INFO L226 Difference]: Without dead ends: 153 [2018-10-14 18:16:03,190 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-14 18:16:03,190 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2018-10-14 18:16:03,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 139. [2018-10-14 18:16:03,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 139 states. [2018-10-14 18:16:03,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 140 transitions. [2018-10-14 18:16:03,197 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 140 transitions. Word has length 122 [2018-10-14 18:16:03,197 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:03,197 INFO L481 AbstractCegarLoop]: Abstraction has 139 states and 140 transitions. [2018-10-14 18:16:03,198 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-14 18:16:03,198 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 140 transitions. [2018-10-14 18:16:03,200 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2018-10-14 18:16:03,200 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:03,200 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-14 18:16:03,200 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:03,201 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:03,201 INFO L82 PathProgramCache]: Analyzing trace with hash 1184191517, now seen corresponding path program 6 times [2018-10-14 18:16:03,202 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:03,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:03,955 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-14 18:16:03,956 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:03,956 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-14 18:16:03,956 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-14 18:16:03,956 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-14 18:16:03,957 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=375, Unknown=0, NotChecked=0, Total=420 [2018-10-14 18:16:03,957 INFO L87 Difference]: Start difference. First operand 139 states and 140 transitions. Second operand 21 states. [2018-10-14 18:16:05,806 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:05,806 INFO L93 Difference]: Finished difference Result 173 states and 174 transitions. [2018-10-14 18:16:05,807 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-14 18:16:05,807 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 138 [2018-10-14 18:16:05,807 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:05,809 INFO L225 Difference]: With dead ends: 173 [2018-10-14 18:16:05,809 INFO L226 Difference]: Without dead ends: 173 [2018-10-14 18:16:05,811 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 330 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=259, Invalid=1721, Unknown=0, NotChecked=0, Total=1980 [2018-10-14 18:16:05,811 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2018-10-14 18:16:05,815 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 153. [2018-10-14 18:16:05,815 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 153 states. [2018-10-14 18:16:05,816 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 154 transitions. [2018-10-14 18:16:05,816 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 154 transitions. Word has length 138 [2018-10-14 18:16:05,817 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:05,817 INFO L481 AbstractCegarLoop]: Abstraction has 153 states and 154 transitions. [2018-10-14 18:16:05,817 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-14 18:16:05,817 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 154 transitions. [2018-10-14 18:16:05,819 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 153 [2018-10-14 18:16:05,819 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:05,820 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-14 18:16:05,820 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:05,820 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:05,820 INFO L82 PathProgramCache]: Analyzing trace with hash -900046867, now seen corresponding path program 7 times [2018-10-14 18:16:05,821 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:05,837 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:06,670 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-14 18:16:06,670 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:06,670 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-14 18:16:06,671 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-14 18:16:06,671 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-14 18:16:06,671 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=354, Unknown=0, NotChecked=0, Total=420 [2018-10-14 18:16:06,672 INFO L87 Difference]: Start difference. First operand 153 states and 154 transitions. Second operand 21 states. [2018-10-14 18:16:07,345 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:07,346 INFO L93 Difference]: Finished difference Result 241 states and 242 transitions. [2018-10-14 18:16:07,346 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-10-14 18:16:07,346 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 152 [2018-10-14 18:16:07,347 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:07,348 INFO L225 Difference]: With dead ends: 241 [2018-10-14 18:16:07,348 INFO L226 Difference]: Without dead ends: 183 [2018-10-14 18:16:07,349 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 384 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=303, Invalid=1503, Unknown=0, NotChecked=0, Total=1806 [2018-10-14 18:16:07,349 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2018-10-14 18:16:07,353 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 169. [2018-10-14 18:16:07,353 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 169 states. [2018-10-14 18:16:07,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 170 transitions. [2018-10-14 18:16:07,354 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 170 transitions. Word has length 152 [2018-10-14 18:16:07,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:07,354 INFO L481 AbstractCegarLoop]: Abstraction has 169 states and 170 transitions. [2018-10-14 18:16:07,354 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-14 18:16:07,355 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 170 transitions. [2018-10-14 18:16:07,356 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 169 [2018-10-14 18:16:07,356 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:07,357 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-14 18:16:07,357 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:07,357 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:07,357 INFO L82 PathProgramCache]: Analyzing trace with hash -806597509, now seen corresponding path program 8 times [2018-10-14 18:16:07,358 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:07,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:08,227 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-14 18:16:08,227 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:08,227 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-14 18:16:08,228 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-14 18:16:08,228 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-14 18:16:08,228 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=542, Unknown=0, NotChecked=0, Total=600 [2018-10-14 18:16:08,229 INFO L87 Difference]: Start difference. First operand 169 states and 170 transitions. Second operand 25 states. [2018-10-14 18:16:10,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:10,409 INFO L93 Difference]: Finished difference Result 203 states and 204 transitions. [2018-10-14 18:16:10,410 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-10-14 18:16:10,410 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 168 [2018-10-14 18:16:10,411 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:10,412 INFO L225 Difference]: With dead ends: 203 [2018-10-14 18:16:10,412 INFO L226 Difference]: Without dead ends: 203 [2018-10-14 18:16:10,414 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 523 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=349, Invalid=2513, Unknown=0, NotChecked=0, Total=2862 [2018-10-14 18:16:10,414 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2018-10-14 18:16:10,417 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 183. [2018-10-14 18:16:10,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 183 states. [2018-10-14 18:16:10,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 184 transitions. [2018-10-14 18:16:10,418 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 184 transitions. Word has length 168 [2018-10-14 18:16:10,419 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:10,419 INFO L481 AbstractCegarLoop]: Abstraction has 183 states and 184 transitions. [2018-10-14 18:16:10,419 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-14 18:16:10,419 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 184 transitions. [2018-10-14 18:16:10,420 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2018-10-14 18:16:10,421 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:10,421 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-14 18:16:10,421 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:10,421 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:10,421 INFO L82 PathProgramCache]: Analyzing trace with hash -760194101, now seen corresponding path program 9 times [2018-10-14 18:16:10,422 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:10,438 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:10,871 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-14 18:16:10,872 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:10,872 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-14 18:16:10,873 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-14 18:16:10,873 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-14 18:16:10,873 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=510, Unknown=0, NotChecked=0, Total=600 [2018-10-14 18:16:10,873 INFO L87 Difference]: Start difference. First operand 183 states and 184 transitions. Second operand 25 states. [2018-10-14 18:16:11,587 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:11,587 INFO L93 Difference]: Finished difference Result 285 states and 286 transitions. [2018-10-14 18:16:11,587 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-14 18:16:11,588 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 182 [2018-10-14 18:16:11,589 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:11,590 INFO L225 Difference]: With dead ends: 285 [2018-10-14 18:16:11,590 INFO L226 Difference]: Without dead ends: 213 [2018-10-14 18:16:11,592 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 599 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=432, Invalid=2220, Unknown=0, NotChecked=0, Total=2652 [2018-10-14 18:16:11,592 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-10-14 18:16:11,595 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-10-14 18:16:11,595 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-10-14 18:16:11,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 200 transitions. [2018-10-14 18:16:11,596 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 200 transitions. Word has length 182 [2018-10-14 18:16:11,596 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:11,596 INFO L481 AbstractCegarLoop]: Abstraction has 199 states and 200 transitions. [2018-10-14 18:16:11,596 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-14 18:16:11,597 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 200 transitions. [2018-10-14 18:16:11,597 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-10-14 18:16:11,598 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:11,598 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-14 18:16:11,598 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:11,598 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:11,598 INFO L82 PathProgramCache]: Analyzing trace with hash -1237558311, now seen corresponding path program 10 times [2018-10-14 18:16:11,599 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:11,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:12,233 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-14 18:16:12,234 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:12,234 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-14 18:16:12,234 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-14 18:16:12,235 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-14 18:16:12,235 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=721, Unknown=0, NotChecked=0, Total=812 [2018-10-14 18:16:12,235 INFO L87 Difference]: Start difference. First operand 199 states and 200 transitions. Second operand 29 states. [2018-10-14 18:16:15,410 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:15,411 INFO L93 Difference]: Finished difference Result 233 states and 234 transitions. [2018-10-14 18:16:15,420 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-10-14 18:16:15,420 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 198 [2018-10-14 18:16:15,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:15,421 INFO L225 Difference]: With dead ends: 233 [2018-10-14 18:16:15,422 INFO L226 Difference]: Without dead ends: 233 [2018-10-14 18:16:15,423 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 914 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=742, Invalid=3418, Unknown=0, NotChecked=0, Total=4160 [2018-10-14 18:16:15,424 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2018-10-14 18:16:15,426 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 213. [2018-10-14 18:16:15,427 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-10-14 18:16:15,427 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 214 transitions. [2018-10-14 18:16:15,428 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 214 transitions. Word has length 198 [2018-10-14 18:16:15,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:15,428 INFO L481 AbstractCegarLoop]: Abstraction has 213 states and 214 transitions. [2018-10-14 18:16:15,428 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-14 18:16:15,428 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 214 transitions. [2018-10-14 18:16:15,430 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-10-14 18:16:15,430 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:15,431 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-14 18:16:15,431 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:15,431 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:15,431 INFO L82 PathProgramCache]: Analyzing trace with hash 1187720873, now seen corresponding path program 11 times [2018-10-14 18:16:15,433 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:15,451 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:16,294 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-14 18:16:16,295 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:16,295 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-14 18:16:16,295 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-14 18:16:16,295 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-14 18:16:16,296 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=694, Unknown=0, NotChecked=0, Total=812 [2018-10-14 18:16:16,296 INFO L87 Difference]: Start difference. First operand 213 states and 214 transitions. Second operand 29 states. [2018-10-14 18:16:17,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:17,581 INFO L93 Difference]: Finished difference Result 329 states and 330 transitions. [2018-10-14 18:16:17,581 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-10-14 18:16:17,582 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 212 [2018-10-14 18:16:17,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:17,583 INFO L225 Difference]: With dead ends: 329 [2018-10-14 18:16:17,583 INFO L226 Difference]: Without dead ends: 243 [2018-10-14 18:16:17,584 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 861 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=585, Invalid=3075, Unknown=0, NotChecked=0, Total=3660 [2018-10-14 18:16:17,585 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 243 states. [2018-10-14 18:16:17,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 243 to 229. [2018-10-14 18:16:17,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 229 states. [2018-10-14 18:16:17,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 230 transitions. [2018-10-14 18:16:17,589 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 230 transitions. Word has length 212 [2018-10-14 18:16:17,589 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:17,589 INFO L481 AbstractCegarLoop]: Abstraction has 229 states and 230 transitions. [2018-10-14 18:16:17,589 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-14 18:16:17,590 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 230 transitions. [2018-10-14 18:16:17,590 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 229 [2018-10-14 18:16:17,591 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:17,591 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-14 18:16:17,591 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:17,591 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:17,591 INFO L82 PathProgramCache]: Analyzing trace with hash -1844305353, now seen corresponding path program 12 times [2018-10-14 18:16:17,592 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:17,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:18,414 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-14 18:16:18,414 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:18,414 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-14 18:16:18,415 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-14 18:16:18,415 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-14 18:16:18,416 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=948, Unknown=0, NotChecked=0, Total=1056 [2018-10-14 18:16:18,416 INFO L87 Difference]: Start difference. First operand 229 states and 230 transitions. Second operand 33 states. [2018-10-14 18:16:21,105 WARN L179 SmtUtils]: Spent 479.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 41 [2018-10-14 18:16:22,388 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:22,389 INFO L93 Difference]: Finished difference Result 263 states and 264 transitions. [2018-10-14 18:16:22,389 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2018-10-14 18:16:22,389 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 228 [2018-10-14 18:16:22,390 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:22,391 INFO L225 Difference]: With dead ends: 263 [2018-10-14 18:16:22,391 INFO L226 Difference]: Without dead ends: 263 [2018-10-14 18:16:22,392 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1181 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=869, Invalid=4387, Unknown=0, NotChecked=0, Total=5256 [2018-10-14 18:16:22,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 263 states. [2018-10-14 18:16:22,396 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 263 to 243. [2018-10-14 18:16:22,396 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 243 states. [2018-10-14 18:16:22,397 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 244 transitions. [2018-10-14 18:16:22,397 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 244 transitions. Word has length 228 [2018-10-14 18:16:22,397 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:22,398 INFO L481 AbstractCegarLoop]: Abstraction has 243 states and 244 transitions. [2018-10-14 18:16:22,398 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-14 18:16:22,398 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 244 transitions. [2018-10-14 18:16:22,399 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 243 [2018-10-14 18:16:22,399 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:22,399 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-14 18:16:22,400 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:22,400 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:22,400 INFO L82 PathProgramCache]: Analyzing trace with hash -56657785, now seen corresponding path program 13 times [2018-10-14 18:16:22,401 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:22,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:22,891 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-14 18:16:22,891 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:22,891 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-14 18:16:22,892 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-14 18:16:22,892 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-14 18:16:22,893 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=906, Unknown=0, NotChecked=0, Total=1056 [2018-10-14 18:16:22,893 INFO L87 Difference]: Start difference. First operand 243 states and 244 transitions. Second operand 33 states. [2018-10-14 18:16:23,736 WARN L179 SmtUtils]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-10-14 18:16:24,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:24,180 INFO L93 Difference]: Finished difference Result 373 states and 374 transitions. [2018-10-14 18:16:24,180 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-10-14 18:16:24,180 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 242 [2018-10-14 18:16:24,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:24,184 INFO L225 Difference]: With dead ends: 373 [2018-10-14 18:16:24,184 INFO L226 Difference]: Without dead ends: 273 [2018-10-14 18:16:24,186 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1170 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=762, Invalid=4068, Unknown=0, NotChecked=0, Total=4830 [2018-10-14 18:16:24,186 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 273 states. [2018-10-14 18:16:24,189 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 273 to 259. [2018-10-14 18:16:24,190 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 259 states. [2018-10-14 18:16:24,191 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 259 states to 259 states and 260 transitions. [2018-10-14 18:16:24,191 INFO L78 Accepts]: Start accepts. Automaton has 259 states and 260 transitions. Word has length 242 [2018-10-14 18:16:24,191 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:24,191 INFO L481 AbstractCegarLoop]: Abstraction has 259 states and 260 transitions. [2018-10-14 18:16:24,191 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-14 18:16:24,191 INFO L276 IsEmpty]: Start isEmpty. Operand 259 states and 260 transitions. [2018-10-14 18:16:24,193 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 259 [2018-10-14 18:16:24,193 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:24,193 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-14 18:16:24,193 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:24,193 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:24,193 INFO L82 PathProgramCache]: Analyzing trace with hash 1486503829, now seen corresponding path program 14 times [2018-10-14 18:16:24,194 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:24,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:25,741 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-14 18:16:25,742 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:25,742 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-14 18:16:25,742 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-14 18:16:25,743 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-14 18:16:25,743 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=1205, Unknown=0, NotChecked=0, Total=1332 [2018-10-14 18:16:25,743 INFO L87 Difference]: Start difference. First operand 259 states and 260 transitions. Second operand 37 states. [2018-10-14 18:16:29,773 WARN L179 SmtUtils]: Spent 139.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 41 [2018-10-14 18:16:30,303 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:30,303 INFO L93 Difference]: Finished difference Result 293 states and 294 transitions. [2018-10-14 18:16:30,310 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-10-14 18:16:30,310 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 258 [2018-10-14 18:16:30,311 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:30,312 INFO L225 Difference]: With dead ends: 293 [2018-10-14 18:16:30,312 INFO L226 Difference]: Without dead ends: 293 [2018-10-14 18:16:30,316 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1523 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=1031, Invalid=5611, Unknown=0, NotChecked=0, Total=6642 [2018-10-14 18:16:30,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-10-14 18:16:30,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 273. [2018-10-14 18:16:30,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 273 states. [2018-10-14 18:16:30,323 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 273 states to 273 states and 274 transitions. [2018-10-14 18:16:30,324 INFO L78 Accepts]: Start accepts. Automaton has 273 states and 274 transitions. Word has length 258 [2018-10-14 18:16:30,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:30,324 INFO L481 AbstractCegarLoop]: Abstraction has 273 states and 274 transitions. [2018-10-14 18:16:30,324 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-14 18:16:30,324 INFO L276 IsEmpty]: Start isEmpty. Operand 273 states and 274 transitions. [2018-10-14 18:16:30,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2018-10-14 18:16:30,326 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:30,326 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-14 18:16:30,326 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:30,327 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:30,327 INFO L82 PathProgramCache]: Analyzing trace with hash -1899898523, now seen corresponding path program 15 times [2018-10-14 18:16:30,328 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:30,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:31,125 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-14 18:16:31,125 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:31,125 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-14 18:16:31,125 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-14 18:16:31,126 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-14 18:16:31,126 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=186, Invalid=1146, Unknown=0, NotChecked=0, Total=1332 [2018-10-14 18:16:31,126 INFO L87 Difference]: Start difference. First operand 273 states and 274 transitions. Second operand 37 states. [2018-10-14 18:16:32,467 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:32,468 INFO L93 Difference]: Finished difference Result 417 states and 418 transitions. [2018-10-14 18:16:32,468 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-14 18:16:32,468 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 272 [2018-10-14 18:16:32,469 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:32,471 INFO L225 Difference]: With dead ends: 417 [2018-10-14 18:16:32,471 INFO L226 Difference]: Without dead ends: 303 [2018-10-14 18:16:32,473 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1526 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=963, Invalid=5199, Unknown=0, NotChecked=0, Total=6162 [2018-10-14 18:16:32,474 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2018-10-14 18:16:32,478 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 289. [2018-10-14 18:16:32,478 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 289 states. [2018-10-14 18:16:32,479 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 289 states to 289 states and 290 transitions. [2018-10-14 18:16:32,479 INFO L78 Accepts]: Start accepts. Automaton has 289 states and 290 transitions. Word has length 272 [2018-10-14 18:16:32,479 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:32,479 INFO L481 AbstractCegarLoop]: Abstraction has 289 states and 290 transitions. [2018-10-14 18:16:32,480 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-14 18:16:32,480 INFO L276 IsEmpty]: Start isEmpty. Operand 289 states and 290 transitions. [2018-10-14 18:16:32,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 289 [2018-10-14 18:16:32,481 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:32,481 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-14 18:16:32,482 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:32,482 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:32,482 INFO L82 PathProgramCache]: Analyzing trace with hash 1369527283, now seen corresponding path program 16 times [2018-10-14 18:16:32,483 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:32,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:33,609 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-14 18:16:33,610 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:33,610 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-14 18:16:33,610 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-14 18:16:33,611 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-14 18:16:33,611 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=1492, Unknown=0, NotChecked=0, Total=1640 [2018-10-14 18:16:33,612 INFO L87 Difference]: Start difference. First operand 289 states and 290 transitions. Second operand 41 states. [2018-10-14 18:16:38,454 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:38,454 INFO L93 Difference]: Finished difference Result 323 states and 324 transitions. [2018-10-14 18:16:38,455 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-10-14 18:16:38,455 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 288 [2018-10-14 18:16:38,456 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:38,457 INFO L225 Difference]: With dead ends: 323 [2018-10-14 18:16:38,457 INFO L226 Difference]: Without dead ends: 323 [2018-10-14 18:16:38,460 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1906 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=1208, Invalid=6982, Unknown=0, NotChecked=0, Total=8190 [2018-10-14 18:16:38,460 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 323 states. [2018-10-14 18:16:38,464 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 323 to 303. [2018-10-14 18:16:38,464 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 303 states. [2018-10-14 18:16:38,465 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 303 states to 303 states and 304 transitions. [2018-10-14 18:16:38,465 INFO L78 Accepts]: Start accepts. Automaton has 303 states and 304 transitions. Word has length 288 [2018-10-14 18:16:38,465 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:38,466 INFO L481 AbstractCegarLoop]: Abstraction has 303 states and 304 transitions. [2018-10-14 18:16:38,466 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-14 18:16:38,466 INFO L276 IsEmpty]: Start isEmpty. Operand 303 states and 304 transitions. [2018-10-14 18:16:38,467 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 303 [2018-10-14 18:16:38,467 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:38,468 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-14 18:16:38,468 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:38,468 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:38,468 INFO L82 PathProgramCache]: Analyzing trace with hash -765005501, now seen corresponding path program 17 times [2018-10-14 18:16:38,469 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:38,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:39,167 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-14 18:16:39,167 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:39,167 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-14 18:16:39,168 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-14 18:16:39,168 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-14 18:16:39,168 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=226, Invalid=1414, Unknown=0, NotChecked=0, Total=1640 [2018-10-14 18:16:39,169 INFO L87 Difference]: Start difference. First operand 303 states and 304 transitions. Second operand 41 states. [2018-10-14 18:16:40,744 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:40,745 INFO L93 Difference]: Finished difference Result 461 states and 462 transitions. [2018-10-14 18:16:40,745 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2018-10-14 18:16:40,745 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 302 [2018-10-14 18:16:40,746 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:40,748 INFO L225 Difference]: With dead ends: 461 [2018-10-14 18:16:40,748 INFO L226 Difference]: Without dead ends: 333 [2018-10-14 18:16:40,750 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1929 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1188, Invalid=6468, Unknown=0, NotChecked=0, Total=7656 [2018-10-14 18:16:40,750 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 333 states. [2018-10-14 18:16:40,754 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 333 to 319. [2018-10-14 18:16:40,754 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 319 states. [2018-10-14 18:16:40,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 319 states to 319 states and 320 transitions. [2018-10-14 18:16:40,755 INFO L78 Accepts]: Start accepts. Automaton has 319 states and 320 transitions. Word has length 302 [2018-10-14 18:16:40,755 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:40,755 INFO L481 AbstractCegarLoop]: Abstraction has 319 states and 320 transitions. [2018-10-14 18:16:40,756 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-14 18:16:40,756 INFO L276 IsEmpty]: Start isEmpty. Operand 319 states and 320 transitions. [2018-10-14 18:16:40,757 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 319 [2018-10-14 18:16:40,757 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:40,758 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-14 18:16:40,758 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:40,758 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:40,758 INFO L82 PathProgramCache]: Analyzing trace with hash 227802961, now seen corresponding path program 18 times [2018-10-14 18:16:40,759 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:40,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:41,970 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-14 18:16:41,970 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:41,971 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-14 18:16:41,971 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-14 18:16:41,971 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-14 18:16:41,972 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=219, Invalid=1761, Unknown=0, NotChecked=0, Total=1980 [2018-10-14 18:16:41,972 INFO L87 Difference]: Start difference. First operand 319 states and 320 transitions. Second operand 45 states. [2018-10-14 18:16:46,883 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:46,884 INFO L93 Difference]: Finished difference Result 353 states and 354 transitions. [2018-10-14 18:16:46,884 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-10-14 18:16:46,884 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 318 [2018-10-14 18:16:46,884 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:46,886 INFO L225 Difference]: With dead ends: 353 [2018-10-14 18:16:46,886 INFO L226 Difference]: Without dead ends: 353 [2018-10-14 18:16:46,888 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2716 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=1920, Invalid=9000, Unknown=0, NotChecked=0, Total=10920 [2018-10-14 18:16:46,888 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2018-10-14 18:16:46,892 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 333. [2018-10-14 18:16:46,892 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 333 states. [2018-10-14 18:16:46,893 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 334 transitions. [2018-10-14 18:16:46,893 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 334 transitions. Word has length 318 [2018-10-14 18:16:46,893 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:46,893 INFO L481 AbstractCegarLoop]: Abstraction has 333 states and 334 transitions. [2018-10-14 18:16:46,894 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-14 18:16:46,894 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 334 transitions. [2018-10-14 18:16:46,895 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 333 [2018-10-14 18:16:46,895 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:46,896 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-14 18:16:46,896 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:46,896 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:46,896 INFO L82 PathProgramCache]: Analyzing trace with hash 1298358305, now seen corresponding path program 19 times [2018-10-14 18:16:46,897 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:46,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:47,902 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-14 18:16:47,903 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:47,903 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-14 18:16:47,903 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-14 18:16:47,903 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-14 18:16:47,904 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=270, Invalid=1710, Unknown=0, NotChecked=0, Total=1980 [2018-10-14 18:16:47,904 INFO L87 Difference]: Start difference. First operand 333 states and 334 transitions. Second operand 45 states. [2018-10-14 18:16:49,932 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:49,933 INFO L93 Difference]: Finished difference Result 505 states and 506 transitions. [2018-10-14 18:16:49,933 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-10-14 18:16:49,933 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 332 [2018-10-14 18:16:49,934 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:49,936 INFO L225 Difference]: With dead ends: 505 [2018-10-14 18:16:49,936 INFO L226 Difference]: Without dead ends: 363 [2018-10-14 18:16:49,937 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2379 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=1437, Invalid=7875, Unknown=0, NotChecked=0, Total=9312 [2018-10-14 18:16:49,938 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 363 states. [2018-10-14 18:16:49,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 363 to 349. [2018-10-14 18:16:49,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 349 states. [2018-10-14 18:16:49,942 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 349 states to 349 states and 350 transitions. [2018-10-14 18:16:49,943 INFO L78 Accepts]: Start accepts. Automaton has 349 states and 350 transitions. Word has length 332 [2018-10-14 18:16:49,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:49,943 INFO L481 AbstractCegarLoop]: Abstraction has 349 states and 350 transitions. [2018-10-14 18:16:49,943 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-14 18:16:49,943 INFO L276 IsEmpty]: Start isEmpty. Operand 349 states and 350 transitions. [2018-10-14 18:16:49,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 349 [2018-10-14 18:16:49,945 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:49,945 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-14 18:16:49,945 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:49,946 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:49,946 INFO L82 PathProgramCache]: Analyzing trace with hash 1535041967, now seen corresponding path program 20 times [2018-10-14 18:16:49,946 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:49,970 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:51,415 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-14 18:16:51,416 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:51,416 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-14 18:16:51,416 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-14 18:16:51,417 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-14 18:16:51,417 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=244, Invalid=2108, Unknown=0, NotChecked=0, Total=2352 [2018-10-14 18:16:51,417 INFO L87 Difference]: Start difference. First operand 349 states and 350 transitions. Second operand 49 states. [2018-10-14 18:16:57,354 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:16:57,354 INFO L93 Difference]: Finished difference Result 383 states and 384 transitions. [2018-10-14 18:16:57,354 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-14 18:16:57,354 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 348 [2018-10-14 18:16:57,355 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:16:57,356 INFO L225 Difference]: With dead ends: 383 [2018-10-14 18:16:57,356 INFO L226 Difference]: Without dead ends: 383 [2018-10-14 18:16:57,357 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3155 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=2127, Invalid=10529, Unknown=0, NotChecked=0, Total=12656 [2018-10-14 18:16:57,358 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 383 states. [2018-10-14 18:16:57,362 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 383 to 363. [2018-10-14 18:16:57,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 363 states. [2018-10-14 18:16:57,363 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 364 transitions. [2018-10-14 18:16:57,363 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 364 transitions. Word has length 348 [2018-10-14 18:16:57,364 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:16:57,364 INFO L481 AbstractCegarLoop]: Abstraction has 363 states and 364 transitions. [2018-10-14 18:16:57,364 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-14 18:16:57,364 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 364 transitions. [2018-10-14 18:16:57,366 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 363 [2018-10-14 18:16:57,366 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:16:57,366 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-14 18:16:57,367 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:16:57,367 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:16:57,367 INFO L82 PathProgramCache]: Analyzing trace with hash -1406417409, now seen corresponding path program 21 times [2018-10-14 18:16:57,368 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:16:57,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:16:59,062 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-14 18:16:59,062 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:16:59,062 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-14 18:16:59,063 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-14 18:16:59,063 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-14 18:16:59,064 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=318, Invalid=2034, Unknown=0, NotChecked=0, Total=2352 [2018-10-14 18:16:59,064 INFO L87 Difference]: Start difference. First operand 363 states and 364 transitions. Second operand 49 states. [2018-10-14 18:17:01,589 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:17:01,589 INFO L93 Difference]: Finished difference Result 549 states and 550 transitions. [2018-10-14 18:17:01,589 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 71 states. [2018-10-14 18:17:01,589 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 362 [2018-10-14 18:17:01,590 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:17:01,591 INFO L225 Difference]: With dead ends: 549 [2018-10-14 18:17:01,591 INFO L226 Difference]: Without dead ends: 393 [2018-10-14 18:17:01,592 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2876 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=1710, Invalid=9420, Unknown=0, NotChecked=0, Total=11130 [2018-10-14 18:17:01,593 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 393 states. [2018-10-14 18:17:01,597 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 393 to 379. [2018-10-14 18:17:01,597 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-10-14 18:17:01,598 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 380 transitions. [2018-10-14 18:17:01,598 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 380 transitions. Word has length 362 [2018-10-14 18:17:01,599 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:17:01,599 INFO L481 AbstractCegarLoop]: Abstraction has 379 states and 380 transitions. [2018-10-14 18:17:01,599 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-14 18:17:01,599 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 380 transitions. [2018-10-14 18:17:01,601 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 379 [2018-10-14 18:17:01,601 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:17:01,601 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-14 18:17:01,601 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:17:01,602 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:17:01,602 INFO L82 PathProgramCache]: Analyzing trace with hash 1057921805, now seen corresponding path program 22 times [2018-10-14 18:17:01,603 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:17:01,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:17:03,526 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-14 18:17:03,526 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:17:03,526 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-14 18:17:03,527 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-14 18:17:03,527 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-14 18:17:03,527 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=271, Invalid=2485, Unknown=0, NotChecked=0, Total=2756 [2018-10-14 18:17:03,528 INFO L87 Difference]: Start difference. First operand 379 states and 380 transitions. Second operand 53 states. [2018-10-14 18:17:10,104 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:17:10,104 INFO L93 Difference]: Finished difference Result 413 states and 414 transitions. [2018-10-14 18:17:10,105 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-14 18:17:10,105 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 378 [2018-10-14 18:17:10,105 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:17:10,107 INFO L225 Difference]: With dead ends: 413 [2018-10-14 18:17:10,107 INFO L226 Difference]: Without dead ends: 413 [2018-10-14 18:17:10,109 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3697 ImplicationChecksByTransitivity, 5.6s TimeCoverageRelationStatistics Valid=2377, Invalid=12385, Unknown=0, NotChecked=0, Total=14762 [2018-10-14 18:17:10,109 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 413 states. [2018-10-14 18:17:10,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 413 to 393. [2018-10-14 18:17:10,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 393 states. [2018-10-14 18:17:10,115 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 393 states to 393 states and 394 transitions. [2018-10-14 18:17:10,115 INFO L78 Accepts]: Start accepts. Automaton has 393 states and 394 transitions. Word has length 378 [2018-10-14 18:17:10,116 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:17:10,116 INFO L481 AbstractCegarLoop]: Abstraction has 393 states and 394 transitions. [2018-10-14 18:17:10,116 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-14 18:17:10,116 INFO L276 IsEmpty]: Start isEmpty. Operand 393 states and 394 transitions. [2018-10-14 18:17:10,118 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 393 [2018-10-14 18:17:10,118 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:17:10,119 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-14 18:17:10,119 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:17:10,119 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:17:10,119 INFO L82 PathProgramCache]: Analyzing trace with hash 936690397, now seen corresponding path program 23 times [2018-10-14 18:17:10,120 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:17:10,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:17:12,094 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-14 18:17:12,095 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:17:12,095 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-14 18:17:12,095 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-14 18:17:12,096 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-14 18:17:12,096 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=370, Invalid=2386, Unknown=0, NotChecked=0, Total=2756 [2018-10-14 18:17:12,096 INFO L87 Difference]: Start difference. First operand 393 states and 394 transitions. Second operand 53 states. [2018-10-14 18:17:14,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:17:14,668 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-14 18:17:14,668 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-14 18:17:14,668 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 392 [2018-10-14 18:17:14,669 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:17:14,671 INFO L225 Difference]: With dead ends: 593 [2018-10-14 18:17:14,671 INFO L226 Difference]: Without dead ends: 423 [2018-10-14 18:17:14,672 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3420 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=2007, Invalid=11103, Unknown=0, NotChecked=0, Total=13110 [2018-10-14 18:17:14,672 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 423 states. [2018-10-14 18:17:14,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 423 to 409. [2018-10-14 18:17:14,677 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 409 states. [2018-10-14 18:17:14,677 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 409 states to 409 states and 410 transitions. [2018-10-14 18:17:14,678 INFO L78 Accepts]: Start accepts. Automaton has 409 states and 410 transitions. Word has length 392 [2018-10-14 18:17:14,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:17:14,678 INFO L481 AbstractCegarLoop]: Abstraction has 409 states and 410 transitions. [2018-10-14 18:17:14,678 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-14 18:17:14,678 INFO L276 IsEmpty]: Start isEmpty. Operand 409 states and 410 transitions. [2018-10-14 18:17:14,680 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 409 [2018-10-14 18:17:14,680 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:17:14,681 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-14 18:17:14,681 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:17:14,681 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:17:14,681 INFO L82 PathProgramCache]: Analyzing trace with hash -426783893, now seen corresponding path program 24 times [2018-10-14 18:17:14,682 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:17:14,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:17:17,479 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-14 18:17:17,480 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:17:17,480 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-14 18:17:17,480 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-14 18:17:17,481 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-14 18:17:17,481 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=234, Invalid=2958, Unknown=0, NotChecked=0, Total=3192 [2018-10-14 18:17:17,481 INFO L87 Difference]: Start difference. First operand 409 states and 410 transitions. Second operand 57 states. [2018-10-14 18:17:25,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:17:25,472 INFO L93 Difference]: Finished difference Result 443 states and 444 transitions. [2018-10-14 18:17:25,472 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-10-14 18:17:25,472 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 408 [2018-10-14 18:17:25,473 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:17:25,475 INFO L225 Difference]: With dead ends: 443 [2018-10-14 18:17:25,475 INFO L226 Difference]: Without dead ends: 443 [2018-10-14 18:17:25,476 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3543 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=1645, Invalid=14105, Unknown=0, NotChecked=0, Total=15750 [2018-10-14 18:17:25,476 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 443 states. [2018-10-14 18:17:25,480 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 443 to 423. [2018-10-14 18:17:25,480 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 423 states. [2018-10-14 18:17:25,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 423 states to 423 states and 424 transitions. [2018-10-14 18:17:25,481 INFO L78 Accepts]: Start accepts. Automaton has 423 states and 424 transitions. Word has length 408 [2018-10-14 18:17:25,482 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:17:25,482 INFO L481 AbstractCegarLoop]: Abstraction has 423 states and 424 transitions. [2018-10-14 18:17:25,482 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-14 18:17:25,482 INFO L276 IsEmpty]: Start isEmpty. Operand 423 states and 424 transitions. [2018-10-14 18:17:25,484 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 423 [2018-10-14 18:17:25,484 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:17:25,485 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-14 18:17:25,485 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:17:25,485 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:17:25,485 INFO L82 PathProgramCache]: Analyzing trace with hash 1276311227, now seen corresponding path program 25 times [2018-10-14 18:17:25,486 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:17:25,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:17:27,517 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-14 18:17:27,518 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:17:27,518 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-14 18:17:27,518 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-14 18:17:27,518 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-14 18:17:27,519 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=426, Invalid=2766, Unknown=0, NotChecked=0, Total=3192 [2018-10-14 18:17:27,519 INFO L87 Difference]: Start difference. First operand 423 states and 424 transitions. Second operand 57 states. [2018-10-14 18:17:30,389 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:17:30,390 INFO L93 Difference]: Finished difference Result 637 states and 638 transitions. [2018-10-14 18:17:30,390 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-14 18:17:30,390 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 422 [2018-10-14 18:17:30,391 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:17:30,393 INFO L225 Difference]: With dead ends: 637 [2018-10-14 18:17:30,393 INFO L226 Difference]: Without dead ends: 453 [2018-10-14 18:17:30,394 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4011 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=2328, Invalid=12924, Unknown=0, NotChecked=0, Total=15252 [2018-10-14 18:17:30,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 453 states. [2018-10-14 18:17:30,398 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 453 to 439. [2018-10-14 18:17:30,398 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 439 states. [2018-10-14 18:17:30,399 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 439 states to 439 states and 440 transitions. [2018-10-14 18:17:30,399 INFO L78 Accepts]: Start accepts. Automaton has 439 states and 440 transitions. Word has length 422 [2018-10-14 18:17:30,400 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:17:30,400 INFO L481 AbstractCegarLoop]: Abstraction has 439 states and 440 transitions. [2018-10-14 18:17:30,400 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-14 18:17:30,400 INFO L276 IsEmpty]: Start isEmpty. Operand 439 states and 440 transitions. [2018-10-14 18:17:30,402 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 439 [2018-10-14 18:17:30,402 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:17:30,403 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-14 18:17:30,403 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:17:30,403 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:17:30,403 INFO L82 PathProgramCache]: Analyzing trace with hash -1594944823, now seen corresponding path program 26 times [2018-10-14 18:17:30,404 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:17:30,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:17:32,375 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-14 18:17:32,375 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:17:32,376 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-14 18:17:32,376 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-14 18:17:32,376 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-14 18:17:32,376 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=411, Invalid=3249, Unknown=0, NotChecked=0, Total=3660 [2018-10-14 18:17:32,377 INFO L87 Difference]: Start difference. First operand 439 states and 440 transitions. Second operand 61 states. [2018-10-14 18:17:40,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:17:40,519 INFO L93 Difference]: Finished difference Result 473 states and 474 transitions. [2018-10-14 18:17:40,519 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-10-14 18:17:40,520 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 438 [2018-10-14 18:17:40,520 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:17:40,522 INFO L225 Difference]: With dead ends: 473 [2018-10-14 18:17:40,522 INFO L226 Difference]: Without dead ends: 473 [2018-10-14 18:17:40,523 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5462 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=3658, Invalid=17222, Unknown=0, NotChecked=0, Total=20880 [2018-10-14 18:17:40,524 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 473 states. [2018-10-14 18:17:40,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 473 to 453. [2018-10-14 18:17:40,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 453 states. [2018-10-14 18:17:40,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 453 states to 453 states and 454 transitions. [2018-10-14 18:17:40,529 INFO L78 Accepts]: Start accepts. Automaton has 453 states and 454 transitions. Word has length 438 [2018-10-14 18:17:40,530 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:17:40,530 INFO L481 AbstractCegarLoop]: Abstraction has 453 states and 454 transitions. [2018-10-14 18:17:40,530 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-14 18:17:40,530 INFO L276 IsEmpty]: Start isEmpty. Operand 453 states and 454 transitions. [2018-10-14 18:17:40,532 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 453 [2018-10-14 18:17:40,532 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:17:40,533 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-14 18:17:40,533 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:17:40,533 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:17:40,533 INFO L82 PathProgramCache]: Analyzing trace with hash -851770983, now seen corresponding path program 27 times [2018-10-14 18:17:40,534 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:17:40,560 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:17:41,989 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-14 18:17:41,989 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:17:41,989 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-14 18:17:41,990 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-14 18:17:41,990 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-14 18:17:41,990 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=486, Invalid=3174, Unknown=0, NotChecked=0, Total=3660 [2018-10-14 18:17:41,990 INFO L87 Difference]: Start difference. First operand 453 states and 454 transitions. Second operand 61 states. [2018-10-14 18:17:45,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:17:45,045 INFO L93 Difference]: Finished difference Result 681 states and 682 transitions. [2018-10-14 18:17:45,046 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-10-14 18:17:45,046 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 452 [2018-10-14 18:17:45,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:17:45,049 INFO L225 Difference]: With dead ends: 681 [2018-10-14 18:17:45,049 INFO L226 Difference]: Without dead ends: 483 [2018-10-14 18:17:45,050 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 131 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4649 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=2673, Invalid=14883, Unknown=0, NotChecked=0, Total=17556 [2018-10-14 18:17:45,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 483 states. [2018-10-14 18:17:45,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 483 to 469. [2018-10-14 18:17:45,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 469 states. [2018-10-14 18:17:45,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 469 states to 469 states and 470 transitions. [2018-10-14 18:17:45,056 INFO L78 Accepts]: Start accepts. Automaton has 469 states and 470 transitions. Word has length 452 [2018-10-14 18:17:45,056 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:17:45,056 INFO L481 AbstractCegarLoop]: Abstraction has 469 states and 470 transitions. [2018-10-14 18:17:45,057 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-14 18:17:45,057 INFO L276 IsEmpty]: Start isEmpty. Operand 469 states and 470 transitions. [2018-10-14 18:17:45,059 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 469 [2018-10-14 18:17:45,059 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:17:45,060 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-14 18:17:45,060 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:17:45,060 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:17:45,060 INFO L82 PathProgramCache]: Analyzing trace with hash -742846169, now seen corresponding path program 28 times [2018-10-14 18:17:45,061 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:17:45,090 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:17:46,966 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-14 18:17:46,967 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:17:46,967 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-14 18:17:46,967 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-14 18:17:46,968 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-14 18:17:46,968 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=444, Invalid=3716, Unknown=0, NotChecked=0, Total=4160 [2018-10-14 18:17:46,968 INFO L87 Difference]: Start difference. First operand 469 states and 470 transitions. Second operand 65 states. [2018-10-14 18:17:56,293 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:17:56,293 INFO L93 Difference]: Finished difference Result 503 states and 504 transitions. [2018-10-14 18:17:56,294 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 105 states. [2018-10-14 18:17:56,294 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 468 [2018-10-14 18:17:56,294 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:17:56,295 INFO L225 Difference]: With dead ends: 503 [2018-10-14 18:17:56,296 INFO L226 Difference]: Without dead ends: 503 [2018-10-14 18:17:56,297 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 151 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6073 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=3945, Invalid=19311, Unknown=0, NotChecked=0, Total=23256 [2018-10-14 18:17:56,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 503 states. [2018-10-14 18:17:56,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 503 to 483. [2018-10-14 18:17:56,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 483 states. [2018-10-14 18:17:56,302 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 483 states to 483 states and 484 transitions. [2018-10-14 18:17:56,302 INFO L78 Accepts]: Start accepts. Automaton has 483 states and 484 transitions. Word has length 468 [2018-10-14 18:17:56,303 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:17:56,303 INFO L481 AbstractCegarLoop]: Abstraction has 483 states and 484 transitions. [2018-10-14 18:17:56,303 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-14 18:17:56,303 INFO L276 IsEmpty]: Start isEmpty. Operand 483 states and 484 transitions. [2018-10-14 18:17:56,306 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 483 [2018-10-14 18:17:56,306 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:17:56,306 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-14 18:17:56,306 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:17:56,306 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:17:56,307 INFO L82 PathProgramCache]: Analyzing trace with hash -1639873673, now seen corresponding path program 29 times [2018-10-14 18:17:56,307 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:17:56,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:17:58,179 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-14 18:17:58,179 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:17:58,180 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-14 18:17:58,180 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-14 18:17:58,181 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-14 18:17:58,181 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=550, Invalid=3610, Unknown=0, NotChecked=0, Total=4160 [2018-10-14 18:17:58,181 INFO L87 Difference]: Start difference. First operand 483 states and 484 transitions. Second operand 65 states. [2018-10-14 18:18:01,806 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:18:01,806 INFO L93 Difference]: Finished difference Result 725 states and 726 transitions. [2018-10-14 18:18:01,806 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 95 states. [2018-10-14 18:18:01,806 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 482 [2018-10-14 18:18:01,807 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:18:01,809 INFO L225 Difference]: With dead ends: 725 [2018-10-14 18:18:01,809 INFO L226 Difference]: Without dead ends: 513 [2018-10-14 18:18:01,810 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5334 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=3042, Invalid=16980, Unknown=0, NotChecked=0, Total=20022 [2018-10-14 18:18:01,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 513 states. [2018-10-14 18:18:01,813 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 513 to 499. [2018-10-14 18:18:01,814 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 499 states. [2018-10-14 18:18:01,815 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 499 states to 499 states and 500 transitions. [2018-10-14 18:18:01,815 INFO L78 Accepts]: Start accepts. Automaton has 499 states and 500 transitions. Word has length 482 [2018-10-14 18:18:01,815 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:18:01,815 INFO L481 AbstractCegarLoop]: Abstraction has 499 states and 500 transitions. [2018-10-14 18:18:01,815 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-14 18:18:01,815 INFO L276 IsEmpty]: Start isEmpty. Operand 499 states and 500 transitions. [2018-10-14 18:18:01,818 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 499 [2018-10-14 18:18:01,818 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:18:01,818 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-14 18:18:01,819 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:18:01,819 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:18:01,819 INFO L82 PathProgramCache]: Analyzing trace with hash -249928059, now seen corresponding path program 30 times [2018-10-14 18:18:01,820 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:18:01,850 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:18:04,141 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-14 18:18:04,142 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:18:04,142 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-14 18:18:04,143 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-14 18:18:04,143 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-14 18:18:04,143 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=4213, Unknown=0, NotChecked=0, Total=4692 [2018-10-14 18:18:04,144 INFO L87 Difference]: Start difference. First operand 499 states and 500 transitions. Second operand 69 states. [2018-10-14 18:18:14,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:18:14,754 INFO L93 Difference]: Finished difference Result 533 states and 534 transitions. [2018-10-14 18:18:14,754 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 111 states. [2018-10-14 18:18:14,754 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 498 [2018-10-14 18:18:14,755 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:18:14,756 INFO L225 Difference]: With dead ends: 533 [2018-10-14 18:18:14,756 INFO L226 Difference]: Without dead ends: 533 [2018-10-14 18:18:14,758 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 160 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6815 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=4283, Invalid=21799, Unknown=0, NotChecked=0, Total=26082 [2018-10-14 18:18:14,758 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 533 states. [2018-10-14 18:18:14,762 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 533 to 513. [2018-10-14 18:18:14,762 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 513 states. [2018-10-14 18:18:14,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 513 states to 513 states and 514 transitions. [2018-10-14 18:18:14,763 INFO L78 Accepts]: Start accepts. Automaton has 513 states and 514 transitions. Word has length 498 [2018-10-14 18:18:14,764 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:18:14,764 INFO L481 AbstractCegarLoop]: Abstraction has 513 states and 514 transitions. [2018-10-14 18:18:14,764 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-14 18:18:14,764 INFO L276 IsEmpty]: Start isEmpty. Operand 513 states and 514 transitions. [2018-10-14 18:18:14,767 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 513 [2018-10-14 18:18:14,767 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:18:14,767 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-14 18:18:14,767 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:18:14,768 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:18:14,768 INFO L82 PathProgramCache]: Analyzing trace with hash 381361237, now seen corresponding path program 31 times [2018-10-14 18:18:14,768 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:18:14,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:18:16,453 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-14 18:18:16,453 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:18:16,453 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-14 18:18:16,454 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-14 18:18:16,454 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-14 18:18:16,454 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=618, Invalid=4074, Unknown=0, NotChecked=0, Total=4692 [2018-10-14 18:18:16,455 INFO L87 Difference]: Start difference. First operand 513 states and 514 transitions. Second operand 69 states. [2018-10-14 18:18:20,841 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:18:20,842 INFO L93 Difference]: Finished difference Result 769 states and 770 transitions. [2018-10-14 18:18:20,842 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 101 states. [2018-10-14 18:18:20,842 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 512 [2018-10-14 18:18:20,843 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:18:20,844 INFO L225 Difference]: With dead ends: 769 [2018-10-14 18:18:20,844 INFO L226 Difference]: Without dead ends: 543 [2018-10-14 18:18:20,845 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-14 18:18:20,846 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 543 states. [2018-10-14 18:18:20,849 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 543 to 529. [2018-10-14 18:18:20,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 529 states. [2018-10-14 18:18:20,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 529 states to 529 states and 530 transitions. [2018-10-14 18:18:20,851 INFO L78 Accepts]: Start accepts. Automaton has 529 states and 530 transitions. Word has length 512 [2018-10-14 18:18:20,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:18:20,851 INFO L481 AbstractCegarLoop]: Abstraction has 529 states and 530 transitions. [2018-10-14 18:18:20,851 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-14 18:18:20,851 INFO L276 IsEmpty]: Start isEmpty. Operand 529 states and 530 transitions. [2018-10-14 18:18:20,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 529 [2018-10-14 18:18:20,854 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:18:20,855 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-14 18:18:20,855 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:18:20,855 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:18:20,855 INFO L82 PathProgramCache]: Analyzing trace with hash 1843376867, now seen corresponding path program 32 times [2018-10-14 18:18:20,856 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:18:20,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:18:23,521 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-14 18:18:23,521 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:18:23,521 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-14 18:18:23,522 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-14 18:18:23,522 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-14 18:18:23,522 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=516, Invalid=4740, Unknown=0, NotChecked=0, Total=5256 [2018-10-14 18:18:23,523 INFO L87 Difference]: Start difference. First operand 529 states and 530 transitions. Second operand 73 states. [2018-10-14 18:18:35,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:18:35,547 INFO L93 Difference]: Finished difference Result 563 states and 564 transitions. [2018-10-14 18:18:35,552 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-10-14 18:18:35,553 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 528 [2018-10-14 18:18:35,553 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:18:35,555 INFO L225 Difference]: With dead ends: 563 [2018-10-14 18:18:35,555 INFO L226 Difference]: Without dead ends: 563 [2018-10-14 18:18:35,556 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 169 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7598 ImplicationChecksByTransitivity, 9.0s TimeCoverageRelationStatistics Valid=4636, Invalid=24434, Unknown=0, NotChecked=0, Total=29070 [2018-10-14 18:18:35,556 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 563 states. [2018-10-14 18:18:35,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 563 to 543. [2018-10-14 18:18:35,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 543 states. [2018-10-14 18:18:35,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 543 states to 543 states and 544 transitions. [2018-10-14 18:18:35,561 INFO L78 Accepts]: Start accepts. Automaton has 543 states and 544 transitions. Word has length 528 [2018-10-14 18:18:35,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:18:35,562 INFO L481 AbstractCegarLoop]: Abstraction has 543 states and 544 transitions. [2018-10-14 18:18:35,562 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-14 18:18:35,562 INFO L276 IsEmpty]: Start isEmpty. Operand 543 states and 544 transitions. [2018-10-14 18:18:35,565 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 543 [2018-10-14 18:18:35,565 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:18:35,565 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-14 18:18:35,566 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:18:35,566 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:18:35,566 INFO L82 PathProgramCache]: Analyzing trace with hash 2027711539, now seen corresponding path program 33 times [2018-10-14 18:18:35,566 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:18:35,598 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:18:39,125 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-14 18:18:39,126 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:18:39,126 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-14 18:18:39,126 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-14 18:18:39,127 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-14 18:18:39,127 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=690, Invalid=4566, Unknown=0, NotChecked=0, Total=5256 [2018-10-14 18:18:39,127 INFO L87 Difference]: Start difference. First operand 543 states and 544 transitions. Second operand 73 states. [2018-10-14 18:18:43,794 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:18:43,795 INFO L93 Difference]: Finished difference Result 813 states and 814 transitions. [2018-10-14 18:18:43,795 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 107 states. [2018-10-14 18:18:43,795 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 542 [2018-10-14 18:18:43,796 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:18:43,798 INFO L225 Difference]: With dead ends: 813 [2018-10-14 18:18:43,798 INFO L226 Difference]: Without dead ends: 573 [2018-10-14 18:18:43,799 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 158 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6845 ImplicationChecksByTransitivity, 5.7s TimeCoverageRelationStatistics Valid=3852, Invalid=21588, Unknown=0, NotChecked=0, Total=25440 [2018-10-14 18:18:43,800 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 573 states. [2018-10-14 18:18:43,804 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 573 to 559. [2018-10-14 18:18:43,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 559 states. [2018-10-14 18:18:43,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 559 states to 559 states and 560 transitions. [2018-10-14 18:18:43,805 INFO L78 Accepts]: Start accepts. Automaton has 559 states and 560 transitions. Word has length 542 [2018-10-14 18:18:43,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:18:43,806 INFO L481 AbstractCegarLoop]: Abstraction has 559 states and 560 transitions. [2018-10-14 18:18:43,806 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-14 18:18:43,806 INFO L276 IsEmpty]: Start isEmpty. Operand 559 states and 560 transitions. [2018-10-14 18:18:43,809 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 559 [2018-10-14 18:18:43,809 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:18:43,810 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-14 18:18:43,810 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:18:43,810 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:18:43,810 INFO L82 PathProgramCache]: Analyzing trace with hash -1217030591, now seen corresponding path program 34 times [2018-10-14 18:18:43,811 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:18:43,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:18:46,258 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-14 18:18:46,258 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:18:46,258 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-14 18:18:46,259 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-14 18:18:46,259 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-14 18:18:46,260 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=667, Invalid=5185, Unknown=0, NotChecked=0, Total=5852 [2018-10-14 18:18:46,260 INFO L87 Difference]: Start difference. First operand 559 states and 560 transitions. Second operand 77 states. [2018-10-14 18:18:58,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:18:58,403 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-14 18:18:58,403 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-10-14 18:18:58,403 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 558 [2018-10-14 18:18:58,404 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:18:58,405 INFO L225 Difference]: With dead ends: 593 [2018-10-14 18:18:58,405 INFO L226 Difference]: Without dead ends: 593 [2018-10-14 18:18:58,406 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 183 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9152 ImplicationChecksByTransitivity, 9.0s TimeCoverageRelationStatistics Valid=5956, Invalid=28084, Unknown=0, NotChecked=0, Total=34040 [2018-10-14 18:18:58,407 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 593 states. [2018-10-14 18:18:58,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 593 to 573. [2018-10-14 18:18:58,411 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 573 states. [2018-10-14 18:18:58,412 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 573 states to 573 states and 574 transitions. [2018-10-14 18:18:58,412 INFO L78 Accepts]: Start accepts. Automaton has 573 states and 574 transitions. Word has length 558 [2018-10-14 18:18:58,412 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:18:58,412 INFO L481 AbstractCegarLoop]: Abstraction has 573 states and 574 transitions. [2018-10-14 18:18:58,413 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-14 18:18:58,413 INFO L276 IsEmpty]: Start isEmpty. Operand 573 states and 574 transitions. [2018-10-14 18:18:58,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 573 [2018-10-14 18:18:58,416 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:18:58,417 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-14 18:18:58,417 INFO L424 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:18:58,417 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:18:58,417 INFO L82 PathProgramCache]: Analyzing trace with hash 1736053521, now seen corresponding path program 35 times [2018-10-14 18:18:58,418 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:18:58,452 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:19:00,545 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-14 18:19:00,546 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:19:00,546 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-14 18:19:00,546 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-14 18:19:00,547 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-14 18:19:00,547 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=766, Invalid=5086, Unknown=0, NotChecked=0, Total=5852 [2018-10-14 18:19:00,547 INFO L87 Difference]: Start difference. First operand 573 states and 574 transitions. Second operand 77 states. [2018-10-14 18:19:05,613 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:19:05,613 INFO L93 Difference]: Finished difference Result 857 states and 858 transitions. [2018-10-14 18:19:05,614 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 113 states. [2018-10-14 18:19:05,614 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 572 [2018-10-14 18:19:05,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:19:05,616 INFO L225 Difference]: With dead ends: 857 [2018-10-14 18:19:05,616 INFO L226 Difference]: Without dead ends: 603 [2018-10-14 18:19:05,617 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 167 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7671 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=4293, Invalid=24099, Unknown=0, NotChecked=0, Total=28392 [2018-10-14 18:19:05,618 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 603 states. [2018-10-14 18:19:05,621 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 603 to 589. [2018-10-14 18:19:05,622 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 589 states. [2018-10-14 18:19:05,622 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 589 states to 589 states and 590 transitions. [2018-10-14 18:19:05,623 INFO L78 Accepts]: Start accepts. Automaton has 589 states and 590 transitions. Word has length 572 [2018-10-14 18:19:05,623 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:19:05,623 INFO L481 AbstractCegarLoop]: Abstraction has 589 states and 590 transitions. [2018-10-14 18:19:05,623 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-14 18:19:05,623 INFO L276 IsEmpty]: Start isEmpty. Operand 589 states and 590 transitions. [2018-10-14 18:19:05,627 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 589 [2018-10-14 18:19:05,627 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:19:05,628 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-14 18:19:05,628 INFO L424 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:19:05,628 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:19:05,628 INFO L82 PathProgramCache]: Analyzing trace with hash 703115423, now seen corresponding path program 36 times [2018-10-14 18:19:05,629 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:19:05,665 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:19:08,567 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-14 18:19:08,568 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:19:08,568 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-14 18:19:08,568 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-14 18:19:08,569 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-14 18:19:08,569 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=708, Invalid=5772, Unknown=0, NotChecked=0, Total=6480 [2018-10-14 18:19:08,569 INFO L87 Difference]: Start difference. First operand 589 states and 590 transitions. Second operand 81 states. [2018-10-14 18:19:21,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:19:21,971 INFO L93 Difference]: Finished difference Result 623 states and 624 transitions. [2018-10-14 18:19:21,971 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 133 states. [2018-10-14 18:19:21,971 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 588 [2018-10-14 18:19:21,972 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:19:21,973 INFO L225 Difference]: With dead ends: 623 [2018-10-14 18:19:21,973 INFO L226 Difference]: Without dead ends: 623 [2018-10-14 18:19:21,975 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 191 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9935 ImplicationChecksByTransitivity, 10.3s TimeCoverageRelationStatistics Valid=6323, Invalid=30733, Unknown=0, NotChecked=0, Total=37056 [2018-10-14 18:19:21,975 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 623 states. [2018-10-14 18:19:21,979 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 623 to 603. [2018-10-14 18:19:21,980 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 603 states. [2018-10-14 18:19:21,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 603 states to 603 states and 604 transitions. [2018-10-14 18:19:21,981 INFO L78 Accepts]: Start accepts. Automaton has 603 states and 604 transitions. Word has length 588 [2018-10-14 18:19:21,981 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:19:21,981 INFO L481 AbstractCegarLoop]: Abstraction has 603 states and 604 transitions. [2018-10-14 18:19:21,982 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-14 18:19:21,982 INFO L276 IsEmpty]: Start isEmpty. Operand 603 states and 604 transitions. [2018-10-14 18:19:21,985 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 603 [2018-10-14 18:19:21,985 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:19:21,986 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-14 18:19:21,986 INFO L424 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:19:21,986 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:19:21,986 INFO L82 PathProgramCache]: Analyzing trace with hash 1544073455, now seen corresponding path program 37 times [2018-10-14 18:19:21,987 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:19:22,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:19:24,697 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-14 18:19:24,697 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:19:24,697 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-14 18:19:24,698 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-14 18:19:24,698 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-14 18:19:24,698 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=846, Invalid=5634, Unknown=0, NotChecked=0, Total=6480 [2018-10-14 18:19:24,698 INFO L87 Difference]: Start difference. First operand 603 states and 604 transitions. Second operand 81 states. [2018-10-14 18:19:30,496 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:19:30,496 INFO L93 Difference]: Finished difference Result 901 states and 902 transitions. [2018-10-14 18:19:30,496 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 119 states. [2018-10-14 18:19:30,497 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 602 [2018-10-14 18:19:30,497 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:19:30,500 INFO L225 Difference]: With dead ends: 901 [2018-10-14 18:19:30,500 INFO L226 Difference]: Without dead ends: 633 [2018-10-14 18:19:30,501 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 176 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8544 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=4758, Invalid=26748, Unknown=0, NotChecked=0, Total=31506 [2018-10-14 18:19:30,501 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 633 states. [2018-10-14 18:19:30,504 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 633 to 619. [2018-10-14 18:19:30,504 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 619 states. [2018-10-14 18:19:30,505 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 619 states to 619 states and 620 transitions. [2018-10-14 18:19:30,505 INFO L78 Accepts]: Start accepts. Automaton has 619 states and 620 transitions. Word has length 602 [2018-10-14 18:19:30,505 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:19:30,505 INFO L481 AbstractCegarLoop]: Abstraction has 619 states and 620 transitions. [2018-10-14 18:19:30,505 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-14 18:19:30,506 INFO L276 IsEmpty]: Start isEmpty. Operand 619 states and 620 transitions. [2018-10-14 18:19:30,509 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 619 [2018-10-14 18:19:30,509 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:19:30,510 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-14 18:19:30,510 INFO L424 AbstractCegarLoop]: === Iteration 41 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:19:30,510 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:19:30,510 INFO L82 PathProgramCache]: Analyzing trace with hash 98935293, now seen corresponding path program 38 times [2018-10-14 18:19:30,511 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:19:30,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:19:33,791 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-14 18:19:33,791 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:19:33,792 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-14 18:19:33,792 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-14 18:19:33,792 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-14 18:19:33,793 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=751, Invalid=6389, Unknown=0, NotChecked=0, Total=7140 [2018-10-14 18:19:33,793 INFO L87 Difference]: Start difference. First operand 619 states and 620 transitions. Second operand 85 states. [2018-10-14 18:19:48,605 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:19:48,606 INFO L93 Difference]: Finished difference Result 653 states and 654 transitions. [2018-10-14 18:19:48,606 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 139 states. [2018-10-14 18:19:48,606 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 618 [2018-10-14 18:19:48,606 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:19:48,608 INFO L225 Difference]: With dead ends: 653 [2018-10-14 18:19:48,609 INFO L226 Difference]: Without dead ends: 653 [2018-10-14 18:19:48,610 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 206 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 200 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10877 ImplicationChecksByTransitivity, 11.5s TimeCoverageRelationStatistics Valid=6749, Invalid=33853, Unknown=0, NotChecked=0, Total=40602 [2018-10-14 18:19:48,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 653 states. [2018-10-14 18:19:48,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 653 to 633. [2018-10-14 18:19:48,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 633 states. [2018-10-14 18:19:48,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 633 states to 633 states and 634 transitions. [2018-10-14 18:19:48,615 INFO L78 Accepts]: Start accepts. Automaton has 633 states and 634 transitions. Word has length 618 [2018-10-14 18:19:48,615 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:19:48,615 INFO L481 AbstractCegarLoop]: Abstraction has 633 states and 634 transitions. [2018-10-14 18:19:48,615 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-14 18:19:48,615 INFO L276 IsEmpty]: Start isEmpty. Operand 633 states and 634 transitions. [2018-10-14 18:19:48,618 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 633 [2018-10-14 18:19:48,618 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:19:48,619 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-14 18:19:48,619 INFO L424 AbstractCegarLoop]: === Iteration 42 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:19:48,619 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:19:48,619 INFO L82 PathProgramCache]: Analyzing trace with hash 480044493, now seen corresponding path program 39 times [2018-10-14 18:19:48,620 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:19:48,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:19:51,796 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-14 18:19:51,797 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:19:51,797 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-14 18:19:51,797 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-14 18:19:51,797 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-14 18:19:51,798 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=930, Invalid=6210, Unknown=0, NotChecked=0, Total=7140 [2018-10-14 18:19:51,798 INFO L87 Difference]: Start difference. First operand 633 states and 634 transitions. Second operand 85 states. [2018-10-14 18:19:57,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:19:57,999 INFO L93 Difference]: Finished difference Result 945 states and 946 transitions. [2018-10-14 18:19:57,999 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 125 states. [2018-10-14 18:19:57,999 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 632 [2018-10-14 18:19:58,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:19:58,003 INFO L225 Difference]: With dead ends: 945 [2018-10-14 18:19:58,003 INFO L226 Difference]: Without dead ends: 663 [2018-10-14 18:19:58,004 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9464 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=5247, Invalid=29535, Unknown=0, NotChecked=0, Total=34782 [2018-10-14 18:19:58,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 663 states. [2018-10-14 18:19:58,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 663 to 649. [2018-10-14 18:19:58,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 649 states. [2018-10-14 18:19:58,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 649 states to 649 states and 650 transitions. [2018-10-14 18:19:58,009 INFO L78 Accepts]: Start accepts. Automaton has 649 states and 650 transitions. Word has length 632 [2018-10-14 18:19:58,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:19:58,009 INFO L481 AbstractCegarLoop]: Abstraction has 649 states and 650 transitions. [2018-10-14 18:19:58,009 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-14 18:19:58,009 INFO L276 IsEmpty]: Start isEmpty. Operand 649 states and 650 transitions. [2018-10-14 18:19:58,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 649 [2018-10-14 18:19:58,013 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:19:58,013 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-14 18:19:58,014 INFO L424 AbstractCegarLoop]: === Iteration 43 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:19:58,014 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:19:58,014 INFO L82 PathProgramCache]: Analyzing trace with hash 1723402843, now seen corresponding path program 40 times [2018-10-14 18:19:58,015 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:19:58,060 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:20:02,029 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-14 18:20:02,030 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:20:02,030 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-14 18:20:02,031 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-14 18:20:02,031 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-14 18:20:02,031 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=684, Invalid=7148, Unknown=0, NotChecked=0, Total=7832 [2018-10-14 18:20:02,032 INFO L87 Difference]: Start difference. First operand 649 states and 650 transitions. Second operand 89 states. [2018-10-14 18:20:12,827 WARN L179 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 86 DAG size of output: 36 [2018-10-14 18:20:14,067 WARN L179 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-14 18:20:14,256 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-14 18:20:14,733 WARN L179 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-14 18:20:14,914 WARN L179 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-14 18:20:15,346 WARN L179 SmtUtils]: Spent 124.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-14 18:20:15,588 WARN L179 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-14 18:20:16,039 WARN L179 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-14 18:20:16,230 WARN L179 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 43 [2018-10-14 18:20:16,670 WARN L179 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 42 [2018-10-14 18:20:20,081 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:20:20,081 INFO L93 Difference]: Finished difference Result 683 states and 684 transitions. [2018-10-14 18:20:20,081 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 141 states. [2018-10-14 18:20:20,081 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 648 [2018-10-14 18:20:20,082 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:20:20,084 INFO L225 Difference]: With dead ends: 683 [2018-10-14 18:20:20,084 INFO L226 Difference]: Without dead ends: 683 [2018-10-14 18:20:20,085 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 205 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11140 ImplicationChecksByTransitivity, 13.3s TimeCoverageRelationStatistics Valid=6198, Invalid=36444, Unknown=0, NotChecked=0, Total=42642 [2018-10-14 18:20:20,085 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 683 states. [2018-10-14 18:20:20,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 683 to 663. [2018-10-14 18:20:20,089 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 663 states. [2018-10-14 18:20:20,090 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 663 states to 663 states and 664 transitions. [2018-10-14 18:20:20,090 INFO L78 Accepts]: Start accepts. Automaton has 663 states and 664 transitions. Word has length 648 [2018-10-14 18:20:20,090 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:20:20,090 INFO L481 AbstractCegarLoop]: Abstraction has 663 states and 664 transitions. [2018-10-14 18:20:20,090 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-14 18:20:20,090 INFO L276 IsEmpty]: Start isEmpty. Operand 663 states and 664 transitions. [2018-10-14 18:20:20,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 663 [2018-10-14 18:20:20,094 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:20:20,094 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-14 18:20:20,094 INFO L424 AbstractCegarLoop]: === Iteration 44 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:20:20,094 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:20:20,095 INFO L82 PathProgramCache]: Analyzing trace with hash 837505451, now seen corresponding path program 41 times [2018-10-14 18:20:20,095 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:20:20,138 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:20:23,130 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-14 18:20:23,131 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:20:23,131 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-14 18:20:23,132 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-14 18:20:23,132 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-14 18:20:23,132 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1018, Invalid=6814, Unknown=0, NotChecked=0, Total=7832 [2018-10-14 18:20:23,133 INFO L87 Difference]: Start difference. First operand 663 states and 664 transitions. Second operand 89 states. [2018-10-14 18:20:29,568 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:20:29,568 INFO L93 Difference]: Finished difference Result 989 states and 990 transitions. [2018-10-14 18:20:29,568 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-10-14 18:20:29,569 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 662 [2018-10-14 18:20:29,570 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:20:29,571 INFO L225 Difference]: With dead ends: 989 [2018-10-14 18:20:29,572 INFO L226 Difference]: Without dead ends: 693 [2018-10-14 18:20:29,573 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 194 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10431 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=5760, Invalid=32460, Unknown=0, NotChecked=0, Total=38220 [2018-10-14 18:20:29,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 693 states. [2018-10-14 18:20:29,577 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 693 to 679. [2018-10-14 18:20:29,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 679 states. [2018-10-14 18:20:29,578 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 679 states to 679 states and 680 transitions. [2018-10-14 18:20:29,578 INFO L78 Accepts]: Start accepts. Automaton has 679 states and 680 transitions. Word has length 662 [2018-10-14 18:20:29,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:20:29,578 INFO L481 AbstractCegarLoop]: Abstraction has 679 states and 680 transitions. [2018-10-14 18:20:29,579 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-14 18:20:29,579 INFO L276 IsEmpty]: Start isEmpty. Operand 679 states and 680 transitions. [2018-10-14 18:20:29,581 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 679 [2018-10-14 18:20:29,582 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:20:29,582 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-14 18:20:29,582 INFO L424 AbstractCegarLoop]: === Iteration 45 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:20:29,582 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:20:29,582 INFO L82 PathProgramCache]: Analyzing trace with hash 944736697, now seen corresponding path program 42 times [2018-10-14 18:20:29,583 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:20:29,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:20:33,404 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-14 18:20:33,404 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:20:33,405 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-14 18:20:33,405 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-14 18:20:33,406 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-14 18:20:33,406 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=987, Invalid=7569, Unknown=0, NotChecked=0, Total=8556 [2018-10-14 18:20:33,406 INFO L87 Difference]: Start difference. First operand 679 states and 680 transitions. Second operand 93 states. [2018-10-14 18:20:46,114 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:20:46,114 INFO L93 Difference]: Finished difference Result 713 states and 714 transitions. [2018-10-14 18:20:46,114 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 156 states. [2018-10-14 18:20:46,115 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 678 [2018-10-14 18:20:46,115 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:20:46,117 INFO L225 Difference]: With dead ends: 713 [2018-10-14 18:20:46,117 INFO L226 Difference]: Without dead ends: 713 [2018-10-14 18:20:46,118 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 223 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13786 ImplicationChecksByTransitivity, 13.0s TimeCoverageRelationStatistics Valid=8814, Invalid=41586, Unknown=0, NotChecked=0, Total=50400 [2018-10-14 18:20:46,119 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 713 states. [2018-10-14 18:20:46,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 713 to 693. [2018-10-14 18:20:46,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 693 states. [2018-10-14 18:20:46,123 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 693 states to 693 states and 694 transitions. [2018-10-14 18:20:46,123 INFO L78 Accepts]: Start accepts. Automaton has 693 states and 694 transitions. Word has length 678 [2018-10-14 18:20:46,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:20:46,123 INFO L481 AbstractCegarLoop]: Abstraction has 693 states and 694 transitions. [2018-10-14 18:20:46,124 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-14 18:20:46,124 INFO L276 IsEmpty]: Start isEmpty. Operand 693 states and 694 transitions. [2018-10-14 18:20:46,127 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 693 [2018-10-14 18:20:46,127 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:20:46,127 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-14 18:20:46,127 INFO L424 AbstractCegarLoop]: === Iteration 46 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:20:46,127 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:20:46,127 INFO L82 PathProgramCache]: Analyzing trace with hash 1565037705, now seen corresponding path program 43 times [2018-10-14 18:20:46,128 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:20:46,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:20:49,103 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-14 18:20:49,103 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:20:49,104 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-14 18:20:49,104 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-14 18:20:49,104 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-14 18:20:49,105 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1110, Invalid=7446, Unknown=0, NotChecked=0, Total=8556 [2018-10-14 18:20:49,105 INFO L87 Difference]: Start difference. First operand 693 states and 694 transitions. Second operand 93 states. [2018-10-14 18:20:56,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:20:56,615 INFO L93 Difference]: Finished difference Result 1033 states and 1034 transitions. [2018-10-14 18:20:56,616 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 137 states. [2018-10-14 18:20:56,616 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 692 [2018-10-14 18:20:56,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:20:56,619 INFO L225 Difference]: With dead ends: 1033 [2018-10-14 18:20:56,619 INFO L226 Difference]: Without dead ends: 723 [2018-10-14 18:20:56,621 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11445 ImplicationChecksByTransitivity, 6.4s TimeCoverageRelationStatistics Valid=6297, Invalid=35523, Unknown=0, NotChecked=0, Total=41820 [2018-10-14 18:20:56,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 723 states. [2018-10-14 18:20:56,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 723 to 709. [2018-10-14 18:20:56,625 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-10-14 18:20:56,626 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 710 transitions. [2018-10-14 18:20:56,626 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 710 transitions. Word has length 692 [2018-10-14 18:20:56,626 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:20:56,626 INFO L481 AbstractCegarLoop]: Abstraction has 709 states and 710 transitions. [2018-10-14 18:20:56,626 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-14 18:20:56,626 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 710 transitions. [2018-10-14 18:20:56,629 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 709 [2018-10-14 18:20:56,629 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:20:56,629 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-14 18:20:56,629 INFO L424 AbstractCegarLoop]: === Iteration 47 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:20:56,630 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:20:56,630 INFO L82 PathProgramCache]: Analyzing trace with hash 758497303, now seen corresponding path program 44 times [2018-10-14 18:20:56,630 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:20:56,669 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:21:00,558 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-14 18:21:00,559 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:21:00,559 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-14 18:21:00,559 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-14 18:21:00,560 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-14 18:21:00,560 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1036, Invalid=8276, Unknown=0, NotChecked=0, Total=9312 [2018-10-14 18:21:00,560 INFO L87 Difference]: Start difference. First operand 709 states and 710 transitions. Second operand 97 states. [2018-10-14 18:21:19,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:21:19,432 INFO L93 Difference]: Finished difference Result 743 states and 744 transitions. [2018-10-14 18:21:19,433 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-14 18:21:19,433 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 708 [2018-10-14 18:21:19,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:21:19,435 INFO L225 Difference]: With dead ends: 743 [2018-10-14 18:21:19,435 INFO L226 Difference]: Without dead ends: 743 [2018-10-14 18:21:19,436 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 231 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14741 ImplicationChecksByTransitivity, 14.0s TimeCoverageRelationStatistics Valid=9261, Invalid=44795, Unknown=0, NotChecked=0, Total=54056 [2018-10-14 18:21:19,437 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 743 states. [2018-10-14 18:21:19,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 743 to 723. [2018-10-14 18:21:19,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 723 states. [2018-10-14 18:21:19,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 723 states to 723 states and 724 transitions. [2018-10-14 18:21:19,441 INFO L78 Accepts]: Start accepts. Automaton has 723 states and 724 transitions. Word has length 708 [2018-10-14 18:21:19,442 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:21:19,442 INFO L481 AbstractCegarLoop]: Abstraction has 723 states and 724 transitions. [2018-10-14 18:21:19,442 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-14 18:21:19,442 INFO L276 IsEmpty]: Start isEmpty. Operand 723 states and 724 transitions. [2018-10-14 18:21:19,445 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 723 [2018-10-14 18:21:19,445 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:21:19,446 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-14 18:21:19,446 INFO L424 AbstractCegarLoop]: === Iteration 48 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:21:19,446 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:21:19,446 INFO L82 PathProgramCache]: Analyzing trace with hash 245976679, now seen corresponding path program 45 times [2018-10-14 18:21:19,447 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:21:19,490 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:21:22,878 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-14 18:21:22,879 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:21:22,879 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-14 18:21:22,879 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-14 18:21:22,880 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-14 18:21:22,880 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1206, Invalid=8106, Unknown=0, NotChecked=0, Total=9312 [2018-10-14 18:21:22,880 INFO L87 Difference]: Start difference. First operand 723 states and 724 transitions. Second operand 97 states. [2018-10-14 18:21:31,005 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:21:31,005 INFO L93 Difference]: Finished difference Result 1077 states and 1078 transitions. [2018-10-14 18:21:31,005 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 143 states. [2018-10-14 18:21:31,006 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 722 [2018-10-14 18:21:31,006 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:21:31,008 INFO L225 Difference]: With dead ends: 1077 [2018-10-14 18:21:31,008 INFO L226 Difference]: Without dead ends: 753 [2018-10-14 18:21:31,010 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-14 18:21:31,010 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 753 states. [2018-10-14 18:21:31,014 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 753 to 739. [2018-10-14 18:21:31,014 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-10-14 18:21:31,015 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 740 transitions. [2018-10-14 18:21:31,015 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 740 transitions. Word has length 722 [2018-10-14 18:21:31,015 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:21:31,016 INFO L481 AbstractCegarLoop]: Abstraction has 739 states and 740 transitions. [2018-10-14 18:21:31,016 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-14 18:21:31,016 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 740 transitions. [2018-10-14 18:21:31,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 739 [2018-10-14 18:21:31,019 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:21:31,019 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-14 18:21:31,020 INFO L424 AbstractCegarLoop]: === Iteration 49 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:21:31,020 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:21:31,020 INFO L82 PathProgramCache]: Analyzing trace with hash -1265087115, now seen corresponding path program 46 times [2018-10-14 18:21:31,020 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:21:31,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:21:35,557 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-14 18:21:35,557 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:21:35,557 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-14 18:21:35,558 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-14 18:21:35,558 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-14 18:21:35,559 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1087, Invalid=9013, Unknown=0, NotChecked=0, Total=10100 [2018-10-14 18:21:35,559 INFO L87 Difference]: Start difference. First operand 739 states and 740 transitions. Second operand 101 states. [2018-10-14 18:21:51,278 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:21:51,278 INFO L93 Difference]: Finished difference Result 773 states and 774 transitions. [2018-10-14 18:21:51,278 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-14 18:21:51,278 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 738 [2018-10-14 18:21:51,279 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:21:51,281 INFO L225 Difference]: With dead ends: 773 [2018-10-14 18:21:51,281 INFO L226 Difference]: Without dead ends: 773 [2018-10-14 18:21:51,283 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 240 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15883 ImplicationChecksByTransitivity, 15.7s TimeCoverageRelationStatistics Valid=9775, Invalid=48547, Unknown=0, NotChecked=0, Total=58322 [2018-10-14 18:21:51,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 773 states. [2018-10-14 18:21:51,287 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 773 to 753. [2018-10-14 18:21:51,287 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 753 states. [2018-10-14 18:21:51,288 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 753 states to 753 states and 754 transitions. [2018-10-14 18:21:51,288 INFO L78 Accepts]: Start accepts. Automaton has 753 states and 754 transitions. Word has length 738 [2018-10-14 18:21:51,289 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:21:51,289 INFO L481 AbstractCegarLoop]: Abstraction has 753 states and 754 transitions. [2018-10-14 18:21:51,289 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-14 18:21:51,289 INFO L276 IsEmpty]: Start isEmpty. Operand 753 states and 754 transitions. [2018-10-14 18:21:51,293 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 753 [2018-10-14 18:21:51,293 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:21:51,293 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-14 18:21:51,294 INFO L424 AbstractCegarLoop]: === Iteration 50 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:21:51,294 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:21:51,294 INFO L82 PathProgramCache]: Analyzing trace with hash -626909371, now seen corresponding path program 47 times [2018-10-14 18:21:51,294 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:21:51,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:21:54,891 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-14 18:21:54,892 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:21:54,892 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-14 18:21:54,893 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-14 18:21:54,893 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-14 18:21:54,893 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1306, Invalid=8794, Unknown=0, NotChecked=0, Total=10100 [2018-10-14 18:21:54,893 INFO L87 Difference]: Start difference. First operand 753 states and 754 transitions. Second operand 101 states. [2018-10-14 18:22:03,652 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:22:03,653 INFO L93 Difference]: Finished difference Result 1121 states and 1122 transitions. [2018-10-14 18:22:03,653 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 149 states. [2018-10-14 18:22:03,653 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 752 [2018-10-14 18:22:03,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:22:03,656 INFO L225 Difference]: With dead ends: 1121 [2018-10-14 18:22:03,656 INFO L226 Difference]: Without dead ends: 783 [2018-10-14 18:22:03,658 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 221 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13614 ImplicationChecksByTransitivity, 7.5s TimeCoverageRelationStatistics Valid=7443, Invalid=42063, Unknown=0, NotChecked=0, Total=49506 [2018-10-14 18:22:03,658 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 783 states. [2018-10-14 18:22:03,663 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 783 to 769. [2018-10-14 18:22:03,663 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 769 states. [2018-10-14 18:22:03,665 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 769 states to 769 states and 770 transitions. [2018-10-14 18:22:03,665 INFO L78 Accepts]: Start accepts. Automaton has 769 states and 770 transitions. Word has length 752 [2018-10-14 18:22:03,665 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:22:03,665 INFO L481 AbstractCegarLoop]: Abstraction has 769 states and 770 transitions. [2018-10-14 18:22:03,665 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-14 18:22:03,666 INFO L276 IsEmpty]: Start isEmpty. Operand 769 states and 770 transitions. [2018-10-14 18:22:03,670 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 769 [2018-10-14 18:22:03,670 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:22:03,671 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-14 18:22:03,671 INFO L424 AbstractCegarLoop]: === Iteration 51 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:22:03,671 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:22:03,671 INFO L82 PathProgramCache]: Analyzing trace with hash -263990829, now seen corresponding path program 48 times [2018-10-14 18:22:03,672 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:22:03,717 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:22:08,061 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-14 18:22:08,062 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:22:08,062 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-14 18:22:08,062 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-14 18:22:08,063 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-14 18:22:08,063 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1140, Invalid=9780, Unknown=0, NotChecked=0, Total=10920 [2018-10-14 18:22:08,063 INFO L87 Difference]: Start difference. First operand 769 states and 770 transitions. Second operand 105 states. [2018-10-14 18:22:30,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:22:30,661 INFO L93 Difference]: Finished difference Result 803 states and 804 transitions. [2018-10-14 18:22:30,662 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 173 states. [2018-10-14 18:22:30,662 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 768 [2018-10-14 18:22:30,663 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:22:30,665 INFO L225 Difference]: With dead ends: 803 [2018-10-14 18:22:30,665 INFO L226 Difference]: Without dead ends: 803 [2018-10-14 18:22:30,666 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 255 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 249 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17066 ImplicationChecksByTransitivity, 16.8s TimeCoverageRelationStatistics Valid=10304, Invalid=52446, Unknown=0, NotChecked=0, Total=62750 [2018-10-14 18:22:30,667 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 803 states. [2018-10-14 18:22:30,671 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 803 to 783. [2018-10-14 18:22:30,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 783 states. [2018-10-14 18:22:30,672 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 783 states to 783 states and 784 transitions. [2018-10-14 18:22:30,672 INFO L78 Accepts]: Start accepts. Automaton has 783 states and 784 transitions. Word has length 768 [2018-10-14 18:22:30,672 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:22:30,672 INFO L481 AbstractCegarLoop]: Abstraction has 783 states and 784 transitions. [2018-10-14 18:22:30,672 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-14 18:22:30,672 INFO L276 IsEmpty]: Start isEmpty. Operand 783 states and 784 transitions. [2018-10-14 18:22:30,676 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 783 [2018-10-14 18:22:30,677 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:22:30,677 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-14 18:22:30,677 INFO L424 AbstractCegarLoop]: === Iteration 52 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:22:30,677 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:22:30,677 INFO L82 PathProgramCache]: Analyzing trace with hash -261642461, now seen corresponding path program 49 times [2018-10-14 18:22:30,678 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:22:30,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:22:34,317 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-14 18:22:34,317 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:22:34,317 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-14 18:22:34,318 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-14 18:22:34,318 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-14 18:22:34,319 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1410, Invalid=9510, Unknown=0, NotChecked=0, Total=10920 [2018-10-14 18:22:34,319 INFO L87 Difference]: Start difference. First operand 783 states and 784 transitions. Second operand 105 states. [2018-10-14 18:22:43,591 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:22:43,591 INFO L93 Difference]: Finished difference Result 1165 states and 1166 transitions. [2018-10-14 18:22:43,591 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 155 states. [2018-10-14 18:22:43,592 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 782 [2018-10-14 18:22:43,592 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:22:43,595 INFO L225 Difference]: With dead ends: 1165 [2018-10-14 18:22:43,595 INFO L226 Difference]: Without dead ends: 813 [2018-10-14 18:22:43,597 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-14 18:22:43,597 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 813 states. [2018-10-14 18:22:43,602 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 813 to 799. [2018-10-14 18:22:43,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 799 states. [2018-10-14 18:22:43,602 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 799 states to 799 states and 800 transitions. [2018-10-14 18:22:43,603 INFO L78 Accepts]: Start accepts. Automaton has 799 states and 800 transitions. Word has length 782 [2018-10-14 18:22:43,603 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:22:43,603 INFO L481 AbstractCegarLoop]: Abstraction has 799 states and 800 transitions. [2018-10-14 18:22:43,603 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-14 18:22:43,603 INFO L276 IsEmpty]: Start isEmpty. Operand 799 states and 800 transitions. [2018-10-14 18:22:43,607 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 799 [2018-10-14 18:22:43,607 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:22:43,607 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-14 18:22:43,608 INFO L424 AbstractCegarLoop]: === Iteration 53 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:22:43,608 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:22:43,608 INFO L82 PathProgramCache]: Analyzing trace with hash -1432031951, now seen corresponding path program 50 times [2018-10-14 18:22:43,609 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:22:43,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:22:48,338 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-14 18:22:48,338 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:22:48,339 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-14 18:22:48,339 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-14 18:22:48,339 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-14 18:22:48,340 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1371, Invalid=10401, Unknown=0, NotChecked=0, Total=11772 [2018-10-14 18:22:48,340 INFO L87 Difference]: Start difference. First operand 799 states and 800 transitions. Second operand 109 states. [2018-10-14 18:23:06,690 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:23:06,690 INFO L93 Difference]: Finished difference Result 833 states and 834 transitions. [2018-10-14 18:23:06,691 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 184 states. [2018-10-14 18:23:06,691 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 798 [2018-10-14 18:23:06,691 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:23:06,693 INFO L225 Difference]: With dead ends: 833 [2018-10-14 18:23:06,693 INFO L226 Difference]: Without dead ends: 833 [2018-10-14 18:23:06,695 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 269 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 263 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19364 ImplicationChecksByTransitivity, 16.8s TimeCoverageRelationStatistics Valid=12232, Invalid=57728, Unknown=0, NotChecked=0, Total=69960 [2018-10-14 18:23:06,695 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 833 states. [2018-10-14 18:23:06,699 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 833 to 813. [2018-10-14 18:23:06,699 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 813 states. [2018-10-14 18:23:06,700 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 813 states to 813 states and 814 transitions. [2018-10-14 18:23:06,700 INFO L78 Accepts]: Start accepts. Automaton has 813 states and 814 transitions. Word has length 798 [2018-10-14 18:23:06,701 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:23:06,701 INFO L481 AbstractCegarLoop]: Abstraction has 813 states and 814 transitions. [2018-10-14 18:23:06,701 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-14 18:23:06,701 INFO L276 IsEmpty]: Start isEmpty. Operand 813 states and 814 transitions. [2018-10-14 18:23:06,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 813 [2018-10-14 18:23:06,705 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:23:06,705 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-14 18:23:06,705 INFO L424 AbstractCegarLoop]: === Iteration 54 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:23:06,706 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:23:06,706 INFO L82 PathProgramCache]: Analyzing trace with hash -1882290687, now seen corresponding path program 51 times [2018-10-14 18:23:06,706 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:23:06,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:23:10,665 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-14 18:23:10,666 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:23:10,666 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-14 18:23:10,666 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-14 18:23:10,667 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-14 18:23:10,667 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1518, Invalid=10254, Unknown=0, NotChecked=0, Total=11772 [2018-10-14 18:23:10,667 INFO L87 Difference]: Start difference. First operand 813 states and 814 transitions. Second operand 109 states. [2018-10-14 18:23:21,034 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:23:21,034 INFO L93 Difference]: Finished difference Result 1209 states and 1210 transitions. [2018-10-14 18:23:21,034 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-14 18:23:21,035 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 812 [2018-10-14 18:23:21,035 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:23:21,037 INFO L225 Difference]: With dead ends: 1209 [2018-10-14 18:23:21,037 INFO L226 Difference]: Without dead ends: 843 [2018-10-14 18:23:21,040 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 239 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15971 ImplicationChecksByTransitivity, 8.6s TimeCoverageRelationStatistics Valid=8685, Invalid=49155, Unknown=0, NotChecked=0, Total=57840 [2018-10-14 18:23:21,040 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 843 states. [2018-10-14 18:23:21,044 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 843 to 829. [2018-10-14 18:23:21,044 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 829 states. [2018-10-14 18:23:21,045 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 829 states to 829 states and 830 transitions. [2018-10-14 18:23:21,045 INFO L78 Accepts]: Start accepts. Automaton has 829 states and 830 transitions. Word has length 812 [2018-10-14 18:23:21,045 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:23:21,045 INFO L481 AbstractCegarLoop]: Abstraction has 829 states and 830 transitions. [2018-10-14 18:23:21,045 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-14 18:23:21,045 INFO L276 IsEmpty]: Start isEmpty. Operand 829 states and 830 transitions. [2018-10-14 18:23:21,049 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 829 [2018-10-14 18:23:21,050 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:23:21,050 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-14 18:23:21,050 INFO L424 AbstractCegarLoop]: === Iteration 55 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:23:21,050 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:23:21,050 INFO L82 PathProgramCache]: Analyzing trace with hash 1288191887, now seen corresponding path program 52 times [2018-10-14 18:23:21,051 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:23:21,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:23:26,240 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-14 18:23:26,240 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:23:26,240 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-14 18:23:26,241 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-14 18:23:26,241 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-14 18:23:26,242 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1428, Invalid=11228, Unknown=0, NotChecked=0, Total=12656 [2018-10-14 18:23:26,242 INFO L87 Difference]: Start difference. First operand 829 states and 830 transitions. Second operand 113 states. [2018-10-14 18:23:50,931 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:23:50,932 INFO L93 Difference]: Finished difference Result 863 states and 864 transitions. [2018-10-14 18:23:50,932 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-10-14 18:23:50,932 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 828 [2018-10-14 18:23:50,933 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:23:50,935 INFO L225 Difference]: With dead ends: 863 [2018-10-14 18:23:50,935 INFO L226 Difference]: Without dead ends: 863 [2018-10-14 18:23:50,937 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 277 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 271 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20491 ImplicationChecksByTransitivity, 18.4s TimeCoverageRelationStatistics Valid=12759, Invalid=61497, Unknown=0, NotChecked=0, Total=74256 [2018-10-14 18:23:50,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 863 states. [2018-10-14 18:23:50,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 863 to 843. [2018-10-14 18:23:50,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 843 states. [2018-10-14 18:23:50,942 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 843 states to 843 states and 844 transitions. [2018-10-14 18:23:50,943 INFO L78 Accepts]: Start accepts. Automaton has 843 states and 844 transitions. Word has length 828 [2018-10-14 18:23:50,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:23:50,943 INFO L481 AbstractCegarLoop]: Abstraction has 843 states and 844 transitions. [2018-10-14 18:23:50,943 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-14 18:23:50,943 INFO L276 IsEmpty]: Start isEmpty. Operand 843 states and 844 transitions. [2018-10-14 18:23:50,947 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 843 [2018-10-14 18:23:50,947 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:23:50,948 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-14 18:23:50,948 INFO L424 AbstractCegarLoop]: === Iteration 56 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:23:50,948 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:23:50,948 INFO L82 PathProgramCache]: Analyzing trace with hash 2135645151, now seen corresponding path program 53 times [2018-10-14 18:23:50,949 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:23:50,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:23:54,963 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-14 18:23:54,964 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:23:54,964 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-14 18:23:54,965 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-14 18:23:54,965 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-14 18:23:54,965 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1630, Invalid=11026, Unknown=0, NotChecked=0, Total=12656 [2018-10-14 18:23:54,966 INFO L87 Difference]: Start difference. First operand 843 states and 844 transitions. Second operand 113 states. [2018-10-14 18:24:06,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 18:24:06,176 INFO L93 Difference]: Finished difference Result 1253 states and 1254 transitions. [2018-10-14 18:24:06,176 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-14 18:24:06,176 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 842 [2018-10-14 18:24:06,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 18:24:06,179 INFO L225 Difference]: With dead ends: 1253 [2018-10-14 18:24:06,179 INFO L226 Difference]: Without dead ends: 873 [2018-10-14 18:24:06,180 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 248 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17220 ImplicationChecksByTransitivity, 9.2s TimeCoverageRelationStatistics Valid=9342, Invalid=52908, Unknown=0, NotChecked=0, Total=62250 [2018-10-14 18:24:06,181 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 873 states. [2018-10-14 18:24:06,185 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 873 to 859. [2018-10-14 18:24:06,185 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 859 states. [2018-10-14 18:24:06,186 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 859 states to 859 states and 860 transitions. [2018-10-14 18:24:06,186 INFO L78 Accepts]: Start accepts. Automaton has 859 states and 860 transitions. Word has length 842 [2018-10-14 18:24:06,186 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 18:24:06,186 INFO L481 AbstractCegarLoop]: Abstraction has 859 states and 860 transitions. [2018-10-14 18:24:06,186 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-14 18:24:06,186 INFO L276 IsEmpty]: Start isEmpty. Operand 859 states and 860 transitions. [2018-10-14 18:24:06,191 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 859 [2018-10-14 18:24:06,191 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 18:24:06,191 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-14 18:24:06,191 INFO L424 AbstractCegarLoop]: === Iteration 57 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 18:24:06,191 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 18:24:06,192 INFO L82 PathProgramCache]: Analyzing trace with hash -732272403, now seen corresponding path program 54 times [2018-10-14 18:24:06,192 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 18:24:06,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 18:24:11,440 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-14 18:24:11,441 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 18:24:11,441 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [117] total 117 [2018-10-14 18:24:11,442 INFO L460 AbstractCegarLoop]: Interpolant automaton has 117 states [2018-10-14 18:24:11,442 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 117 interpolants. [2018-10-14 18:24:11,442 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1487, Invalid=12085, Unknown=0, NotChecked=0, Total=13572 [2018-10-14 18:24:11,442 INFO L87 Difference]: Start difference. First operand 859 states and 860 transitions. Second operand 117 states.