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-502d2f4 [2018-10-12 22:38:31,881 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-12 22:38:31,883 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-12 22:38:31,895 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-12 22:38:31,895 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-12 22:38:31,896 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-12 22:38:31,898 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-12 22:38:31,899 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-12 22:38:31,901 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-12 22:38:31,903 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-12 22:38:31,904 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-12 22:38:31,904 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-12 22:38:31,905 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-12 22:38:31,906 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-12 22:38:31,907 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-12 22:38:31,908 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-12 22:38:31,908 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-12 22:38:31,910 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-12 22:38:31,912 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-12 22:38:31,915 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-12 22:38:31,916 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-12 22:38:31,921 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-12 22:38:31,923 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-12 22:38:31,923 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-12 22:38:31,924 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-12 22:38:31,925 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-12 22:38:31,927 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-12 22:38:31,928 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-12 22:38:31,931 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-12 22:38:31,932 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-12 22:38:31,933 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-12 22:38:31,933 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-12 22:38:31,933 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-12 22:38:31,934 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-12 22:38:31,935 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-12 22:38:31,938 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-12 22:38:31,938 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-12 22:38:31,954 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-12 22:38:31,954 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-12 22:38:31,955 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-12 22:38:31,955 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-12 22:38:31,956 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-12 22:38:31,956 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-12 22:38:31,957 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-12 22:38:31,957 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-12 22:38:31,958 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-12 22:38:31,958 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-12 22:38:31,958 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-12 22:38:31,958 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-12 22:38:31,958 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-12 22:38:31,959 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-12 22:38:31,959 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-12 22:38:32,027 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-12 22:38:32,039 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-12 22:38:32,043 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-12 22:38:32,046 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-12 22:38:32,047 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-12 22:38:32,048 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-12 22:38:32,048 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-12 22:38:32,128 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-12 22:38:32,130 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-10-12 22:38:32,130 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-12 22:38:32,131 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-12 22:38:32,131 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-12 22:38:32,158 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 12.10 10:38:32" (1/1) ... [2018-10-12 22:38:32,160 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 12.10 10:38:32" (1/1) ... [2018-10-12 22:38:32,175 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 12.10 10:38:32" (1/1) ... [2018-10-12 22:38:32,176 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 12.10 10:38:32" (1/1) ... [2018-10-12 22:38:32,182 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 12.10 10:38:32" (1/1) ... [2018-10-12 22:38:32,184 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 12.10 10:38:32" (1/1) ... [2018-10-12 22:38:32,185 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 12.10 10:38:32" (1/1) ... [2018-10-12 22:38:32,187 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-12 22:38:32,188 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-12 22:38:32,189 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-12 22:38:32,189 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-12 22:38:32,190 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 12.10 10:38:32" (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-12 22:38:32,253 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2018-10-12 22:38:32,254 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-12 22:38:32,254 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-12 22:38:32,753 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-12 22:38:32,754 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 12.10 10:38:32 BoogieIcfgContainer [2018-10-12 22:38:32,754 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-12 22:38:32,755 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-10-12 22:38:32,755 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-10-12 22:38:32,756 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-10-12 22:38:32,759 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 12.10 10:38:32" (1/1) ... [2018-10-12 22:38:32,766 INFO L137 apSepIcfgTransformer]: HeapSepIcfgTransformer: Starting heap partitioning [2018-10-12 22:38:32,767 INFO L138 apSepIcfgTransformer]: To be partitioned heap arrays found [#memory_int] [2018-10-12 22:38:32,803 INFO L191 apSepIcfgTransformer]: Heap separator: starting loc-array-style preprocessing [2018-10-12 22:38:32,847 INFO L219 apSepIcfgTransformer]: finished MemlocArrayUpdater [2018-10-12 22:38:32,862 INFO L282 apSepIcfgTransformer]: finished preprocessing for the equality analysis [2018-10-12 22:38:32,930 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=1) [2018-10-12 22:38:37,441 INFO L315 AbstractInterpreter]: Visited 61 different actions 173 times. Merged at 34 different actions 105 times. Widened at 3 different actions 5 times. Found 4 fixpoints after 3 different actions. Largest state had 0 variables. [2018-10-12 22:38:37,444 INFO L306 apSepIcfgTransformer]: finished equality analysis [2018-10-12 22:38:37,448 INFO L318 apSepIcfgTransformer]: Finished detection of select terms ("array reads") [2018-10-12 22:38:37,465 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-12 22:38:37,520 INFO L232 HeapPartitionManager]: partitioning result: [2018-10-12 22:38:37,521 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-12 22:38:37,521 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-12 22:38:37,521 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 2 [2018-10-12 22:38:37,521 INFO L248 HeapPartitionManager]: # location blocks :2 [2018-10-12 22:38:37,522 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-12 22:38:37,522 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-12 22:38:37,522 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-12 22:38:37,522 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-12 22:38:37,522 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-12 22:38:37,523 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 2 [2018-10-12 22:38:37,523 INFO L248 HeapPartitionManager]: # location blocks :2 [2018-10-12 22:38:37,523 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-12 22:38:37,523 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-12 22:38:37,523 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-12 22:38:37,525 INFO L145 ransitionTransformer]: executing heap partitioning transformation [2018-10-12 22:38:37,543 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 12.10 10:38:37 BasicIcfg [2018-10-12 22:38:37,543 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-10-12 22:38:37,544 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-12 22:38:37,544 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-12 22:38:37,548 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-12 22:38:37,548 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 12.10 10:38:32" (1/3) ... [2018-10-12 22:38:37,549 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4d816dc9 and model type count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 10:38:37, skipping insertion in model container [2018-10-12 22:38:37,549 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 12.10 10:38:32" (2/3) ... [2018-10-12 22:38:37,550 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4d816dc9 and model type count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 12.10 10:38:37, skipping insertion in model container [2018-10-12 22:38:37,550 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 12.10 10:38:37" (3/3) ... [2018-10-12 22:38:37,551 INFO L112 eAbstractionObserver]: Analyzing ICFG memPartitionedIcfg [2018-10-12 22:38:37,561 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-12 22:38:37,569 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-12 22:38:37,586 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-12 22:38:37,612 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-12 22:38:37,613 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-12 22:38:37,613 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-12 22:38:37,613 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-12 22:38:37,613 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-12 22:38:37,613 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-12 22:38:37,614 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-12 22:38:37,614 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-12 22:38:37,614 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-12 22:38:37,628 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states. [2018-10-12 22:38:37,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-10-12 22:38:37,635 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:37,636 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-12 22:38:37,637 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:37,643 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:37,643 INFO L82 PathProgramCache]: Analyzing trace with hash 964056693, now seen corresponding path program 1 times [2018-10-12 22:38:37,709 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:37,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:38,018 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-12 22:38:38,020 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-12 22:38:38,021 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-12 22:38:38,025 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-12 22:38:38,039 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-12 22:38:38,040 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-12 22:38:38,043 INFO L87 Difference]: Start difference. First operand 60 states. Second operand 4 states. [2018-10-12 22:38:38,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:38,125 INFO L93 Difference]: Finished difference Result 73 states and 74 transitions. [2018-10-12 22:38:38,126 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-12 22:38:38,128 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 32 [2018-10-12 22:38:38,128 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:38,205 INFO L225 Difference]: With dead ends: 73 [2018-10-12 22:38:38,206 INFO L226 Difference]: Without dead ends: 73 [2018-10-12 22:38:38,208 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-12 22:38:38,227 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2018-10-12 22:38:38,249 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 59. [2018-10-12 22:38:38,250 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2018-10-12 22:38:38,251 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 60 transitions. [2018-10-12 22:38:38,254 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 60 transitions. Word has length 32 [2018-10-12 22:38:38,255 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:38,255 INFO L481 AbstractCegarLoop]: Abstraction has 59 states and 60 transitions. [2018-10-12 22:38:38,255 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-12 22:38:38,255 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 60 transitions. [2018-10-12 22:38:38,258 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2018-10-12 22:38:38,258 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:38,258 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-12 22:38:38,259 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:38,259 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:38,259 INFO L82 PathProgramCache]: Analyzing trace with hash 575190275, now seen corresponding path program 1 times [2018-10-12 22:38:38,261 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:38,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:38,675 WARN L178 SmtUtils]: Spent 156.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 17 [2018-10-12 22:38:39,152 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-12 22:38:39,152 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:39,153 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-10-12 22:38:39,154 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-12 22:38:39,155 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-12 22:38:39,155 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2018-10-12 22:38:39,155 INFO L87 Difference]: Start difference. First operand 59 states and 60 transitions. Second operand 12 states. [2018-10-12 22:38:40,122 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 28 [2018-10-12 22:38:40,321 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:40,321 INFO L93 Difference]: Finished difference Result 121 states and 123 transitions. [2018-10-12 22:38:40,322 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-12 22:38:40,322 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 48 [2018-10-12 22:38:40,323 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:40,324 INFO L225 Difference]: With dead ends: 121 [2018-10-12 22:38:40,325 INFO L226 Difference]: Without dead ends: 121 [2018-10-12 22:38:40,326 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2018-10-12 22:38:40,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2018-10-12 22:38:40,333 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 80. [2018-10-12 22:38:40,334 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-10-12 22:38:40,335 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 82 transitions. [2018-10-12 22:38:40,335 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 82 transitions. Word has length 48 [2018-10-12 22:38:40,336 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:40,336 INFO L481 AbstractCegarLoop]: Abstraction has 80 states and 82 transitions. [2018-10-12 22:38:40,336 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-12 22:38:40,336 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 82 transitions. [2018-10-12 22:38:40,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-10-12 22:38:40,338 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:40,338 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-12 22:38:40,339 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:40,339 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:40,339 INFO L82 PathProgramCache]: Analyzing trace with hash -1278790061, now seen corresponding path program 1 times [2018-10-12 22:38:40,340 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:40,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:40,515 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-12 22:38:40,515 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:40,515 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-12 22:38:40,516 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-12 22:38:40,516 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-12 22:38:40,516 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-10-12 22:38:40,517 INFO L87 Difference]: Start difference. First operand 80 states and 82 transitions. Second operand 9 states. [2018-10-12 22:38:40,853 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:40,853 INFO L93 Difference]: Finished difference Result 105 states and 106 transitions. [2018-10-12 22:38:40,854 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-12 22:38:40,854 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 62 [2018-10-12 22:38:40,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:40,860 INFO L225 Difference]: With dead ends: 105 [2018-10-12 22:38:40,860 INFO L226 Difference]: Without dead ends: 89 [2018-10-12 22:38:40,860 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-12 22:38:40,861 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-10-12 22:38:40,870 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 75. [2018-10-12 22:38:40,870 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-10-12 22:38:40,871 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 76 transitions. [2018-10-12 22:38:40,871 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 76 transitions. Word has length 62 [2018-10-12 22:38:40,871 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:40,872 INFO L481 AbstractCegarLoop]: Abstraction has 75 states and 76 transitions. [2018-10-12 22:38:40,875 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-12 22:38:40,875 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 76 transitions. [2018-10-12 22:38:40,878 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-10-12 22:38:40,879 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:40,879 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-12 22:38:40,879 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:40,880 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:40,881 INFO L82 PathProgramCache]: Analyzing trace with hash 1155020689, now seen corresponding path program 2 times [2018-10-12 22:38:40,883 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:40,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:41,210 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-12 22:38:41,211 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:41,211 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-12 22:38:41,211 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-12 22:38:41,212 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-12 22:38:41,212 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-10-12 22:38:41,212 INFO L87 Difference]: Start difference. First operand 75 states and 76 transitions. Second operand 9 states. [2018-10-12 22:38:41,432 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:41,432 INFO L93 Difference]: Finished difference Result 88 states and 89 transitions. [2018-10-12 22:38:41,433 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-12 22:38:41,433 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 64 [2018-10-12 22:38:41,434 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:41,434 INFO L225 Difference]: With dead ends: 88 [2018-10-12 22:38:41,435 INFO L226 Difference]: Without dead ends: 88 [2018-10-12 22:38:41,435 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2018-10-12 22:38:41,435 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2018-10-12 22:38:41,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 79. [2018-10-12 22:38:41,441 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-10-12 22:38:41,442 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 80 transitions. [2018-10-12 22:38:41,442 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 80 transitions. Word has length 64 [2018-10-12 22:38:41,442 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:41,442 INFO L481 AbstractCegarLoop]: Abstraction has 79 states and 80 transitions. [2018-10-12 22:38:41,443 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-12 22:38:41,443 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 80 transitions. [2018-10-12 22:38:41,444 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2018-10-12 22:38:41,445 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:41,445 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-12 22:38:41,445 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:41,445 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:41,445 INFO L82 PathProgramCache]: Analyzing trace with hash -205510559, now seen corresponding path program 2 times [2018-10-12 22:38:41,446 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:41,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:42,100 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-12 22:38:42,101 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:42,101 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-12 22:38:42,101 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-12 22:38:42,102 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-12 22:38:42,102 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-10-12 22:38:42,102 INFO L87 Difference]: Start difference. First operand 79 states and 80 transitions. Second operand 13 states. [2018-10-12 22:38:43,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:43,125 INFO L93 Difference]: Finished difference Result 174 states and 176 transitions. [2018-10-12 22:38:43,125 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-12 22:38:43,126 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 78 [2018-10-12 22:38:43,127 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:43,128 INFO L225 Difference]: With dead ends: 174 [2018-10-12 22:38:43,128 INFO L226 Difference]: Without dead ends: 174 [2018-10-12 22:38:43,129 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 184 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=135, Invalid=735, Unknown=0, NotChecked=0, Total=870 [2018-10-12 22:38:43,130 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-10-12 22:38:43,136 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 93. [2018-10-12 22:38:43,137 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-10-12 22:38:43,137 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 94 transitions. [2018-10-12 22:38:43,138 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 94 transitions. Word has length 78 [2018-10-12 22:38:43,138 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:43,138 INFO L481 AbstractCegarLoop]: Abstraction has 93 states and 94 transitions. [2018-10-12 22:38:43,138 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-12 22:38:43,139 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 94 transitions. [2018-10-12 22:38:43,140 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2018-10-12 22:38:43,140 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:43,140 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-12 22:38:43,140 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:43,141 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:43,141 INFO L82 PathProgramCache]: Analyzing trace with hash -1203081935, now seen corresponding path program 3 times [2018-10-12 22:38:43,142 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:43,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:43,338 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-12 22:38:43,338 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:43,338 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-12 22:38:43,339 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-12 22:38:43,339 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-12 22:38:43,339 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-10-12 22:38:43,339 INFO L87 Difference]: Start difference. First operand 93 states and 94 transitions. Second operand 13 states. [2018-10-12 22:38:43,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:43,839 INFO L93 Difference]: Finished difference Result 153 states and 154 transitions. [2018-10-12 22:38:43,839 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-12 22:38:43,839 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 92 [2018-10-12 22:38:43,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:43,841 INFO L225 Difference]: With dead ends: 153 [2018-10-12 22:38:43,842 INFO L226 Difference]: Without dead ends: 123 [2018-10-12 22:38:43,843 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=117, Invalid=483, Unknown=0, NotChecked=0, Total=600 [2018-10-12 22:38:43,843 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2018-10-12 22:38:43,849 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 109. [2018-10-12 22:38:43,849 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-10-12 22:38:43,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 110 transitions. [2018-10-12 22:38:43,850 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 110 transitions. Word has length 92 [2018-10-12 22:38:43,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:43,851 INFO L481 AbstractCegarLoop]: Abstraction has 109 states and 110 transitions. [2018-10-12 22:38:43,851 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-12 22:38:43,851 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 110 transitions. [2018-10-12 22:38:43,853 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2018-10-12 22:38:43,853 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:43,853 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-12 22:38:43,853 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:43,854 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:43,854 INFO L82 PathProgramCache]: Analyzing trace with hash -397749569, now seen corresponding path program 4 times [2018-10-12 22:38:43,855 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:43,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:44,293 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-12 22:38:44,294 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:44,294 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-12 22:38:44,294 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-12 22:38:44,294 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-12 22:38:44,295 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=238, Unknown=0, NotChecked=0, Total=272 [2018-10-12 22:38:44,295 INFO L87 Difference]: Start difference. First operand 109 states and 110 transitions. Second operand 17 states. [2018-10-12 22:38:45,732 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:45,732 INFO L93 Difference]: Finished difference Result 143 states and 144 transitions. [2018-10-12 22:38:45,733 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-12 22:38:45,733 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 108 [2018-10-12 22:38:45,734 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:45,735 INFO L225 Difference]: With dead ends: 143 [2018-10-12 22:38:45,736 INFO L226 Difference]: Without dead ends: 143 [2018-10-12 22:38:45,737 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=185, Invalid=1075, Unknown=0, NotChecked=0, Total=1260 [2018-10-12 22:38:45,737 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2018-10-12 22:38:45,743 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 123. [2018-10-12 22:38:45,743 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 123 states. [2018-10-12 22:38:45,744 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 124 transitions. [2018-10-12 22:38:45,744 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 124 transitions. Word has length 108 [2018-10-12 22:38:45,744 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:45,745 INFO L481 AbstractCegarLoop]: Abstraction has 123 states and 124 transitions. [2018-10-12 22:38:45,745 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-12 22:38:45,745 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 124 transitions. [2018-10-12 22:38:45,747 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2018-10-12 22:38:45,747 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:45,747 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-12 22:38:45,747 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:45,747 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:45,748 INFO L82 PathProgramCache]: Analyzing trace with hash -1502307569, now seen corresponding path program 5 times [2018-10-12 22:38:45,749 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:45,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:46,088 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-12 22:38:46,089 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:46,089 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-12 22:38:46,091 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-12 22:38:46,091 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-12 22:38:46,091 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2018-10-12 22:38:46,092 INFO L87 Difference]: Start difference. First operand 123 states and 124 transitions. Second operand 17 states. [2018-10-12 22:38:46,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:46,693 INFO L93 Difference]: Finished difference Result 197 states and 198 transitions. [2018-10-12 22:38:46,693 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-12 22:38:46,694 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 122 [2018-10-12 22:38:46,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:46,695 INFO L225 Difference]: With dead ends: 197 [2018-10-12 22:38:46,696 INFO L226 Difference]: Without dead ends: 153 [2018-10-12 22:38:46,697 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 216 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=198, Invalid=924, Unknown=0, NotChecked=0, Total=1122 [2018-10-12 22:38:46,697 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2018-10-12 22:38:46,702 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 139. [2018-10-12 22:38:46,702 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 139 states. [2018-10-12 22:38:46,703 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 140 transitions. [2018-10-12 22:38:46,703 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 140 transitions. Word has length 122 [2018-10-12 22:38:46,704 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:46,704 INFO L481 AbstractCegarLoop]: Abstraction has 139 states and 140 transitions. [2018-10-12 22:38:46,704 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-12 22:38:46,704 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 140 transitions. [2018-10-12 22:38:46,706 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2018-10-12 22:38:46,706 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:46,707 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-12 22:38:46,707 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:46,707 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:46,707 INFO L82 PathProgramCache]: Analyzing trace with hash 1184191517, now seen corresponding path program 6 times [2018-10-12 22:38:46,708 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:46,727 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:47,401 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-12 22:38:47,401 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:47,402 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-12 22:38:47,402 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-12 22:38:47,402 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-12 22:38:47,402 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=375, Unknown=0, NotChecked=0, Total=420 [2018-10-12 22:38:47,403 INFO L87 Difference]: Start difference. First operand 139 states and 140 transitions. Second operand 21 states. [2018-10-12 22:38:49,072 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:49,073 INFO L93 Difference]: Finished difference Result 173 states and 174 transitions. [2018-10-12 22:38:49,073 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-12 22:38:49,073 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 138 [2018-10-12 22:38:49,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:49,075 INFO L225 Difference]: With dead ends: 173 [2018-10-12 22:38:49,075 INFO L226 Difference]: Without dead ends: 173 [2018-10-12 22:38:49,077 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 330 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=259, Invalid=1721, Unknown=0, NotChecked=0, Total=1980 [2018-10-12 22:38:49,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2018-10-12 22:38:49,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 153. [2018-10-12 22:38:49,082 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 153 states. [2018-10-12 22:38:49,083 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 154 transitions. [2018-10-12 22:38:49,083 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 154 transitions. Word has length 138 [2018-10-12 22:38:49,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:49,083 INFO L481 AbstractCegarLoop]: Abstraction has 153 states and 154 transitions. [2018-10-12 22:38:49,083 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-12 22:38:49,084 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 154 transitions. [2018-10-12 22:38:49,085 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 153 [2018-10-12 22:38:49,086 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:49,086 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-12 22:38:49,086 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:49,086 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:49,086 INFO L82 PathProgramCache]: Analyzing trace with hash -900046867, now seen corresponding path program 7 times [2018-10-12 22:38:49,087 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:49,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:50,301 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-12 22:38:50,301 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:50,301 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-12 22:38:50,302 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-12 22:38:50,302 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-12 22:38:50,302 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=354, Unknown=0, NotChecked=0, Total=420 [2018-10-12 22:38:50,303 INFO L87 Difference]: Start difference. First operand 153 states and 154 transitions. Second operand 21 states. [2018-10-12 22:38:50,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:50,985 INFO L93 Difference]: Finished difference Result 241 states and 242 transitions. [2018-10-12 22:38:50,986 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-10-12 22:38:50,986 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 152 [2018-10-12 22:38:50,987 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:50,988 INFO L225 Difference]: With dead ends: 241 [2018-10-12 22:38:50,988 INFO L226 Difference]: Without dead ends: 183 [2018-10-12 22:38:50,989 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 384 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=303, Invalid=1503, Unknown=0, NotChecked=0, Total=1806 [2018-10-12 22:38:50,989 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2018-10-12 22:38:50,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 169. [2018-10-12 22:38:50,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 169 states. [2018-10-12 22:38:50,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 170 transitions. [2018-10-12 22:38:50,994 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 170 transitions. Word has length 152 [2018-10-12 22:38:50,994 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:50,995 INFO L481 AbstractCegarLoop]: Abstraction has 169 states and 170 transitions. [2018-10-12 22:38:50,995 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-12 22:38:50,995 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 170 transitions. [2018-10-12 22:38:50,997 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 169 [2018-10-12 22:38:50,997 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:50,997 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-12 22:38:50,997 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:50,997 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:50,998 INFO L82 PathProgramCache]: Analyzing trace with hash -806597509, now seen corresponding path program 8 times [2018-10-12 22:38:50,998 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:51,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:51,626 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-12 22:38:51,627 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:51,627 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-12 22:38:51,627 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-12 22:38:51,628 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-12 22:38:51,628 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=542, Unknown=0, NotChecked=0, Total=600 [2018-10-12 22:38:51,628 INFO L87 Difference]: Start difference. First operand 169 states and 170 transitions. Second operand 25 states. [2018-10-12 22:38:53,767 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:53,768 INFO L93 Difference]: Finished difference Result 203 states and 204 transitions. [2018-10-12 22:38:53,768 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-10-12 22:38:53,768 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 168 [2018-10-12 22:38:53,769 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:53,770 INFO L225 Difference]: With dead ends: 203 [2018-10-12 22:38:53,770 INFO L226 Difference]: Without dead ends: 203 [2018-10-12 22:38:53,772 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 523 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=349, Invalid=2513, Unknown=0, NotChecked=0, Total=2862 [2018-10-12 22:38:53,772 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2018-10-12 22:38:53,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 183. [2018-10-12 22:38:53,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 183 states. [2018-10-12 22:38:53,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 184 transitions. [2018-10-12 22:38:53,776 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 184 transitions. Word has length 168 [2018-10-12 22:38:53,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:53,777 INFO L481 AbstractCegarLoop]: Abstraction has 183 states and 184 transitions. [2018-10-12 22:38:53,777 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-12 22:38:53,777 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 184 transitions. [2018-10-12 22:38:53,779 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2018-10-12 22:38:53,779 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:53,779 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-12 22:38:53,779 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:53,780 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:53,781 INFO L82 PathProgramCache]: Analyzing trace with hash -760194101, now seen corresponding path program 9 times [2018-10-12 22:38:53,782 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:53,796 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:54,140 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-12 22:38:54,141 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:54,141 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-12 22:38:54,141 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-12 22:38:54,142 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-12 22:38:54,142 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=510, Unknown=0, NotChecked=0, Total=600 [2018-10-12 22:38:54,142 INFO L87 Difference]: Start difference. First operand 183 states and 184 transitions. Second operand 25 states. [2018-10-12 22:38:54,831 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:54,831 INFO L93 Difference]: Finished difference Result 285 states and 286 transitions. [2018-10-12 22:38:54,832 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-12 22:38:54,832 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 182 [2018-10-12 22:38:54,833 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:54,834 INFO L225 Difference]: With dead ends: 285 [2018-10-12 22:38:54,834 INFO L226 Difference]: Without dead ends: 213 [2018-10-12 22:38:54,835 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 599 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=432, Invalid=2220, Unknown=0, NotChecked=0, Total=2652 [2018-10-12 22:38:54,836 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-10-12 22:38:54,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-10-12 22:38:54,839 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-10-12 22:38:54,839 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 200 transitions. [2018-10-12 22:38:54,840 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 200 transitions. Word has length 182 [2018-10-12 22:38:54,840 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:54,840 INFO L481 AbstractCegarLoop]: Abstraction has 199 states and 200 transitions. [2018-10-12 22:38:54,840 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-12 22:38:54,840 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 200 transitions. [2018-10-12 22:38:54,842 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-10-12 22:38:54,842 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:54,842 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-12 22:38:54,843 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:54,843 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:54,843 INFO L82 PathProgramCache]: Analyzing trace with hash -1237558311, now seen corresponding path program 10 times [2018-10-12 22:38:54,844 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:54,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:55,458 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-12 22:38:55,459 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:55,459 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-12 22:38:55,459 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-12 22:38:55,460 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-12 22:38:55,460 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=721, Unknown=0, NotChecked=0, Total=812 [2018-10-12 22:38:55,460 INFO L87 Difference]: Start difference. First operand 199 states and 200 transitions. Second operand 29 states. [2018-10-12 22:38:58,352 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:38:58,352 INFO L93 Difference]: Finished difference Result 233 states and 234 transitions. [2018-10-12 22:38:58,360 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-10-12 22:38:58,360 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 198 [2018-10-12 22:38:58,360 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:38:58,361 INFO L225 Difference]: With dead ends: 233 [2018-10-12 22:38:58,361 INFO L226 Difference]: Without dead ends: 233 [2018-10-12 22:38:58,363 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 914 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=742, Invalid=3418, Unknown=0, NotChecked=0, Total=4160 [2018-10-12 22:38:58,363 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2018-10-12 22:38:58,366 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 213. [2018-10-12 22:38:58,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-10-12 22:38:58,366 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 214 transitions. [2018-10-12 22:38:58,367 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 214 transitions. Word has length 198 [2018-10-12 22:38:58,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:38:58,367 INFO L481 AbstractCegarLoop]: Abstraction has 213 states and 214 transitions. [2018-10-12 22:38:58,367 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-12 22:38:58,367 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 214 transitions. [2018-10-12 22:38:58,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-10-12 22:38:58,368 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:38:58,368 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-12 22:38:58,369 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:38:58,369 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:38:58,369 INFO L82 PathProgramCache]: Analyzing trace with hash 1187720873, now seen corresponding path program 11 times [2018-10-12 22:38:58,370 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:38:58,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:38:59,226 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-12 22:38:59,227 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:38:59,227 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-12 22:38:59,227 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-12 22:38:59,228 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-12 22:38:59,228 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=694, Unknown=0, NotChecked=0, Total=812 [2018-10-12 22:38:59,228 INFO L87 Difference]: Start difference. First operand 213 states and 214 transitions. Second operand 29 states. [2018-10-12 22:39:00,442 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:00,443 INFO L93 Difference]: Finished difference Result 329 states and 330 transitions. [2018-10-12 22:39:00,443 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-10-12 22:39:00,443 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 212 [2018-10-12 22:39:00,444 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:00,446 INFO L225 Difference]: With dead ends: 329 [2018-10-12 22:39:00,447 INFO L226 Difference]: Without dead ends: 243 [2018-10-12 22:39:00,448 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-12 22:39:00,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 243 states. [2018-10-12 22:39:00,452 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 243 to 229. [2018-10-12 22:39:00,452 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 229 states. [2018-10-12 22:39:00,452 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 230 transitions. [2018-10-12 22:39:00,453 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 230 transitions. Word has length 212 [2018-10-12 22:39:00,453 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:00,453 INFO L481 AbstractCegarLoop]: Abstraction has 229 states and 230 transitions. [2018-10-12 22:39:00,453 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-12 22:39:00,453 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 230 transitions. [2018-10-12 22:39:00,454 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 229 [2018-10-12 22:39:00,455 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:00,455 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-12 22:39:00,455 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:00,455 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:00,455 INFO L82 PathProgramCache]: Analyzing trace with hash -1844305353, now seen corresponding path program 12 times [2018-10-12 22:39:00,456 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:00,484 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:01,304 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-12 22:39:01,305 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:01,305 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-12 22:39:01,305 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-12 22:39:01,306 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-12 22:39:01,306 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=948, Unknown=0, NotChecked=0, Total=1056 [2018-10-12 22:39:01,306 INFO L87 Difference]: Start difference. First operand 229 states and 230 transitions. Second operand 33 states. [2018-10-12 22:39:03,874 WARN L178 SmtUtils]: Spent 434.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 41 [2018-10-12 22:39:05,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:05,065 INFO L93 Difference]: Finished difference Result 263 states and 264 transitions. [2018-10-12 22:39:05,065 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2018-10-12 22:39:05,065 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 228 [2018-10-12 22:39:05,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:05,067 INFO L225 Difference]: With dead ends: 263 [2018-10-12 22:39:05,067 INFO L226 Difference]: Without dead ends: 263 [2018-10-12 22:39:05,069 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1181 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=869, Invalid=4387, Unknown=0, NotChecked=0, Total=5256 [2018-10-12 22:39:05,069 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 263 states. [2018-10-12 22:39:05,072 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 263 to 243. [2018-10-12 22:39:05,072 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 243 states. [2018-10-12 22:39:05,073 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 244 transitions. [2018-10-12 22:39:05,073 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 244 transitions. Word has length 228 [2018-10-12 22:39:05,074 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:05,074 INFO L481 AbstractCegarLoop]: Abstraction has 243 states and 244 transitions. [2018-10-12 22:39:05,074 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-12 22:39:05,074 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 244 transitions. [2018-10-12 22:39:05,075 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 243 [2018-10-12 22:39:05,075 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:05,076 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-12 22:39:05,076 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:05,076 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:05,076 INFO L82 PathProgramCache]: Analyzing trace with hash -56657785, now seen corresponding path program 13 times [2018-10-12 22:39:05,077 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:05,095 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:05,910 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-12 22:39:05,911 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:05,911 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-12 22:39:05,911 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-12 22:39:05,912 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-12 22:39:05,912 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=906, Unknown=0, NotChecked=0, Total=1056 [2018-10-12 22:39:05,912 INFO L87 Difference]: Start difference. First operand 243 states and 244 transitions. Second operand 33 states. [2018-10-12 22:39:07,031 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:07,031 INFO L93 Difference]: Finished difference Result 373 states and 374 transitions. [2018-10-12 22:39:07,031 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-10-12 22:39:07,032 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 242 [2018-10-12 22:39:07,032 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:07,034 INFO L225 Difference]: With dead ends: 373 [2018-10-12 22:39:07,034 INFO L226 Difference]: Without dead ends: 273 [2018-10-12 22:39:07,036 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1170 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=762, Invalid=4068, Unknown=0, NotChecked=0, Total=4830 [2018-10-12 22:39:07,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 273 states. [2018-10-12 22:39:07,040 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 273 to 259. [2018-10-12 22:39:07,040 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 259 states. [2018-10-12 22:39:07,041 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 259 states to 259 states and 260 transitions. [2018-10-12 22:39:07,041 INFO L78 Accepts]: Start accepts. Automaton has 259 states and 260 transitions. Word has length 242 [2018-10-12 22:39:07,041 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:07,042 INFO L481 AbstractCegarLoop]: Abstraction has 259 states and 260 transitions. [2018-10-12 22:39:07,042 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-12 22:39:07,042 INFO L276 IsEmpty]: Start isEmpty. Operand 259 states and 260 transitions. [2018-10-12 22:39:07,043 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 259 [2018-10-12 22:39:07,043 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:07,043 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-12 22:39:07,044 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:07,044 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:07,044 INFO L82 PathProgramCache]: Analyzing trace with hash 1486503829, now seen corresponding path program 14 times [2018-10-12 22:39:07,045 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:07,065 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:08,075 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-12 22:39:08,075 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:08,075 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-12 22:39:08,076 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-12 22:39:08,076 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-12 22:39:08,076 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=1205, Unknown=0, NotChecked=0, Total=1332 [2018-10-12 22:39:08,077 INFO L87 Difference]: Start difference. First operand 259 states and 260 transitions. Second operand 37 states. [2018-10-12 22:39:11,925 WARN L178 SmtUtils]: Spent 117.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 41 [2018-10-12 22:39:12,378 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:12,378 INFO L93 Difference]: Finished difference Result 293 states and 294 transitions. [2018-10-12 22:39:12,386 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-10-12 22:39:12,386 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 258 [2018-10-12 22:39:12,387 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:12,388 INFO L225 Difference]: With dead ends: 293 [2018-10-12 22:39:12,388 INFO L226 Difference]: Without dead ends: 293 [2018-10-12 22:39:12,390 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1523 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=1031, Invalid=5611, Unknown=0, NotChecked=0, Total=6642 [2018-10-12 22:39:12,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-10-12 22:39:12,396 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 273. [2018-10-12 22:39:12,397 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 273 states. [2018-10-12 22:39:12,398 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 273 states to 273 states and 274 transitions. [2018-10-12 22:39:12,398 INFO L78 Accepts]: Start accepts. Automaton has 273 states and 274 transitions. Word has length 258 [2018-10-12 22:39:12,398 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:12,399 INFO L481 AbstractCegarLoop]: Abstraction has 273 states and 274 transitions. [2018-10-12 22:39:12,399 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-12 22:39:12,399 INFO L276 IsEmpty]: Start isEmpty. Operand 273 states and 274 transitions. [2018-10-12 22:39:12,400 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2018-10-12 22:39:12,400 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:12,400 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-12 22:39:12,401 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:12,401 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:12,401 INFO L82 PathProgramCache]: Analyzing trace with hash -1899898523, now seen corresponding path program 15 times [2018-10-12 22:39:12,402 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:12,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:13,252 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-12 22:39:13,252 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:13,252 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-12 22:39:13,253 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-12 22:39:13,253 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-12 22:39:13,253 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=186, Invalid=1146, Unknown=0, NotChecked=0, Total=1332 [2018-10-12 22:39:13,254 INFO L87 Difference]: Start difference. First operand 273 states and 274 transitions. Second operand 37 states. [2018-10-12 22:39:14,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:14,559 INFO L93 Difference]: Finished difference Result 417 states and 418 transitions. [2018-10-12 22:39:14,560 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-12 22:39:14,560 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 272 [2018-10-12 22:39:14,561 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:14,562 INFO L225 Difference]: With dead ends: 417 [2018-10-12 22:39:14,562 INFO L226 Difference]: Without dead ends: 303 [2018-10-12 22:39:14,564 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1526 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=963, Invalid=5199, Unknown=0, NotChecked=0, Total=6162 [2018-10-12 22:39:14,565 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2018-10-12 22:39:14,568 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 289. [2018-10-12 22:39:14,568 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 289 states. [2018-10-12 22:39:14,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 289 states to 289 states and 290 transitions. [2018-10-12 22:39:14,569 INFO L78 Accepts]: Start accepts. Automaton has 289 states and 290 transitions. Word has length 272 [2018-10-12 22:39:14,570 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:14,570 INFO L481 AbstractCegarLoop]: Abstraction has 289 states and 290 transitions. [2018-10-12 22:39:14,570 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-12 22:39:14,570 INFO L276 IsEmpty]: Start isEmpty. Operand 289 states and 290 transitions. [2018-10-12 22:39:14,571 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 289 [2018-10-12 22:39:14,572 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:14,572 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-12 22:39:14,572 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:14,572 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:14,572 INFO L82 PathProgramCache]: Analyzing trace with hash 1369527283, now seen corresponding path program 16 times [2018-10-12 22:39:14,573 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:14,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:15,556 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-12 22:39:15,557 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:15,557 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-12 22:39:15,557 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-12 22:39:15,558 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-12 22:39:15,558 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=1492, Unknown=0, NotChecked=0, Total=1640 [2018-10-12 22:39:15,559 INFO L87 Difference]: Start difference. First operand 289 states and 290 transitions. Second operand 41 states. [2018-10-12 22:39:19,978 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:19,979 INFO L93 Difference]: Finished difference Result 323 states and 324 transitions. [2018-10-12 22:39:19,979 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-10-12 22:39:19,979 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 288 [2018-10-12 22:39:19,980 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:19,981 INFO L225 Difference]: With dead ends: 323 [2018-10-12 22:39:19,981 INFO L226 Difference]: Without dead ends: 323 [2018-10-12 22:39:19,984 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1906 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=1208, Invalid=6982, Unknown=0, NotChecked=0, Total=8190 [2018-10-12 22:39:19,985 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 323 states. [2018-10-12 22:39:19,988 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 323 to 303. [2018-10-12 22:39:19,989 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 303 states. [2018-10-12 22:39:19,989 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 303 states to 303 states and 304 transitions. [2018-10-12 22:39:19,990 INFO L78 Accepts]: Start accepts. Automaton has 303 states and 304 transitions. Word has length 288 [2018-10-12 22:39:19,990 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:19,990 INFO L481 AbstractCegarLoop]: Abstraction has 303 states and 304 transitions. [2018-10-12 22:39:19,990 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-12 22:39:19,991 INFO L276 IsEmpty]: Start isEmpty. Operand 303 states and 304 transitions. [2018-10-12 22:39:19,992 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 303 [2018-10-12 22:39:19,992 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:19,992 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-12 22:39:19,993 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:19,993 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:19,993 INFO L82 PathProgramCache]: Analyzing trace with hash -765005501, now seen corresponding path program 17 times [2018-10-12 22:39:19,994 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:20,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:20,972 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-12 22:39:20,973 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:20,973 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-12 22:39:20,973 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-12 22:39:20,973 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-12 22:39:20,974 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=226, Invalid=1414, Unknown=0, NotChecked=0, Total=1640 [2018-10-12 22:39:20,974 INFO L87 Difference]: Start difference. First operand 303 states and 304 transitions. Second operand 41 states. [2018-10-12 22:39:22,266 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:22,266 INFO L93 Difference]: Finished difference Result 461 states and 462 transitions. [2018-10-12 22:39:22,266 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2018-10-12 22:39:22,267 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 302 [2018-10-12 22:39:22,267 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:22,269 INFO L225 Difference]: With dead ends: 461 [2018-10-12 22:39:22,269 INFO L226 Difference]: Without dead ends: 333 [2018-10-12 22:39:22,271 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1929 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=1188, Invalid=6468, Unknown=0, NotChecked=0, Total=7656 [2018-10-12 22:39:22,271 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 333 states. [2018-10-12 22:39:22,275 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 333 to 319. [2018-10-12 22:39:22,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 319 states. [2018-10-12 22:39:22,276 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 319 states to 319 states and 320 transitions. [2018-10-12 22:39:22,276 INFO L78 Accepts]: Start accepts. Automaton has 319 states and 320 transitions. Word has length 302 [2018-10-12 22:39:22,276 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:22,276 INFO L481 AbstractCegarLoop]: Abstraction has 319 states and 320 transitions. [2018-10-12 22:39:22,276 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-12 22:39:22,277 INFO L276 IsEmpty]: Start isEmpty. Operand 319 states and 320 transitions. [2018-10-12 22:39:22,278 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 319 [2018-10-12 22:39:22,278 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:22,279 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-12 22:39:22,279 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:22,279 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:22,279 INFO L82 PathProgramCache]: Analyzing trace with hash 227802961, now seen corresponding path program 18 times [2018-10-12 22:39:22,280 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:22,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:23,806 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-12 22:39:23,807 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:23,807 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-12 22:39:23,807 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-12 22:39:23,808 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-12 22:39:23,808 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=219, Invalid=1761, Unknown=0, NotChecked=0, Total=1980 [2018-10-12 22:39:23,808 INFO L87 Difference]: Start difference. First operand 319 states and 320 transitions. Second operand 45 states. [2018-10-12 22:39:28,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:28,743 INFO L93 Difference]: Finished difference Result 353 states and 354 transitions. [2018-10-12 22:39:28,743 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-10-12 22:39:28,743 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 318 [2018-10-12 22:39:28,744 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:28,746 INFO L225 Difference]: With dead ends: 353 [2018-10-12 22:39:28,746 INFO L226 Difference]: Without dead ends: 353 [2018-10-12 22:39:28,748 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2716 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=1920, Invalid=9000, Unknown=0, NotChecked=0, Total=10920 [2018-10-12 22:39:28,748 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2018-10-12 22:39:28,752 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 333. [2018-10-12 22:39:28,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 333 states. [2018-10-12 22:39:28,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 334 transitions. [2018-10-12 22:39:28,753 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 334 transitions. Word has length 318 [2018-10-12 22:39:28,753 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:28,753 INFO L481 AbstractCegarLoop]: Abstraction has 333 states and 334 transitions. [2018-10-12 22:39:28,753 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-12 22:39:28,753 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 334 transitions. [2018-10-12 22:39:28,755 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 333 [2018-10-12 22:39:28,755 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:28,756 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-12 22:39:28,756 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:28,756 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:28,756 INFO L82 PathProgramCache]: Analyzing trace with hash 1298358305, now seen corresponding path program 19 times [2018-10-12 22:39:28,757 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:28,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:29,773 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-12 22:39:29,774 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:29,774 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-12 22:39:29,774 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-12 22:39:29,775 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-12 22:39:29,775 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=270, Invalid=1710, Unknown=0, NotChecked=0, Total=1980 [2018-10-12 22:39:29,775 INFO L87 Difference]: Start difference. First operand 333 states and 334 transitions. Second operand 45 states. [2018-10-12 22:39:31,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:31,894 INFO L93 Difference]: Finished difference Result 505 states and 506 transitions. [2018-10-12 22:39:31,895 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-10-12 22:39:31,895 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 332 [2018-10-12 22:39:31,896 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:31,897 INFO L225 Difference]: With dead ends: 505 [2018-10-12 22:39:31,897 INFO L226 Difference]: Without dead ends: 363 [2018-10-12 22:39:31,899 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-12 22:39:31,899 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 363 states. [2018-10-12 22:39:31,904 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 363 to 349. [2018-10-12 22:39:31,904 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 349 states. [2018-10-12 22:39:31,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 349 states to 349 states and 350 transitions. [2018-10-12 22:39:31,905 INFO L78 Accepts]: Start accepts. Automaton has 349 states and 350 transitions. Word has length 332 [2018-10-12 22:39:31,905 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:31,905 INFO L481 AbstractCegarLoop]: Abstraction has 349 states and 350 transitions. [2018-10-12 22:39:31,905 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-12 22:39:31,905 INFO L276 IsEmpty]: Start isEmpty. Operand 349 states and 350 transitions. [2018-10-12 22:39:31,907 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 349 [2018-10-12 22:39:31,907 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:31,908 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-12 22:39:31,908 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:31,908 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:31,908 INFO L82 PathProgramCache]: Analyzing trace with hash 1535041967, now seen corresponding path program 20 times [2018-10-12 22:39:31,909 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:31,934 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:33,733 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-12 22:39:33,733 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:33,734 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-12 22:39:33,734 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-12 22:39:33,734 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-12 22:39:33,735 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=244, Invalid=2108, Unknown=0, NotChecked=0, Total=2352 [2018-10-12 22:39:33,735 INFO L87 Difference]: Start difference. First operand 349 states and 350 transitions. Second operand 49 states. [2018-10-12 22:39:39,722 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:39,722 INFO L93 Difference]: Finished difference Result 383 states and 384 transitions. [2018-10-12 22:39:39,723 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-12 22:39:39,723 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 348 [2018-10-12 22:39:39,723 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:39,725 INFO L225 Difference]: With dead ends: 383 [2018-10-12 22:39:39,725 INFO L226 Difference]: Without dead ends: 383 [2018-10-12 22:39:39,726 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3155 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=2127, Invalid=10529, Unknown=0, NotChecked=0, Total=12656 [2018-10-12 22:39:39,727 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 383 states. [2018-10-12 22:39:39,731 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 383 to 363. [2018-10-12 22:39:39,731 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 363 states. [2018-10-12 22:39:39,732 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 364 transitions. [2018-10-12 22:39:39,732 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 364 transitions. Word has length 348 [2018-10-12 22:39:39,732 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:39,733 INFO L481 AbstractCegarLoop]: Abstraction has 363 states and 364 transitions. [2018-10-12 22:39:39,733 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-12 22:39:39,733 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 364 transitions. [2018-10-12 22:39:39,735 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 363 [2018-10-12 22:39:39,735 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:39,735 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-12 22:39:39,735 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:39,736 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:39,736 INFO L82 PathProgramCache]: Analyzing trace with hash -1406417409, now seen corresponding path program 21 times [2018-10-12 22:39:39,737 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:39,759 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:41,058 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-12 22:39:41,059 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:41,059 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-12 22:39:41,059 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-12 22:39:41,060 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-12 22:39:41,060 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=318, Invalid=2034, Unknown=0, NotChecked=0, Total=2352 [2018-10-12 22:39:41,061 INFO L87 Difference]: Start difference. First operand 363 states and 364 transitions. Second operand 49 states. [2018-10-12 22:39:43,516 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:43,517 INFO L93 Difference]: Finished difference Result 549 states and 550 transitions. [2018-10-12 22:39:43,517 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 71 states. [2018-10-12 22:39:43,517 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 362 [2018-10-12 22:39:43,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:43,519 INFO L225 Difference]: With dead ends: 549 [2018-10-12 22:39:43,519 INFO L226 Difference]: Without dead ends: 393 [2018-10-12 22:39:43,520 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2876 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=1710, Invalid=9420, Unknown=0, NotChecked=0, Total=11130 [2018-10-12 22:39:43,520 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 393 states. [2018-10-12 22:39:43,524 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 393 to 379. [2018-10-12 22:39:43,524 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-10-12 22:39:43,525 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 380 transitions. [2018-10-12 22:39:43,525 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 380 transitions. Word has length 362 [2018-10-12 22:39:43,526 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:43,526 INFO L481 AbstractCegarLoop]: Abstraction has 379 states and 380 transitions. [2018-10-12 22:39:43,526 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-12 22:39:43,526 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 380 transitions. [2018-10-12 22:39:43,528 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 379 [2018-10-12 22:39:43,528 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:43,528 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-12 22:39:43,529 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:43,529 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:43,529 INFO L82 PathProgramCache]: Analyzing trace with hash 1057921805, now seen corresponding path program 22 times [2018-10-12 22:39:43,530 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:43,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:45,010 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-12 22:39:45,011 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:45,011 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-12 22:39:45,011 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-12 22:39:45,011 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-12 22:39:45,012 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=271, Invalid=2485, Unknown=0, NotChecked=0, Total=2756 [2018-10-12 22:39:45,012 INFO L87 Difference]: Start difference. First operand 379 states and 380 transitions. Second operand 53 states. [2018-10-12 22:39:51,456 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:51,457 INFO L93 Difference]: Finished difference Result 413 states and 414 transitions. [2018-10-12 22:39:51,458 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-12 22:39:51,458 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 378 [2018-10-12 22:39:51,459 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:51,460 INFO L225 Difference]: With dead ends: 413 [2018-10-12 22:39:51,460 INFO L226 Difference]: Without dead ends: 413 [2018-10-12 22:39:51,462 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3697 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=2377, Invalid=12385, Unknown=0, NotChecked=0, Total=14762 [2018-10-12 22:39:51,462 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 413 states. [2018-10-12 22:39:51,466 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 413 to 393. [2018-10-12 22:39:51,466 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 393 states. [2018-10-12 22:39:51,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 393 states to 393 states and 394 transitions. [2018-10-12 22:39:51,467 INFO L78 Accepts]: Start accepts. Automaton has 393 states and 394 transitions. Word has length 378 [2018-10-12 22:39:51,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:51,468 INFO L481 AbstractCegarLoop]: Abstraction has 393 states and 394 transitions. [2018-10-12 22:39:51,468 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-12 22:39:51,468 INFO L276 IsEmpty]: Start isEmpty. Operand 393 states and 394 transitions. [2018-10-12 22:39:51,470 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 393 [2018-10-12 22:39:51,470 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:51,470 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-12 22:39:51,471 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:51,471 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:51,471 INFO L82 PathProgramCache]: Analyzing trace with hash 936690397, now seen corresponding path program 23 times [2018-10-12 22:39:51,472 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:51,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:52,594 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-12 22:39:52,594 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:52,594 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-12 22:39:52,595 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-12 22:39:52,595 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-12 22:39:52,596 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=370, Invalid=2386, Unknown=0, NotChecked=0, Total=2756 [2018-10-12 22:39:52,596 INFO L87 Difference]: Start difference. First operand 393 states and 394 transitions. Second operand 53 states. [2018-10-12 22:39:55,217 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:39:55,218 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-12 22:39:55,218 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-12 22:39:55,218 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 392 [2018-10-12 22:39:55,219 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:39:55,220 INFO L225 Difference]: With dead ends: 593 [2018-10-12 22:39:55,220 INFO L226 Difference]: Without dead ends: 423 [2018-10-12 22:39:55,221 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3420 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=2007, Invalid=11103, Unknown=0, NotChecked=0, Total=13110 [2018-10-12 22:39:55,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 423 states. [2018-10-12 22:39:55,225 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 423 to 409. [2018-10-12 22:39:55,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 409 states. [2018-10-12 22:39:55,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 409 states to 409 states and 410 transitions. [2018-10-12 22:39:55,226 INFO L78 Accepts]: Start accepts. Automaton has 409 states and 410 transitions. Word has length 392 [2018-10-12 22:39:55,227 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:39:55,227 INFO L481 AbstractCegarLoop]: Abstraction has 409 states and 410 transitions. [2018-10-12 22:39:55,227 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-12 22:39:55,227 INFO L276 IsEmpty]: Start isEmpty. Operand 409 states and 410 transitions. [2018-10-12 22:39:55,229 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 409 [2018-10-12 22:39:55,229 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:39:55,230 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-12 22:39:55,230 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:39:55,230 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:39:55,230 INFO L82 PathProgramCache]: Analyzing trace with hash -426783893, now seen corresponding path program 24 times [2018-10-12 22:39:55,231 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:39:55,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:39:58,660 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-12 22:39:58,660 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:39:58,660 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-12 22:39:58,661 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-12 22:39:58,661 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-12 22:39:58,661 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=234, Invalid=2958, Unknown=0, NotChecked=0, Total=3192 [2018-10-12 22:39:58,662 INFO L87 Difference]: Start difference. First operand 409 states and 410 transitions. Second operand 57 states. [2018-10-12 22:40:06,416 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:40:06,416 INFO L93 Difference]: Finished difference Result 443 states and 444 transitions. [2018-10-12 22:40:06,417 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-10-12 22:40:06,417 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 408 [2018-10-12 22:40:06,417 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:40:06,419 INFO L225 Difference]: With dead ends: 443 [2018-10-12 22:40:06,419 INFO L226 Difference]: Without dead ends: 443 [2018-10-12 22:40:06,420 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3543 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=1645, Invalid=14105, Unknown=0, NotChecked=0, Total=15750 [2018-10-12 22:40:06,421 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 443 states. [2018-10-12 22:40:06,424 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 443 to 423. [2018-10-12 22:40:06,425 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 423 states. [2018-10-12 22:40:06,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 423 states to 423 states and 424 transitions. [2018-10-12 22:40:06,426 INFO L78 Accepts]: Start accepts. Automaton has 423 states and 424 transitions. Word has length 408 [2018-10-12 22:40:06,426 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:40:06,426 INFO L481 AbstractCegarLoop]: Abstraction has 423 states and 424 transitions. [2018-10-12 22:40:06,426 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-12 22:40:06,426 INFO L276 IsEmpty]: Start isEmpty. Operand 423 states and 424 transitions. [2018-10-12 22:40:06,428 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 423 [2018-10-12 22:40:06,429 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:40:06,429 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-12 22:40:06,429 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:40:06,429 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:40:06,430 INFO L82 PathProgramCache]: Analyzing trace with hash 1276311227, now seen corresponding path program 25 times [2018-10-12 22:40:06,430 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:40:06,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:40:07,725 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-12 22:40:07,726 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:40:07,726 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-12 22:40:07,727 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-12 22:40:07,727 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-12 22:40:07,727 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=426, Invalid=2766, Unknown=0, NotChecked=0, Total=3192 [2018-10-12 22:40:07,727 INFO L87 Difference]: Start difference. First operand 423 states and 424 transitions. Second operand 57 states. [2018-10-12 22:40:10,841 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:40:10,841 INFO L93 Difference]: Finished difference Result 637 states and 638 transitions. [2018-10-12 22:40:10,841 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-12 22:40:10,841 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 422 [2018-10-12 22:40:10,842 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:40:10,844 INFO L225 Difference]: With dead ends: 637 [2018-10-12 22:40:10,844 INFO L226 Difference]: Without dead ends: 453 [2018-10-12 22:40:10,845 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4011 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=2328, Invalid=12924, Unknown=0, NotChecked=0, Total=15252 [2018-10-12 22:40:10,845 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 453 states. [2018-10-12 22:40:10,849 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 453 to 439. [2018-10-12 22:40:10,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 439 states. [2018-10-12 22:40:10,850 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 439 states to 439 states and 440 transitions. [2018-10-12 22:40:10,851 INFO L78 Accepts]: Start accepts. Automaton has 439 states and 440 transitions. Word has length 422 [2018-10-12 22:40:10,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:40:10,851 INFO L481 AbstractCegarLoop]: Abstraction has 439 states and 440 transitions. [2018-10-12 22:40:10,851 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-12 22:40:10,851 INFO L276 IsEmpty]: Start isEmpty. Operand 439 states and 440 transitions. [2018-10-12 22:40:10,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 439 [2018-10-12 22:40:10,854 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:40:10,854 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-12 22:40:10,854 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:40:10,854 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:40:10,855 INFO L82 PathProgramCache]: Analyzing trace with hash -1594944823, now seen corresponding path program 26 times [2018-10-12 22:40:10,855 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:40:10,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:40:12,516 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-12 22:40:12,516 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:40:12,517 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-12 22:40:12,517 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-12 22:40:12,517 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-12 22:40:12,517 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=411, Invalid=3249, Unknown=0, NotChecked=0, Total=3660 [2018-10-12 22:40:12,518 INFO L87 Difference]: Start difference. First operand 439 states and 440 transitions. Second operand 61 states. [2018-10-12 22:40:21,018 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:40:21,018 INFO L93 Difference]: Finished difference Result 473 states and 474 transitions. [2018-10-12 22:40:21,018 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-10-12 22:40:21,018 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 438 [2018-10-12 22:40:21,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:40:21,020 INFO L225 Difference]: With dead ends: 473 [2018-10-12 22:40:21,020 INFO L226 Difference]: Without dead ends: 473 [2018-10-12 22:40:21,022 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5462 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=3658, Invalid=17222, Unknown=0, NotChecked=0, Total=20880 [2018-10-12 22:40:21,022 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 473 states. [2018-10-12 22:40:21,026 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 473 to 453. [2018-10-12 22:40:21,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 453 states. [2018-10-12 22:40:21,027 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 453 states to 453 states and 454 transitions. [2018-10-12 22:40:21,027 INFO L78 Accepts]: Start accepts. Automaton has 453 states and 454 transitions. Word has length 438 [2018-10-12 22:40:21,028 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:40:21,028 INFO L481 AbstractCegarLoop]: Abstraction has 453 states and 454 transitions. [2018-10-12 22:40:21,028 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-12 22:40:21,028 INFO L276 IsEmpty]: Start isEmpty. Operand 453 states and 454 transitions. [2018-10-12 22:40:21,030 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 453 [2018-10-12 22:40:21,031 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:40:21,031 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-12 22:40:21,031 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:40:21,031 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:40:21,032 INFO L82 PathProgramCache]: Analyzing trace with hash -851770983, now seen corresponding path program 27 times [2018-10-12 22:40:21,032 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:40:21,061 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:40:22,994 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-12 22:40:22,995 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:40:22,995 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-12 22:40:22,995 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-12 22:40:22,996 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-12 22:40:22,996 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=486, Invalid=3174, Unknown=0, NotChecked=0, Total=3660 [2018-10-12 22:40:22,996 INFO L87 Difference]: Start difference. First operand 453 states and 454 transitions. Second operand 61 states. [2018-10-12 22:40:26,195 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:40:26,195 INFO L93 Difference]: Finished difference Result 681 states and 682 transitions. [2018-10-12 22:40:26,196 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-10-12 22:40:26,196 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 452 [2018-10-12 22:40:26,196 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:40:26,198 INFO L225 Difference]: With dead ends: 681 [2018-10-12 22:40:26,198 INFO L226 Difference]: Without dead ends: 483 [2018-10-12 22:40:26,200 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 131 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4649 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=2673, Invalid=14883, Unknown=0, NotChecked=0, Total=17556 [2018-10-12 22:40:26,201 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 483 states. [2018-10-12 22:40:26,205 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 483 to 469. [2018-10-12 22:40:26,205 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 469 states. [2018-10-12 22:40:26,206 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 469 states to 469 states and 470 transitions. [2018-10-12 22:40:26,206 INFO L78 Accepts]: Start accepts. Automaton has 469 states and 470 transitions. Word has length 452 [2018-10-12 22:40:26,207 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:40:26,207 INFO L481 AbstractCegarLoop]: Abstraction has 469 states and 470 transitions. [2018-10-12 22:40:26,207 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-12 22:40:26,207 INFO L276 IsEmpty]: Start isEmpty. Operand 469 states and 470 transitions. [2018-10-12 22:40:26,210 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 469 [2018-10-12 22:40:26,210 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:40:26,210 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-12 22:40:26,210 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:40:26,211 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:40:26,211 INFO L82 PathProgramCache]: Analyzing trace with hash -742846169, now seen corresponding path program 28 times [2018-10-12 22:40:26,211 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:40:26,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:40:28,060 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-12 22:40:28,061 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:40:28,061 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-12 22:40:28,061 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-12 22:40:28,062 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-12 22:40:28,062 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=444, Invalid=3716, Unknown=0, NotChecked=0, Total=4160 [2018-10-12 22:40:28,062 INFO L87 Difference]: Start difference. First operand 469 states and 470 transitions. Second operand 65 states. [2018-10-12 22:40:37,454 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:40:37,454 INFO L93 Difference]: Finished difference Result 503 states and 504 transitions. [2018-10-12 22:40:37,454 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 105 states. [2018-10-12 22:40:37,454 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 468 [2018-10-12 22:40:37,455 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:40:37,456 INFO L225 Difference]: With dead ends: 503 [2018-10-12 22:40:37,456 INFO L226 Difference]: Without dead ends: 503 [2018-10-12 22:40:37,457 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-12 22:40:37,457 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 503 states. [2018-10-12 22:40:37,460 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 503 to 483. [2018-10-12 22:40:37,460 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 483 states. [2018-10-12 22:40:37,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 483 states to 483 states and 484 transitions. [2018-10-12 22:40:37,461 INFO L78 Accepts]: Start accepts. Automaton has 483 states and 484 transitions. Word has length 468 [2018-10-12 22:40:37,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:40:37,462 INFO L481 AbstractCegarLoop]: Abstraction has 483 states and 484 transitions. [2018-10-12 22:40:37,462 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-12 22:40:37,462 INFO L276 IsEmpty]: Start isEmpty. Operand 483 states and 484 transitions. [2018-10-12 22:40:37,465 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 483 [2018-10-12 22:40:37,465 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:40:37,465 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-12 22:40:37,465 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:40:37,466 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:40:37,466 INFO L82 PathProgramCache]: Analyzing trace with hash -1639873673, now seen corresponding path program 29 times [2018-10-12 22:40:37,466 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:40:37,495 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:40:39,010 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-12 22:40:39,010 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:40:39,010 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-12 22:40:39,011 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-12 22:40:39,011 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-12 22:40:39,011 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=550, Invalid=3610, Unknown=0, NotChecked=0, Total=4160 [2018-10-12 22:40:39,012 INFO L87 Difference]: Start difference. First operand 483 states and 484 transitions. Second operand 65 states. [2018-10-12 22:40:42,957 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:40:42,957 INFO L93 Difference]: Finished difference Result 725 states and 726 transitions. [2018-10-12 22:40:42,958 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 95 states. [2018-10-12 22:40:42,958 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 482 [2018-10-12 22:40:42,959 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:40:42,960 INFO L225 Difference]: With dead ends: 725 [2018-10-12 22:40:42,960 INFO L226 Difference]: Without dead ends: 513 [2018-10-12 22:40:42,962 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5334 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=3042, Invalid=16980, Unknown=0, NotChecked=0, Total=20022 [2018-10-12 22:40:42,962 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 513 states. [2018-10-12 22:40:42,966 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 513 to 499. [2018-10-12 22:40:42,966 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 499 states. [2018-10-12 22:40:42,967 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 499 states to 499 states and 500 transitions. [2018-10-12 22:40:42,967 INFO L78 Accepts]: Start accepts. Automaton has 499 states and 500 transitions. Word has length 482 [2018-10-12 22:40:42,967 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:40:42,967 INFO L481 AbstractCegarLoop]: Abstraction has 499 states and 500 transitions. [2018-10-12 22:40:42,968 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-12 22:40:42,968 INFO L276 IsEmpty]: Start isEmpty. Operand 499 states and 500 transitions. [2018-10-12 22:40:42,970 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 499 [2018-10-12 22:40:42,971 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:40:42,971 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-12 22:40:42,971 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:40:42,971 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:40:42,972 INFO L82 PathProgramCache]: Analyzing trace with hash -249928059, now seen corresponding path program 30 times [2018-10-12 22:40:42,972 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:40:43,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:40:45,287 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-12 22:40:45,287 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:40:45,287 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-12 22:40:45,288 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-12 22:40:45,289 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-12 22:40:45,289 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=4213, Unknown=0, NotChecked=0, Total=4692 [2018-10-12 22:40:45,289 INFO L87 Difference]: Start difference. First operand 499 states and 500 transitions. Second operand 69 states. [2018-10-12 22:40:56,093 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:40:56,093 INFO L93 Difference]: Finished difference Result 533 states and 534 transitions. [2018-10-12 22:40:56,094 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 111 states. [2018-10-12 22:40:56,094 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 498 [2018-10-12 22:40:56,094 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:40:56,096 INFO L225 Difference]: With dead ends: 533 [2018-10-12 22:40:56,096 INFO L226 Difference]: Without dead ends: 533 [2018-10-12 22:40:56,097 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 160 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6815 ImplicationChecksByTransitivity, 8.1s TimeCoverageRelationStatistics Valid=4283, Invalid=21799, Unknown=0, NotChecked=0, Total=26082 [2018-10-12 22:40:56,098 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 533 states. [2018-10-12 22:40:56,101 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 533 to 513. [2018-10-12 22:40:56,101 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 513 states. [2018-10-12 22:40:56,102 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 513 states to 513 states and 514 transitions. [2018-10-12 22:40:56,102 INFO L78 Accepts]: Start accepts. Automaton has 513 states and 514 transitions. Word has length 498 [2018-10-12 22:40:56,103 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:40:56,103 INFO L481 AbstractCegarLoop]: Abstraction has 513 states and 514 transitions. [2018-10-12 22:40:56,103 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-12 22:40:56,103 INFO L276 IsEmpty]: Start isEmpty. Operand 513 states and 514 transitions. [2018-10-12 22:40:56,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 513 [2018-10-12 22:40:56,106 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:40:56,107 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-12 22:40:56,107 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:40:56,107 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:40:56,107 INFO L82 PathProgramCache]: Analyzing trace with hash 381361237, now seen corresponding path program 31 times [2018-10-12 22:40:56,108 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:40:56,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:40:58,560 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-12 22:40:58,561 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:40:58,561 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-12 22:40:58,561 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-12 22:40:58,562 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-12 22:40:58,562 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=618, Invalid=4074, Unknown=0, NotChecked=0, Total=4692 [2018-10-12 22:40:58,562 INFO L87 Difference]: Start difference. First operand 513 states and 514 transitions. Second operand 69 states. [2018-10-12 22:41:02,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:41:02,905 INFO L93 Difference]: Finished difference Result 769 states and 770 transitions. [2018-10-12 22:41:02,906 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 101 states. [2018-10-12 22:41:02,906 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 512 [2018-10-12 22:41:02,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:41:02,909 INFO L225 Difference]: With dead ends: 769 [2018-10-12 22:41:02,909 INFO L226 Difference]: Without dead ends: 543 [2018-10-12 22:41:02,911 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 149 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6066 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=3435, Invalid=19215, Unknown=0, NotChecked=0, Total=22650 [2018-10-12 22:41:02,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 543 states. [2018-10-12 22:41:02,915 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 543 to 529. [2018-10-12 22:41:02,915 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 529 states. [2018-10-12 22:41:02,916 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 529 states to 529 states and 530 transitions. [2018-10-12 22:41:02,916 INFO L78 Accepts]: Start accepts. Automaton has 529 states and 530 transitions. Word has length 512 [2018-10-12 22:41:02,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:41:02,917 INFO L481 AbstractCegarLoop]: Abstraction has 529 states and 530 transitions. [2018-10-12 22:41:02,917 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-12 22:41:02,917 INFO L276 IsEmpty]: Start isEmpty. Operand 529 states and 530 transitions. [2018-10-12 22:41:02,920 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 529 [2018-10-12 22:41:02,920 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:41:02,921 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-12 22:41:02,921 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:41:02,921 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:41:02,921 INFO L82 PathProgramCache]: Analyzing trace with hash 1843376867, now seen corresponding path program 32 times [2018-10-12 22:41:02,922 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:41:02,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:41:05,352 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-12 22:41:05,352 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:41:05,352 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-12 22:41:05,353 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-12 22:41:05,353 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-12 22:41:05,354 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=516, Invalid=4740, Unknown=0, NotChecked=0, Total=5256 [2018-10-12 22:41:05,354 INFO L87 Difference]: Start difference. First operand 529 states and 530 transitions. Second operand 73 states. [2018-10-12 22:41:17,760 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:41:17,760 INFO L93 Difference]: Finished difference Result 563 states and 564 transitions. [2018-10-12 22:41:17,761 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-10-12 22:41:17,761 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 528 [2018-10-12 22:41:17,761 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:41:17,763 INFO L225 Difference]: With dead ends: 563 [2018-10-12 22:41:17,763 INFO L226 Difference]: Without dead ends: 563 [2018-10-12 22:41:17,765 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 169 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7598 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=4636, Invalid=24434, Unknown=0, NotChecked=0, Total=29070 [2018-10-12 22:41:17,765 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 563 states. [2018-10-12 22:41:17,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 563 to 543. [2018-10-12 22:41:17,769 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 543 states. [2018-10-12 22:41:17,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 543 states to 543 states and 544 transitions. [2018-10-12 22:41:17,770 INFO L78 Accepts]: Start accepts. Automaton has 543 states and 544 transitions. Word has length 528 [2018-10-12 22:41:17,770 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:41:17,770 INFO L481 AbstractCegarLoop]: Abstraction has 543 states and 544 transitions. [2018-10-12 22:41:17,771 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-12 22:41:17,771 INFO L276 IsEmpty]: Start isEmpty. Operand 543 states and 544 transitions. [2018-10-12 22:41:17,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 543 [2018-10-12 22:41:17,775 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:41:17,775 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-12 22:41:17,775 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:41:17,775 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:41:17,776 INFO L82 PathProgramCache]: Analyzing trace with hash 2027711539, now seen corresponding path program 33 times [2018-10-12 22:41:17,777 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:41:17,814 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:41:20,587 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-12 22:41:20,587 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:41:20,587 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-12 22:41:20,588 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-12 22:41:20,588 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-12 22:41:20,588 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=690, Invalid=4566, Unknown=0, NotChecked=0, Total=5256 [2018-10-12 22:41:20,589 INFO L87 Difference]: Start difference. First operand 543 states and 544 transitions. Second operand 73 states. [2018-10-12 22:41:25,263 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:41:25,263 INFO L93 Difference]: Finished difference Result 813 states and 814 transitions. [2018-10-12 22:41:25,263 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 107 states. [2018-10-12 22:41:25,263 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 542 [2018-10-12 22:41:25,264 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:41:25,267 INFO L225 Difference]: With dead ends: 813 [2018-10-12 22:41:25,267 INFO L226 Difference]: Without dead ends: 573 [2018-10-12 22:41:25,268 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 158 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6845 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=3852, Invalid=21588, Unknown=0, NotChecked=0, Total=25440 [2018-10-12 22:41:25,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 573 states. [2018-10-12 22:41:25,272 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 573 to 559. [2018-10-12 22:41:25,272 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 559 states. [2018-10-12 22:41:25,272 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 559 states to 559 states and 560 transitions. [2018-10-12 22:41:25,273 INFO L78 Accepts]: Start accepts. Automaton has 559 states and 560 transitions. Word has length 542 [2018-10-12 22:41:25,273 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:41:25,273 INFO L481 AbstractCegarLoop]: Abstraction has 559 states and 560 transitions. [2018-10-12 22:41:25,273 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-12 22:41:25,273 INFO L276 IsEmpty]: Start isEmpty. Operand 559 states and 560 transitions. [2018-10-12 22:41:25,277 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 559 [2018-10-12 22:41:25,277 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:41:25,277 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-12 22:41:25,277 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:41:25,278 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:41:25,278 INFO L82 PathProgramCache]: Analyzing trace with hash -1217030591, now seen corresponding path program 34 times [2018-10-12 22:41:25,278 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:41:25,313 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:41:28,319 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-12 22:41:28,319 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:41:28,319 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-12 22:41:28,320 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-12 22:41:28,320 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-12 22:41:28,320 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=667, Invalid=5185, Unknown=0, NotChecked=0, Total=5852 [2018-10-12 22:41:28,321 INFO L87 Difference]: Start difference. First operand 559 states and 560 transitions. Second operand 77 states. [2018-10-12 22:41:40,713 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:41:40,713 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-12 22:41:40,713 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-10-12 22:41:40,713 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 558 [2018-10-12 22:41:40,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:41:40,715 INFO L225 Difference]: With dead ends: 593 [2018-10-12 22:41:40,715 INFO L226 Difference]: Without dead ends: 593 [2018-10-12 22:41:40,717 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 183 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9152 ImplicationChecksByTransitivity, 9.7s TimeCoverageRelationStatistics Valid=5956, Invalid=28084, Unknown=0, NotChecked=0, Total=34040 [2018-10-12 22:41:40,717 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 593 states. [2018-10-12 22:41:40,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 593 to 573. [2018-10-12 22:41:40,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 573 states. [2018-10-12 22:41:40,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 573 states to 573 states and 574 transitions. [2018-10-12 22:41:40,721 INFO L78 Accepts]: Start accepts. Automaton has 573 states and 574 transitions. Word has length 558 [2018-10-12 22:41:40,722 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:41:40,722 INFO L481 AbstractCegarLoop]: Abstraction has 573 states and 574 transitions. [2018-10-12 22:41:40,722 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-12 22:41:40,722 INFO L276 IsEmpty]: Start isEmpty. Operand 573 states and 574 transitions. [2018-10-12 22:41:40,725 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 573 [2018-10-12 22:41:40,726 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:41:40,726 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-12 22:41:40,726 INFO L424 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:41:40,726 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:41:40,727 INFO L82 PathProgramCache]: Analyzing trace with hash 1736053521, now seen corresponding path program 35 times [2018-10-12 22:41:40,727 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:41:40,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:41:43,043 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-12 22:41:43,044 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:41:43,044 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-12 22:41:43,045 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-12 22:41:43,045 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-12 22:41:43,045 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=766, Invalid=5086, Unknown=0, NotChecked=0, Total=5852 [2018-10-12 22:41:43,046 INFO L87 Difference]: Start difference. First operand 573 states and 574 transitions. Second operand 77 states. [2018-10-12 22:41:48,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:41:48,301 INFO L93 Difference]: Finished difference Result 857 states and 858 transitions. [2018-10-12 22:41:48,301 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 113 states. [2018-10-12 22:41:48,301 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 572 [2018-10-12 22:41:48,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:41:48,303 INFO L225 Difference]: With dead ends: 857 [2018-10-12 22:41:48,303 INFO L226 Difference]: Without dead ends: 603 [2018-10-12 22:41:48,305 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 167 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7671 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=4293, Invalid=24099, Unknown=0, NotChecked=0, Total=28392 [2018-10-12 22:41:48,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 603 states. [2018-10-12 22:41:48,309 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 603 to 589. [2018-10-12 22:41:48,309 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 589 states. [2018-10-12 22:41:48,310 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 589 states to 589 states and 590 transitions. [2018-10-12 22:41:48,310 INFO L78 Accepts]: Start accepts. Automaton has 589 states and 590 transitions. Word has length 572 [2018-10-12 22:41:48,310 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:41:48,310 INFO L481 AbstractCegarLoop]: Abstraction has 589 states and 590 transitions. [2018-10-12 22:41:48,310 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-12 22:41:48,310 INFO L276 IsEmpty]: Start isEmpty. Operand 589 states and 590 transitions. [2018-10-12 22:41:48,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 589 [2018-10-12 22:41:48,314 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:41:48,314 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-12 22:41:48,314 INFO L424 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:41:48,315 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:41:48,315 INFO L82 PathProgramCache]: Analyzing trace with hash 703115423, now seen corresponding path program 36 times [2018-10-12 22:41:48,315 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:41:48,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:41:51,201 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-12 22:41:51,202 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:41:51,202 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-12 22:41:51,203 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-12 22:41:51,203 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-12 22:41:51,203 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=708, Invalid=5772, Unknown=0, NotChecked=0, Total=6480 [2018-10-12 22:41:51,204 INFO L87 Difference]: Start difference. First operand 589 states and 590 transitions. Second operand 81 states. [2018-10-12 22:42:04,906 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:42:04,906 INFO L93 Difference]: Finished difference Result 623 states and 624 transitions. [2018-10-12 22:42:04,906 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 133 states. [2018-10-12 22:42:04,907 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 588 [2018-10-12 22:42:04,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:42:04,909 INFO L225 Difference]: With dead ends: 623 [2018-10-12 22:42:04,909 INFO L226 Difference]: Without dead ends: 623 [2018-10-12 22:42:04,911 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 191 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9935 ImplicationChecksByTransitivity, 10.4s TimeCoverageRelationStatistics Valid=6323, Invalid=30733, Unknown=0, NotChecked=0, Total=37056 [2018-10-12 22:42:04,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 623 states. [2018-10-12 22:42:04,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 623 to 603. [2018-10-12 22:42:04,914 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 603 states. [2018-10-12 22:42:04,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 603 states to 603 states and 604 transitions. [2018-10-12 22:42:04,915 INFO L78 Accepts]: Start accepts. Automaton has 603 states and 604 transitions. Word has length 588 [2018-10-12 22:42:04,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:42:04,916 INFO L481 AbstractCegarLoop]: Abstraction has 603 states and 604 transitions. [2018-10-12 22:42:04,916 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-12 22:42:04,916 INFO L276 IsEmpty]: Start isEmpty. Operand 603 states and 604 transitions. [2018-10-12 22:42:04,934 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 603 [2018-10-12 22:42:04,934 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:42:04,935 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-12 22:42:04,935 INFO L424 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:42:04,936 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:42:04,936 INFO L82 PathProgramCache]: Analyzing trace with hash 1544073455, now seen corresponding path program 37 times [2018-10-12 22:42:04,936 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:42:04,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:42:07,471 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-12 22:42:07,471 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:42:07,471 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-12 22:42:07,472 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-12 22:42:07,472 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-12 22:42:07,472 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=846, Invalid=5634, Unknown=0, NotChecked=0, Total=6480 [2018-10-12 22:42:07,473 INFO L87 Difference]: Start difference. First operand 603 states and 604 transitions. Second operand 81 states. [2018-10-12 22:42:13,319 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:42:13,320 INFO L93 Difference]: Finished difference Result 901 states and 902 transitions. [2018-10-12 22:42:13,320 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 119 states. [2018-10-12 22:42:13,320 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 602 [2018-10-12 22:42:13,321 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:42:13,323 INFO L225 Difference]: With dead ends: 901 [2018-10-12 22:42:13,323 INFO L226 Difference]: Without dead ends: 633 [2018-10-12 22:42:13,325 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 176 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8544 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=4758, Invalid=26748, Unknown=0, NotChecked=0, Total=31506 [2018-10-12 22:42:13,325 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 633 states. [2018-10-12 22:42:13,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 633 to 619. [2018-10-12 22:42:13,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 619 states. [2018-10-12 22:42:13,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 619 states to 619 states and 620 transitions. [2018-10-12 22:42:13,329 INFO L78 Accepts]: Start accepts. Automaton has 619 states and 620 transitions. Word has length 602 [2018-10-12 22:42:13,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:42:13,330 INFO L481 AbstractCegarLoop]: Abstraction has 619 states and 620 transitions. [2018-10-12 22:42:13,330 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-12 22:42:13,330 INFO L276 IsEmpty]: Start isEmpty. Operand 619 states and 620 transitions. [2018-10-12 22:42:13,334 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 619 [2018-10-12 22:42:13,334 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:42:13,334 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-12 22:42:13,335 INFO L424 AbstractCegarLoop]: === Iteration 41 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:42:13,335 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:42:13,335 INFO L82 PathProgramCache]: Analyzing trace with hash 98935293, now seen corresponding path program 38 times [2018-10-12 22:42:13,336 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:42:13,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:42:16,421 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-12 22:42:16,421 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:42:16,421 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-12 22:42:16,422 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-12 22:42:16,422 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-12 22:42:16,422 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=751, Invalid=6389, Unknown=0, NotChecked=0, Total=7140 [2018-10-12 22:42:16,423 INFO L87 Difference]: Start difference. First operand 619 states and 620 transitions. Second operand 85 states. [2018-10-12 22:42:31,658 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:42:31,658 INFO L93 Difference]: Finished difference Result 653 states and 654 transitions. [2018-10-12 22:42:31,658 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 139 states. [2018-10-12 22:42:31,658 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 618 [2018-10-12 22:42:31,659 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:42:31,660 INFO L225 Difference]: With dead ends: 653 [2018-10-12 22:42:31,660 INFO L226 Difference]: Without dead ends: 653 [2018-10-12 22:42:31,662 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-12 22:42:31,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 653 states. [2018-10-12 22:42:31,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 653 to 633. [2018-10-12 22:42:31,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 633 states. [2018-10-12 22:42:31,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 633 states to 633 states and 634 transitions. [2018-10-12 22:42:31,666 INFO L78 Accepts]: Start accepts. Automaton has 633 states and 634 transitions. Word has length 618 [2018-10-12 22:42:31,666 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:42:31,667 INFO L481 AbstractCegarLoop]: Abstraction has 633 states and 634 transitions. [2018-10-12 22:42:31,667 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-12 22:42:31,667 INFO L276 IsEmpty]: Start isEmpty. Operand 633 states and 634 transitions. [2018-10-12 22:42:31,670 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 633 [2018-10-12 22:42:31,670 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:42:31,670 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-12 22:42:31,670 INFO L424 AbstractCegarLoop]: === Iteration 42 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:42:31,670 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:42:31,670 INFO L82 PathProgramCache]: Analyzing trace with hash 480044493, now seen corresponding path program 39 times [2018-10-12 22:42:31,671 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:42:31,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:42:34,347 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-12 22:42:34,347 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:42:34,348 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-12 22:42:34,348 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-12 22:42:34,348 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-12 22:42:34,349 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=930, Invalid=6210, Unknown=0, NotChecked=0, Total=7140 [2018-10-12 22:42:34,349 INFO L87 Difference]: Start difference. First operand 633 states and 634 transitions. Second operand 85 states. [2018-10-12 22:42:40,664 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:42:40,664 INFO L93 Difference]: Finished difference Result 945 states and 946 transitions. [2018-10-12 22:42:40,665 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 125 states. [2018-10-12 22:42:40,665 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 632 [2018-10-12 22:42:40,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:42:40,668 INFO L225 Difference]: With dead ends: 945 [2018-10-12 22:42:40,668 INFO L226 Difference]: Without dead ends: 663 [2018-10-12 22:42:40,670 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9464 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=5247, Invalid=29535, Unknown=0, NotChecked=0, Total=34782 [2018-10-12 22:42:40,671 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 663 states. [2018-10-12 22:42:40,675 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 663 to 649. [2018-10-12 22:42:40,675 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 649 states. [2018-10-12 22:42:40,675 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 649 states to 649 states and 650 transitions. [2018-10-12 22:42:40,676 INFO L78 Accepts]: Start accepts. Automaton has 649 states and 650 transitions. Word has length 632 [2018-10-12 22:42:40,676 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:42:40,676 INFO L481 AbstractCegarLoop]: Abstraction has 649 states and 650 transitions. [2018-10-12 22:42:40,676 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-12 22:42:40,676 INFO L276 IsEmpty]: Start isEmpty. Operand 649 states and 650 transitions. [2018-10-12 22:42:40,680 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 649 [2018-10-12 22:42:40,680 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:42:40,681 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-12 22:42:40,681 INFO L424 AbstractCegarLoop]: === Iteration 43 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:42:40,681 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:42:40,681 INFO L82 PathProgramCache]: Analyzing trace with hash 1723402843, now seen corresponding path program 40 times [2018-10-12 22:42:40,682 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:42:40,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:42:44,564 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-12 22:42:44,564 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:42:44,565 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-12 22:42:44,565 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-12 22:42:44,566 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-12 22:42:44,566 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=684, Invalid=7148, Unknown=0, NotChecked=0, Total=7832 [2018-10-12 22:42:44,566 INFO L87 Difference]: Start difference. First operand 649 states and 650 transitions. Second operand 89 states. [2018-10-12 22:42:56,284 WARN L178 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 36 [2018-10-12 22:42:57,032 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-12 22:42:57,214 WARN L178 SmtUtils]: Spent 109.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-12 22:42:57,687 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-12 22:42:57,918 WARN L178 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-12 22:42:58,346 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-12 22:42:58,566 WARN L178 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-12 22:42:58,998 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-12 22:42:59,189 WARN L178 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 43 [2018-10-12 22:42:59,619 WARN L178 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 42 [2018-10-12 22:43:03,240 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:43:03,241 INFO L93 Difference]: Finished difference Result 683 states and 684 transitions. [2018-10-12 22:43:03,241 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 141 states. [2018-10-12 22:43:03,241 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 648 [2018-10-12 22:43:03,242 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:43:03,243 INFO L225 Difference]: With dead ends: 683 [2018-10-12 22:43:03,243 INFO L226 Difference]: Without dead ends: 683 [2018-10-12 22:43:03,245 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 205 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11140 ImplicationChecksByTransitivity, 13.4s TimeCoverageRelationStatistics Valid=6198, Invalid=36444, Unknown=0, NotChecked=0, Total=42642 [2018-10-12 22:43:03,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 683 states. [2018-10-12 22:43:03,249 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 683 to 663. [2018-10-12 22:43:03,249 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 663 states. [2018-10-12 22:43:03,250 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 663 states to 663 states and 664 transitions. [2018-10-12 22:43:03,250 INFO L78 Accepts]: Start accepts. Automaton has 663 states and 664 transitions. Word has length 648 [2018-10-12 22:43:03,251 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:43:03,251 INFO L481 AbstractCegarLoop]: Abstraction has 663 states and 664 transitions. [2018-10-12 22:43:03,251 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-12 22:43:03,251 INFO L276 IsEmpty]: Start isEmpty. Operand 663 states and 664 transitions. [2018-10-12 22:43:03,254 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 663 [2018-10-12 22:43:03,254 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:43:03,255 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-12 22:43:03,255 INFO L424 AbstractCegarLoop]: === Iteration 44 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:43:03,255 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:43:03,255 INFO L82 PathProgramCache]: Analyzing trace with hash 837505451, now seen corresponding path program 41 times [2018-10-12 22:43:03,255 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:43:03,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:43:06,092 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-12 22:43:06,092 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:43:06,092 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-12 22:43:06,093 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-12 22:43:06,094 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-12 22:43:06,094 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1018, Invalid=6814, Unknown=0, NotChecked=0, Total=7832 [2018-10-12 22:43:06,095 INFO L87 Difference]: Start difference. First operand 663 states and 664 transitions. Second operand 89 states. [2018-10-12 22:43:12,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:43:12,908 INFO L93 Difference]: Finished difference Result 989 states and 990 transitions. [2018-10-12 22:43:12,908 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-10-12 22:43:12,909 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 662 [2018-10-12 22:43:12,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:43:12,911 INFO L225 Difference]: With dead ends: 989 [2018-10-12 22:43:12,911 INFO L226 Difference]: Without dead ends: 693 [2018-10-12 22:43:12,914 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-12 22:43:12,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 693 states. [2018-10-12 22:43:12,918 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 693 to 679. [2018-10-12 22:43:12,918 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 679 states. [2018-10-12 22:43:12,918 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 679 states to 679 states and 680 transitions. [2018-10-12 22:43:12,919 INFO L78 Accepts]: Start accepts. Automaton has 679 states and 680 transitions. Word has length 662 [2018-10-12 22:43:12,919 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:43:12,919 INFO L481 AbstractCegarLoop]: Abstraction has 679 states and 680 transitions. [2018-10-12 22:43:12,919 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-12 22:43:12,919 INFO L276 IsEmpty]: Start isEmpty. Operand 679 states and 680 transitions. [2018-10-12 22:43:12,922 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 679 [2018-10-12 22:43:12,923 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:43:12,923 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-12 22:43:12,923 INFO L424 AbstractCegarLoop]: === Iteration 45 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:43:12,923 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:43:12,923 INFO L82 PathProgramCache]: Analyzing trace with hash 944736697, now seen corresponding path program 42 times [2018-10-12 22:43:12,924 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:43:12,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:43:16,839 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-12 22:43:16,840 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:43:16,840 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-12 22:43:16,840 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-12 22:43:16,841 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-12 22:43:16,841 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=987, Invalid=7569, Unknown=0, NotChecked=0, Total=8556 [2018-10-12 22:43:16,841 INFO L87 Difference]: Start difference. First operand 679 states and 680 transitions. Second operand 93 states. [2018-10-12 22:43:29,581 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:43:29,581 INFO L93 Difference]: Finished difference Result 713 states and 714 transitions. [2018-10-12 22:43:29,581 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 156 states. [2018-10-12 22:43:29,581 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 678 [2018-10-12 22:43:29,582 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:43:29,584 INFO L225 Difference]: With dead ends: 713 [2018-10-12 22:43:29,584 INFO L226 Difference]: Without dead ends: 713 [2018-10-12 22:43:29,586 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 223 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13786 ImplicationChecksByTransitivity, 13.1s TimeCoverageRelationStatistics Valid=8814, Invalid=41586, Unknown=0, NotChecked=0, Total=50400 [2018-10-12 22:43:29,586 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 713 states. [2018-10-12 22:43:29,590 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 713 to 693. [2018-10-12 22:43:29,590 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 693 states. [2018-10-12 22:43:29,590 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 693 states to 693 states and 694 transitions. [2018-10-12 22:43:29,591 INFO L78 Accepts]: Start accepts. Automaton has 693 states and 694 transitions. Word has length 678 [2018-10-12 22:43:29,591 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:43:29,591 INFO L481 AbstractCegarLoop]: Abstraction has 693 states and 694 transitions. [2018-10-12 22:43:29,591 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-12 22:43:29,591 INFO L276 IsEmpty]: Start isEmpty. Operand 693 states and 694 transitions. [2018-10-12 22:43:29,594 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 693 [2018-10-12 22:43:29,595 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:43:29,595 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-12 22:43:29,595 INFO L424 AbstractCegarLoop]: === Iteration 46 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:43:29,595 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:43:29,595 INFO L82 PathProgramCache]: Analyzing trace with hash 1565037705, now seen corresponding path program 43 times [2018-10-12 22:43:29,596 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:43:29,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:43:32,561 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-12 22:43:32,562 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:43:32,562 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-12 22:43:32,562 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-12 22:43:32,563 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-12 22:43:32,563 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1110, Invalid=7446, Unknown=0, NotChecked=0, Total=8556 [2018-10-12 22:43:32,563 INFO L87 Difference]: Start difference. First operand 693 states and 694 transitions. Second operand 93 states. [2018-10-12 22:43:40,188 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:43:40,188 INFO L93 Difference]: Finished difference Result 1033 states and 1034 transitions. [2018-10-12 22:43:40,188 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 137 states. [2018-10-12 22:43:40,188 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 692 [2018-10-12 22:43:40,189 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:43:40,191 INFO L225 Difference]: With dead ends: 1033 [2018-10-12 22:43:40,191 INFO L226 Difference]: Without dead ends: 723 [2018-10-12 22:43:40,193 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11445 ImplicationChecksByTransitivity, 6.6s TimeCoverageRelationStatistics Valid=6297, Invalid=35523, Unknown=0, NotChecked=0, Total=41820 [2018-10-12 22:43:40,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 723 states. [2018-10-12 22:43:40,198 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 723 to 709. [2018-10-12 22:43:40,198 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-10-12 22:43:40,199 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 710 transitions. [2018-10-12 22:43:40,199 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 710 transitions. Word has length 692 [2018-10-12 22:43:40,199 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:43:40,199 INFO L481 AbstractCegarLoop]: Abstraction has 709 states and 710 transitions. [2018-10-12 22:43:40,199 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-12 22:43:40,199 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 710 transitions. [2018-10-12 22:43:40,203 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 709 [2018-10-12 22:43:40,203 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:43:40,203 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-12 22:43:40,203 INFO L424 AbstractCegarLoop]: === Iteration 47 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:43:40,203 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:43:40,204 INFO L82 PathProgramCache]: Analyzing trace with hash 758497303, now seen corresponding path program 44 times [2018-10-12 22:43:40,204 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:43:40,239 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:43:43,939 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-12 22:43:43,939 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:43:43,940 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-12 22:43:43,940 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-12 22:43:43,941 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-12 22:43:43,941 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1036, Invalid=8276, Unknown=0, NotChecked=0, Total=9312 [2018-10-12 22:43:43,941 INFO L87 Difference]: Start difference. First operand 709 states and 710 transitions. Second operand 97 states. [2018-10-12 22:44:02,829 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:44:02,830 INFO L93 Difference]: Finished difference Result 743 states and 744 transitions. [2018-10-12 22:44:02,830 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-12 22:44:02,830 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 708 [2018-10-12 22:44:02,831 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:44:02,833 INFO L225 Difference]: With dead ends: 743 [2018-10-12 22:44:02,833 INFO L226 Difference]: Without dead ends: 743 [2018-10-12 22:44:02,836 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 231 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14741 ImplicationChecksByTransitivity, 13.9s TimeCoverageRelationStatistics Valid=9261, Invalid=44795, Unknown=0, NotChecked=0, Total=54056 [2018-10-12 22:44:02,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 743 states. [2018-10-12 22:44:02,841 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 743 to 723. [2018-10-12 22:44:02,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 723 states. [2018-10-12 22:44:02,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 723 states to 723 states and 724 transitions. [2018-10-12 22:44:02,842 INFO L78 Accepts]: Start accepts. Automaton has 723 states and 724 transitions. Word has length 708 [2018-10-12 22:44:02,843 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:44:02,843 INFO L481 AbstractCegarLoop]: Abstraction has 723 states and 724 transitions. [2018-10-12 22:44:02,843 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-12 22:44:02,843 INFO L276 IsEmpty]: Start isEmpty. Operand 723 states and 724 transitions. [2018-10-12 22:44:02,847 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 723 [2018-10-12 22:44:02,847 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:44:02,848 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-12 22:44:02,848 INFO L424 AbstractCegarLoop]: === Iteration 48 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:44:02,848 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:44:02,848 INFO L82 PathProgramCache]: Analyzing trace with hash 245976679, now seen corresponding path program 45 times [2018-10-12 22:44:02,849 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:44:02,888 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:44:06,273 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-12 22:44:06,274 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:44:06,274 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-12 22:44:06,275 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-12 22:44:06,275 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-12 22:44:06,275 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1206, Invalid=8106, Unknown=0, NotChecked=0, Total=9312 [2018-10-12 22:44:06,276 INFO L87 Difference]: Start difference. First operand 723 states and 724 transitions. Second operand 97 states. [2018-10-12 22:44:14,998 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:44:14,998 INFO L93 Difference]: Finished difference Result 1077 states and 1078 transitions. [2018-10-12 22:44:14,999 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 143 states. [2018-10-12 22:44:14,999 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 722 [2018-10-12 22:44:15,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:44:15,002 INFO L225 Difference]: With dead ends: 1077 [2018-10-12 22:44:15,002 INFO L226 Difference]: Without dead ends: 753 [2018-10-12 22:44:15,005 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 214 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 212 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12506 ImplicationChecksByTransitivity, 7.4s TimeCoverageRelationStatistics Valid=6858, Invalid=38724, Unknown=0, NotChecked=0, Total=45582 [2018-10-12 22:44:15,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 753 states. [2018-10-12 22:44:15,009 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 753 to 739. [2018-10-12 22:44:15,010 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-10-12 22:44:15,011 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 740 transitions. [2018-10-12 22:44:15,011 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 740 transitions. Word has length 722 [2018-10-12 22:44:15,011 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:44:15,011 INFO L481 AbstractCegarLoop]: Abstraction has 739 states and 740 transitions. [2018-10-12 22:44:15,012 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-12 22:44:15,012 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 740 transitions. [2018-10-12 22:44:15,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 739 [2018-10-12 22:44:15,017 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:44:15,017 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-12 22:44:15,018 INFO L424 AbstractCegarLoop]: === Iteration 49 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:44:15,018 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:44:15,018 INFO L82 PathProgramCache]: Analyzing trace with hash -1265087115, now seen corresponding path program 46 times [2018-10-12 22:44:15,019 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:44:15,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:44:19,215 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-12 22:44:19,215 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:44:19,215 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-12 22:44:19,216 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-12 22:44:19,216 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-12 22:44:19,217 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1087, Invalid=9013, Unknown=0, NotChecked=0, Total=10100 [2018-10-12 22:44:19,217 INFO L87 Difference]: Start difference. First operand 739 states and 740 transitions. Second operand 101 states. [2018-10-12 22:44:35,902 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:44:35,903 INFO L93 Difference]: Finished difference Result 773 states and 774 transitions. [2018-10-12 22:44:35,903 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-12 22:44:35,903 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 738 [2018-10-12 22:44:35,904 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:44:35,906 INFO L225 Difference]: With dead ends: 773 [2018-10-12 22:44:35,906 INFO L226 Difference]: Without dead ends: 773 [2018-10-12 22:44:35,909 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 240 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15883 ImplicationChecksByTransitivity, 16.0s TimeCoverageRelationStatistics Valid=9775, Invalid=48547, Unknown=0, NotChecked=0, Total=58322 [2018-10-12 22:44:35,909 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 773 states. [2018-10-12 22:44:35,913 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 773 to 753. [2018-10-12 22:44:35,913 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 753 states. [2018-10-12 22:44:35,914 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 753 states to 753 states and 754 transitions. [2018-10-12 22:44:35,914 INFO L78 Accepts]: Start accepts. Automaton has 753 states and 754 transitions. Word has length 738 [2018-10-12 22:44:35,915 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:44:35,915 INFO L481 AbstractCegarLoop]: Abstraction has 753 states and 754 transitions. [2018-10-12 22:44:35,915 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-12 22:44:35,915 INFO L276 IsEmpty]: Start isEmpty. Operand 753 states and 754 transitions. [2018-10-12 22:44:35,919 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 753 [2018-10-12 22:44:35,920 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:44:35,920 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-12 22:44:35,920 INFO L424 AbstractCegarLoop]: === Iteration 50 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:44:35,920 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:44:35,921 INFO L82 PathProgramCache]: Analyzing trace with hash -626909371, now seen corresponding path program 47 times [2018-10-12 22:44:35,921 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:44:35,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:44:39,249 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-12 22:44:39,249 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:44:39,250 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-12 22:44:39,250 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-12 22:44:39,251 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-12 22:44:39,251 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1306, Invalid=8794, Unknown=0, NotChecked=0, Total=10100 [2018-10-12 22:44:39,251 INFO L87 Difference]: Start difference. First operand 753 states and 754 transitions. Second operand 101 states. [2018-10-12 22:44:48,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:44:48,560 INFO L93 Difference]: Finished difference Result 1121 states and 1122 transitions. [2018-10-12 22:44:48,560 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 149 states. [2018-10-12 22:44:48,560 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 752 [2018-10-12 22:44:48,561 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:44:48,563 INFO L225 Difference]: With dead ends: 1121 [2018-10-12 22:44:48,563 INFO L226 Difference]: Without dead ends: 783 [2018-10-12 22:44:48,567 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 221 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13614 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=7443, Invalid=42063, Unknown=0, NotChecked=0, Total=49506 [2018-10-12 22:44:48,568 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 783 states. [2018-10-12 22:44:48,573 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 783 to 769. [2018-10-12 22:44:48,574 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 769 states. [2018-10-12 22:44:48,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 769 states to 769 states and 770 transitions. [2018-10-12 22:44:48,575 INFO L78 Accepts]: Start accepts. Automaton has 769 states and 770 transitions. Word has length 752 [2018-10-12 22:44:48,575 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:44:48,575 INFO L481 AbstractCegarLoop]: Abstraction has 769 states and 770 transitions. [2018-10-12 22:44:48,575 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-12 22:44:48,576 INFO L276 IsEmpty]: Start isEmpty. Operand 769 states and 770 transitions. [2018-10-12 22:44:48,580 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 769 [2018-10-12 22:44:48,580 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:44:48,581 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-12 22:44:48,581 INFO L424 AbstractCegarLoop]: === Iteration 51 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:44:48,581 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:44:48,581 INFO L82 PathProgramCache]: Analyzing trace with hash -263990829, now seen corresponding path program 48 times [2018-10-12 22:44:48,582 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:44:48,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:44:53,333 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-12 22:44:53,333 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:44:53,333 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-12 22:44:53,334 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-12 22:44:53,334 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-12 22:44:53,335 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1140, Invalid=9780, Unknown=0, NotChecked=0, Total=10920 [2018-10-12 22:44:53,335 INFO L87 Difference]: Start difference. First operand 769 states and 770 transitions. Second operand 105 states. [2018-10-12 22:45:07,644 WARN L178 SmtUtils]: Spent 119.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 42 [2018-10-12 22:45:15,363 WARN L178 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 41 [2018-10-12 22:45:16,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:45:16,901 INFO L93 Difference]: Finished difference Result 803 states and 804 transitions. [2018-10-12 22:45:16,901 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 173 states. [2018-10-12 22:45:16,901 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 768 [2018-10-12 22:45:16,902 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:45:16,904 INFO L225 Difference]: With dead ends: 803 [2018-10-12 22:45:16,905 INFO L226 Difference]: Without dead ends: 803 [2018-10-12 22:45:16,906 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 255 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 249 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17066 ImplicationChecksByTransitivity, 17.6s TimeCoverageRelationStatistics Valid=10304, Invalid=52446, Unknown=0, NotChecked=0, Total=62750 [2018-10-12 22:45:16,907 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 803 states. [2018-10-12 22:45:16,911 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 803 to 783. [2018-10-12 22:45:16,911 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 783 states. [2018-10-12 22:45:16,912 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 783 states to 783 states and 784 transitions. [2018-10-12 22:45:16,912 INFO L78 Accepts]: Start accepts. Automaton has 783 states and 784 transitions. Word has length 768 [2018-10-12 22:45:16,912 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:45:16,912 INFO L481 AbstractCegarLoop]: Abstraction has 783 states and 784 transitions. [2018-10-12 22:45:16,913 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-12 22:45:16,913 INFO L276 IsEmpty]: Start isEmpty. Operand 783 states and 784 transitions. [2018-10-12 22:45:16,918 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 783 [2018-10-12 22:45:16,918 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:45:16,919 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-12 22:45:16,919 INFO L424 AbstractCegarLoop]: === Iteration 52 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:45:16,919 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:45:16,919 INFO L82 PathProgramCache]: Analyzing trace with hash -261642461, now seen corresponding path program 49 times [2018-10-12 22:45:16,920 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:45:16,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:45:20,435 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-12 22:45:20,435 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:45:20,435 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-12 22:45:20,436 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-12 22:45:20,436 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-12 22:45:20,436 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1410, Invalid=9510, Unknown=0, NotChecked=0, Total=10920 [2018-10-12 22:45:20,436 INFO L87 Difference]: Start difference. First operand 783 states and 784 transitions. Second operand 105 states. [2018-10-12 22:45:30,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:45:30,338 INFO L93 Difference]: Finished difference Result 1165 states and 1166 transitions. [2018-10-12 22:45:30,338 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 155 states. [2018-10-12 22:45:30,338 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 782 [2018-10-12 22:45:30,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:45:30,341 INFO L225 Difference]: With dead ends: 1165 [2018-10-12 22:45:30,341 INFO L226 Difference]: Without dead ends: 813 [2018-10-12 22:45:30,344 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 232 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 230 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14769 ImplicationChecksByTransitivity, 8.1s TimeCoverageRelationStatistics Valid=8052, Invalid=45540, Unknown=0, NotChecked=0, Total=53592 [2018-10-12 22:45:30,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 813 states. [2018-10-12 22:45:30,349 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 813 to 799. [2018-10-12 22:45:30,349 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 799 states. [2018-10-12 22:45:30,350 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 799 states to 799 states and 800 transitions. [2018-10-12 22:45:30,350 INFO L78 Accepts]: Start accepts. Automaton has 799 states and 800 transitions. Word has length 782 [2018-10-12 22:45:30,350 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:45:30,350 INFO L481 AbstractCegarLoop]: Abstraction has 799 states and 800 transitions. [2018-10-12 22:45:30,350 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-12 22:45:30,350 INFO L276 IsEmpty]: Start isEmpty. Operand 799 states and 800 transitions. [2018-10-12 22:45:30,356 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 799 [2018-10-12 22:45:30,357 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:45:30,357 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-12 22:45:30,357 INFO L424 AbstractCegarLoop]: === Iteration 53 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:45:30,358 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:45:30,358 INFO L82 PathProgramCache]: Analyzing trace with hash -1432031951, now seen corresponding path program 50 times [2018-10-12 22:45:30,359 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:45:30,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:45:35,431 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-12 22:45:35,432 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:45:35,432 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-12 22:45:35,433 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-12 22:45:35,433 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-12 22:45:35,433 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1371, Invalid=10401, Unknown=0, NotChecked=0, Total=11772 [2018-10-12 22:45:35,433 INFO L87 Difference]: Start difference. First operand 799 states and 800 transitions. Second operand 109 states. [2018-10-12 22:45:54,568 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:45:54,569 INFO L93 Difference]: Finished difference Result 833 states and 834 transitions. [2018-10-12 22:45:54,569 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 184 states. [2018-10-12 22:45:54,569 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 798 [2018-10-12 22:45:54,570 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:45:54,572 INFO L225 Difference]: With dead ends: 833 [2018-10-12 22:45:54,572 INFO L226 Difference]: Without dead ends: 833 [2018-10-12 22:45:54,574 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 269 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 263 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19364 ImplicationChecksByTransitivity, 17.6s TimeCoverageRelationStatistics Valid=12232, Invalid=57728, Unknown=0, NotChecked=0, Total=69960 [2018-10-12 22:45:54,575 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 833 states. [2018-10-12 22:45:54,579 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 833 to 813. [2018-10-12 22:45:54,579 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 813 states. [2018-10-12 22:45:54,580 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 813 states to 813 states and 814 transitions. [2018-10-12 22:45:54,580 INFO L78 Accepts]: Start accepts. Automaton has 813 states and 814 transitions. Word has length 798 [2018-10-12 22:45:54,580 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:45:54,581 INFO L481 AbstractCegarLoop]: Abstraction has 813 states and 814 transitions. [2018-10-12 22:45:54,581 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-12 22:45:54,581 INFO L276 IsEmpty]: Start isEmpty. Operand 813 states and 814 transitions. [2018-10-12 22:45:54,585 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 813 [2018-10-12 22:45:54,585 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:45:54,586 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-12 22:45:54,586 INFO L424 AbstractCegarLoop]: === Iteration 54 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:45:54,586 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:45:54,586 INFO L82 PathProgramCache]: Analyzing trace with hash -1882290687, now seen corresponding path program 51 times [2018-10-12 22:45:54,587 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:45:54,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:45:58,638 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-12 22:45:58,639 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:45:58,639 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-12 22:45:58,639 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-12 22:45:58,640 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-12 22:45:58,640 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1518, Invalid=10254, Unknown=0, NotChecked=0, Total=11772 [2018-10-12 22:45:58,640 INFO L87 Difference]: Start difference. First operand 813 states and 814 transitions. Second operand 109 states. [2018-10-12 22:46:09,367 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:46:09,367 INFO L93 Difference]: Finished difference Result 1209 states and 1210 transitions. [2018-10-12 22:46:09,367 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-12 22:46:09,368 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 812 [2018-10-12 22:46:09,368 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:46:09,371 INFO L225 Difference]: With dead ends: 1209 [2018-10-12 22:46:09,371 INFO L226 Difference]: Without dead ends: 843 [2018-10-12 22:46:09,374 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 239 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15971 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=8685, Invalid=49155, Unknown=0, NotChecked=0, Total=57840 [2018-10-12 22:46:09,374 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 843 states. [2018-10-12 22:46:09,378 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 843 to 829. [2018-10-12 22:46:09,379 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 829 states. [2018-10-12 22:46:09,380 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 829 states to 829 states and 830 transitions. [2018-10-12 22:46:09,380 INFO L78 Accepts]: Start accepts. Automaton has 829 states and 830 transitions. Word has length 812 [2018-10-12 22:46:09,380 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:46:09,380 INFO L481 AbstractCegarLoop]: Abstraction has 829 states and 830 transitions. [2018-10-12 22:46:09,380 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-12 22:46:09,380 INFO L276 IsEmpty]: Start isEmpty. Operand 829 states and 830 transitions. [2018-10-12 22:46:09,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 829 [2018-10-12 22:46:09,387 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:46:09,388 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-12 22:46:09,388 INFO L424 AbstractCegarLoop]: === Iteration 55 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:46:09,388 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:46:09,388 INFO L82 PathProgramCache]: Analyzing trace with hash 1288191887, now seen corresponding path program 52 times [2018-10-12 22:46:09,389 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:46:09,439 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:46:14,693 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-12 22:46:14,693 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:46:14,694 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-12 22:46:14,694 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-12 22:46:14,695 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-12 22:46:14,695 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1428, Invalid=11228, Unknown=0, NotChecked=0, Total=12656 [2018-10-12 22:46:14,695 INFO L87 Difference]: Start difference. First operand 829 states and 830 transitions. Second operand 113 states. [2018-10-12 22:46:34,496 WARN L178 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 45 DAG size of output: 35 [2018-10-12 22:46:40,419 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:46:40,420 INFO L93 Difference]: Finished difference Result 863 states and 864 transitions. [2018-10-12 22:46:40,420 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-10-12 22:46:40,420 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 828 [2018-10-12 22:46:40,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:46:40,424 INFO L225 Difference]: With dead ends: 863 [2018-10-12 22:46:40,424 INFO L226 Difference]: Without dead ends: 863 [2018-10-12 22:46:40,427 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 277 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 271 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20491 ImplicationChecksByTransitivity, 19.0s TimeCoverageRelationStatistics Valid=12759, Invalid=61497, Unknown=0, NotChecked=0, Total=74256 [2018-10-12 22:46:40,427 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 863 states. [2018-10-12 22:46:40,431 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 863 to 843. [2018-10-12 22:46:40,432 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 843 states. [2018-10-12 22:46:40,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 843 states to 843 states and 844 transitions. [2018-10-12 22:46:40,432 INFO L78 Accepts]: Start accepts. Automaton has 843 states and 844 transitions. Word has length 828 [2018-10-12 22:46:40,433 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:46:40,433 INFO L481 AbstractCegarLoop]: Abstraction has 843 states and 844 transitions. [2018-10-12 22:46:40,433 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-12 22:46:40,433 INFO L276 IsEmpty]: Start isEmpty. Operand 843 states and 844 transitions. [2018-10-12 22:46:40,438 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 843 [2018-10-12 22:46:40,438 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:46:40,438 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-12 22:46:40,439 INFO L424 AbstractCegarLoop]: === Iteration 56 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:46:40,439 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:46:40,439 INFO L82 PathProgramCache]: Analyzing trace with hash 2135645151, now seen corresponding path program 53 times [2018-10-12 22:46:40,439 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:46:40,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:46:44,825 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-12 22:46:44,825 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:46:44,826 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-12 22:46:44,826 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-12 22:46:44,827 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-12 22:46:44,827 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1630, Invalid=11026, Unknown=0, NotChecked=0, Total=12656 [2018-10-12 22:46:44,828 INFO L87 Difference]: Start difference. First operand 843 states and 844 transitions. Second operand 113 states. [2018-10-12 22:46:56,357 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:46:56,357 INFO L93 Difference]: Finished difference Result 1253 states and 1254 transitions. [2018-10-12 22:46:56,357 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-12 22:46:56,357 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 842 [2018-10-12 22:46:56,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:46:56,361 INFO L225 Difference]: With dead ends: 1253 [2018-10-12 22:46:56,361 INFO L226 Difference]: Without dead ends: 873 [2018-10-12 22:46:56,363 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 248 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17220 ImplicationChecksByTransitivity, 9.7s TimeCoverageRelationStatistics Valid=9342, Invalid=52908, Unknown=0, NotChecked=0, Total=62250 [2018-10-12 22:46:56,363 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 873 states. [2018-10-12 22:46:56,368 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 873 to 859. [2018-10-12 22:46:56,368 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 859 states. [2018-10-12 22:46:56,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 859 states to 859 states and 860 transitions. [2018-10-12 22:46:56,369 INFO L78 Accepts]: Start accepts. Automaton has 859 states and 860 transitions. Word has length 842 [2018-10-12 22:46:56,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:46:56,369 INFO L481 AbstractCegarLoop]: Abstraction has 859 states and 860 transitions. [2018-10-12 22:46:56,369 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-12 22:46:56,369 INFO L276 IsEmpty]: Start isEmpty. Operand 859 states and 860 transitions. [2018-10-12 22:46:56,375 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 859 [2018-10-12 22:46:56,375 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:46:56,375 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-12 22:46:56,375 INFO L424 AbstractCegarLoop]: === Iteration 57 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:46:56,375 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:46:56,376 INFO L82 PathProgramCache]: Analyzing trace with hash -732272403, now seen corresponding path program 54 times [2018-10-12 22:46:56,376 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:46:56,425 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:47:01,676 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-12 22:47:01,676 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:47:01,676 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [117] total 117 [2018-10-12 22:47:01,677 INFO L460 AbstractCegarLoop]: Interpolant automaton has 117 states [2018-10-12 22:47:01,677 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 117 interpolants. [2018-10-12 22:47:01,678 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1487, Invalid=12085, Unknown=0, NotChecked=0, Total=13572 [2018-10-12 22:47:01,678 INFO L87 Difference]: Start difference. First operand 859 states and 860 transitions. Second operand 117 states.