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/ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-502d2f4 [2018-10-12 22:28:59,252 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-12 22:28:59,254 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-12 22:28:59,271 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-12 22:28:59,271 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-12 22:28:59,272 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-12 22:28:59,274 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-12 22:28:59,277 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-12 22:28:59,279 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-12 22:28:59,286 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-12 22:28:59,286 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-12 22:28:59,287 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-12 22:28:59,288 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-12 22:28:59,288 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-12 22:28:59,290 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-12 22:28:59,290 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-12 22:28:59,291 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-12 22:28:59,293 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-12 22:28:59,294 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-12 22:28:59,296 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-12 22:28:59,297 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-12 22:28:59,298 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-12 22:28:59,300 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-12 22:28:59,301 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-12 22:28:59,301 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-12 22:28:59,301 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-12 22:28:59,302 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-12 22:28:59,303 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-12 22:28:59,304 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-12 22:28:59,305 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-12 22:28:59,305 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-12 22:28:59,305 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-12 22:28:59,306 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-12 22:28:59,306 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-12 22:28:59,307 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-12 22:28:59,307 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-12 22:28:59,308 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:28:59,323 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-12 22:28:59,324 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-12 22:28:59,325 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-12 22:28:59,325 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-12 22:28:59,325 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-12 22:28:59,325 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-12 22:28:59,329 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-12 22:28:59,329 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-12 22:28:59,329 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-12 22:28:59,329 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-12 22:28:59,329 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-12 22:28:59,330 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-12 22:28:59,330 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-12 22:28:59,331 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-12 22:28:59,332 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-12 22:28:59,398 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-12 22:28:59,416 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-12 22:28:59,421 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-12 22:28:59,423 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-12 22:28:59,424 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-12 22:28:59,424 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl [2018-10-12 22:28:59,425 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl' [2018-10-12 22:28:59,511 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-12 22:28:59,512 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-10-12 22:28:59,513 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-12 22:28:59,513 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-12 22:28:59,513 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-12 22:28:59,541 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 12.10 10:28:59" (1/1) ... [2018-10-12 22:28:59,543 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 12.10 10:28:59" (1/1) ... [2018-10-12 22:28:59,561 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 12.10 10:28:59" (1/1) ... [2018-10-12 22:28:59,562 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 12.10 10:28:59" (1/1) ... [2018-10-12 22:28:59,572 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 12.10 10:28:59" (1/1) ... [2018-10-12 22:28:59,580 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 12.10 10:28:59" (1/1) ... [2018-10-12 22:28:59,585 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 12.10 10:28:59" (1/1) ... [2018-10-12 22:28:59,591 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-12 22:28:59,592 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-12 22:28:59,592 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-12 22:28:59,592 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-12 22:28:59,597 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 12.10 10:28:59" (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:28:59,680 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2018-10-12 22:28:59,680 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-12 22:28:59,681 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-12 22:29:00,469 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-12 22:29:00,470 INFO L202 PluginConnector]: Adding new model ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 10:29:00 BoogieIcfgContainer [2018-10-12 22:29:00,470 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-12 22:29:00,471 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-10-12 22:29:00,471 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-10-12 22:29:00,472 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-10-12 22:29:00,475 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 10:29:00" (1/1) ... [2018-10-12 22:29:00,484 INFO L137 apSepIcfgTransformer]: HeapSepIcfgTransformer: Starting heap partitioning [2018-10-12 22:29:00,484 INFO L138 apSepIcfgTransformer]: To be partitioned heap arrays found [#memory_int] [2018-10-12 22:29:00,527 INFO L191 apSepIcfgTransformer]: Heap separator: starting loc-array-style preprocessing [2018-10-12 22:29:00,581 INFO L219 apSepIcfgTransformer]: finished MemlocArrayUpdater [2018-10-12 22:29:00,597 INFO L282 apSepIcfgTransformer]: finished preprocessing for the equality analysis [2018-10-12 22:29:00,663 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=1) [2018-10-12 22:30:22,576 INFO L315 AbstractInterpreter]: Visited 110 different actions 668 times. Merged at 91 different actions 538 times. Widened at 6 different actions 15 times. Found 19 fixpoints after 9 different actions. Largest state had 0 variables. [2018-10-12 22:30:22,579 INFO L306 apSepIcfgTransformer]: finished equality analysis [2018-10-12 22:30:22,583 INFO L318 apSepIcfgTransformer]: Finished detection of select terms ("array reads") [2018-10-12 22:30:22,650 WARN L152 HeapPartitionManager]: No literal set constraint found for loc-array access (select |v_#locv_ULTIMATE.start_write~int_old_#memory_int_2_1_1| |v_ULTIMATE.start_write~int_#ptr.base_6|) at (assume #memory_int == write~int_old_#memory_int[write~int_#ptr.base := write~int_old_#memory_int[write~int_#ptr.base][write~int_#ptr.offset := write~int_#value]];) [2018-10-12 22:30:22,668 WARN L152 HeapPartitionManager]: No literal set constraint found for loc-array access (select |#loc_#memory_int_(Array-Int-#locsort1)| |v_ULTIMATE.start_read~int_#ptr.base_6|) at (assume #memory_int[read~int_#ptr.base][read~int_#ptr.offset] == read~int_#value;) [2018-10-12 22:30:22,668 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_6|) |v_ULTIMATE.start_read~int_#ptr.offset_4|) at (assume #memory_int[read~int_#ptr.base][read~int_#ptr.offset] == read~int_#value;) [2018-10-12 22:30:22,696 WARN L152 HeapPartitionManager]: No literal set constraint found for loc-array access (select |v_#locv_ULTIMATE.start_write~int_old_#memory_int_4_1_1| |v_ULTIMATE.start_write~int_#ptr.base_13|) at (assume write~int_old_#memory_int[write~int_#ptr.base := write~int_old_#memory_int[write~int_#ptr.base][write~int_#ptr.offset := write~int_#value]] == #memory_int;) [2018-10-12 22:30:22,706 WARN L152 HeapPartitionManager]: No literal set constraint found for loc-array access (select |#loc_#memory_int_(Array-Int-#locsort1)| |v_ULTIMATE.start_read~int_#ptr.base_12|) at (assume #memory_int[read~int_#ptr.base][read~int_#ptr.offset] == read~int_#value;) [2018-10-12 22:30:22,707 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_12|) |v_ULTIMATE.start_read~int_#ptr.offset_8|) at (assume #memory_int[read~int_#ptr.base][read~int_#ptr.offset] == read~int_#value;) [2018-10-12 22:30:22,708 INFO L232 HeapPartitionManager]: partitioning result: [2018-10-12 22:30:22,709 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-12 22:30:22,709 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-12 22:30:22,709 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 2 [2018-10-12 22:30:22,710 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-12 22:30:22,710 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-12 22:30:22,710 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 2 [2018-10-12 22:30:22,710 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-12 22:30:22,711 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-12 22:30:22,711 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-12 22:30:22,711 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 2 [2018-10-12 22:30:22,711 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-12 22:30:22,712 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-12 22:30:22,712 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 2 [2018-10-12 22:30:22,712 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-12 22:30:22,713 INFO L145 ransitionTransformer]: executing heap partitioning transformation [2018-10-12 22:30:22,737 INFO L202 PluginConnector]: Adding new model ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 12.10 10:30:22 BasicIcfg [2018-10-12 22:30:22,738 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-10-12 22:30:22,742 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-12 22:30:22,742 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-12 22:30:22,747 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-12 22:30:22,748 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 12.10 10:28:59" (1/3) ... [2018-10-12 22:30:22,749 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@50e87b16 and model type ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 12.10 10:30:22, skipping insertion in model container [2018-10-12 22:30:22,750 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 12.10 10:29:00" (2/3) ... [2018-10-12 22:30:22,750 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@50e87b16 and model type ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 12.10 10:30:22, skipping insertion in model container [2018-10-12 22:30:22,750 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 12.10 10:30:22" (3/3) ... [2018-10-12 22:30:22,753 INFO L112 eAbstractionObserver]: Analyzing ICFG memPartitionedIcfg [2018-10-12 22:30:22,763 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-12 22:30:22,773 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-12 22:30:22,788 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-12 22:30:22,808 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-12 22:30:22,809 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-12 22:30:22,809 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-12 22:30:22,809 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-12 22:30:22,809 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-12 22:30:22,809 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-12 22:30:22,810 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-12 22:30:22,810 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-12 22:30:22,810 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-12 22:30:22,822 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states. [2018-10-12 22:30:22,830 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-10-12 22:30:22,830 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:22,831 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:30:22,832 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:22,836 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:22,837 INFO L82 PathProgramCache]: Analyzing trace with hash 314183860, now seen corresponding path program 1 times [2018-10-12 22:30:22,895 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:22,967 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:23,809 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:30:23,812 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-12 22:30:23,812 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2018-10-12 22:30:23,816 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-12 22:30:23,828 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-12 22:30:23,829 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2018-10-12 22:30:23,831 INFO L87 Difference]: Start difference. First operand 108 states. Second operand 12 states. [2018-10-12 22:30:24,520 WARN L178 SmtUtils]: Spent 193.00 ms on a formula simplification that was a NOOP. DAG size: 30 [2018-10-12 22:30:24,816 WARN L178 SmtUtils]: Spent 161.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-10-12 22:30:25,084 WARN L178 SmtUtils]: Spent 130.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-10-12 22:30:25,546 WARN L178 SmtUtils]: Spent 150.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-10-12 22:30:25,920 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:25,921 INFO L93 Difference]: Finished difference Result 204 states and 208 transitions. [2018-10-12 22:30:25,921 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-10-12 22:30:25,923 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 64 [2018-10-12 22:30:25,924 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:25,938 INFO L225 Difference]: With dead ends: 204 [2018-10-12 22:30:25,939 INFO L226 Difference]: Without dead ends: 204 [2018-10-12 22:30:25,941 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=98, Invalid=322, Unknown=0, NotChecked=0, Total=420 [2018-10-12 22:30:25,960 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2018-10-12 22:30:25,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 185. [2018-10-12 22:30:25,989 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 185 states. [2018-10-12 22:30:25,991 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 189 transitions. [2018-10-12 22:30:25,992 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 189 transitions. Word has length 64 [2018-10-12 22:30:25,993 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:25,993 INFO L481 AbstractCegarLoop]: Abstraction has 185 states and 189 transitions. [2018-10-12 22:30:25,993 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-12 22:30:25,993 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 189 transitions. [2018-10-12 22:30:25,998 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2018-10-12 22:30:25,999 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:25,999 INFO L375 BasicCegarLoop]: trace histogram [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, 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] [2018-10-12 22:30:25,999 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:26,000 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:26,000 INFO L82 PathProgramCache]: Analyzing trace with hash 1971731846, now seen corresponding path program 1 times [2018-10-12 22:30:26,001 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:26,053 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:26,279 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 26 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-12 22:30:26,279 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:26,279 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2018-10-12 22:30:26,281 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-10-12 22:30:26,281 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-10-12 22:30:26,281 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2018-10-12 22:30:26,282 INFO L87 Difference]: Start difference. First operand 185 states and 189 transitions. Second operand 8 states. [2018-10-12 22:30:26,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:26,625 INFO L93 Difference]: Finished difference Result 306 states and 312 transitions. [2018-10-12 22:30:26,630 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-12 22:30:26,630 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 118 [2018-10-12 22:30:26,631 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:26,636 INFO L225 Difference]: With dead ends: 306 [2018-10-12 22:30:26,636 INFO L226 Difference]: Without dead ends: 306 [2018-10-12 22:30:26,637 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2018-10-12 22:30:26,638 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 306 states. [2018-10-12 22:30:26,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 306 to 213. [2018-10-12 22:30:26,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-10-12 22:30:26,670 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 217 transitions. [2018-10-12 22:30:26,670 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 217 transitions. Word has length 118 [2018-10-12 22:30:26,671 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:26,671 INFO L481 AbstractCegarLoop]: Abstraction has 213 states and 217 transitions. [2018-10-12 22:30:26,671 INFO L482 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-10-12 22:30:26,671 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 217 transitions. [2018-10-12 22:30:26,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 140 [2018-10-12 22:30:26,679 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:26,679 INFO L375 BasicCegarLoop]: trace histogram [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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:30:26,681 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:26,681 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:26,681 INFO L82 PathProgramCache]: Analyzing trace with hash -2131493066, now seen corresponding path program 1 times [2018-10-12 22:30:26,682 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:26,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:26,944 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 17 proven. 30 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-10-12 22:30:26,945 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:26,945 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2018-10-12 22:30:26,946 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-10-12 22:30:26,946 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-10-12 22:30:26,946 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2018-10-12 22:30:26,947 INFO L87 Difference]: Start difference. First operand 213 states and 217 transitions. Second operand 10 states. [2018-10-12 22:30:27,459 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:27,459 INFO L93 Difference]: Finished difference Result 339 states and 346 transitions. [2018-10-12 22:30:27,459 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-12 22:30:27,460 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 139 [2018-10-12 22:30:27,460 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:27,462 INFO L225 Difference]: With dead ends: 339 [2018-10-12 22:30:27,462 INFO L226 Difference]: Without dead ends: 339 [2018-10-12 22:30:27,463 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=90, Invalid=290, Unknown=0, NotChecked=0, Total=380 [2018-10-12 22:30:27,464 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 339 states. [2018-10-12 22:30:27,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 339 to 243. [2018-10-12 22:30:27,476 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 243 states. [2018-10-12 22:30:27,477 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 248 transitions. [2018-10-12 22:30:27,477 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 248 transitions. Word has length 139 [2018-10-12 22:30:27,478 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:27,478 INFO L481 AbstractCegarLoop]: Abstraction has 243 states and 248 transitions. [2018-10-12 22:30:27,478 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-10-12 22:30:27,478 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 248 transitions. [2018-10-12 22:30:27,481 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 154 [2018-10-12 22:30:27,481 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:27,481 INFO L375 BasicCegarLoop]: trace histogram [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, 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, 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:30:27,482 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:27,482 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:27,482 INFO L82 PathProgramCache]: Analyzing trace with hash 576856674, now seen corresponding path program 1 times [2018-10-12 22:30:27,483 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:27,512 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:28,334 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 49 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-10-12 22:30:28,334 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:28,334 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2018-10-12 22:30:28,335 INFO L460 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-12 22:30:28,335 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-12 22:30:28,335 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=441, Unknown=0, NotChecked=0, Total=506 [2018-10-12 22:30:28,336 INFO L87 Difference]: Start difference. First operand 243 states and 248 transitions. Second operand 23 states. [2018-10-12 22:30:30,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:30,826 INFO L93 Difference]: Finished difference Result 296 states and 302 transitions. [2018-10-12 22:30:30,828 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-12 22:30:30,828 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 153 [2018-10-12 22:30:30,829 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:30,832 INFO L225 Difference]: With dead ends: 296 [2018-10-12 22:30:30,832 INFO L226 Difference]: Without dead ends: 296 [2018-10-12 22:30:30,833 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 5 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 389 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=243, Invalid=1563, Unknown=0, NotChecked=0, Total=1806 [2018-10-12 22:30:30,833 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 296 states. [2018-10-12 22:30:30,851 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 296 to 274. [2018-10-12 22:30:30,854 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 274 states. [2018-10-12 22:30:30,855 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 280 transitions. [2018-10-12 22:30:30,855 INFO L78 Accepts]: Start accepts. Automaton has 274 states and 280 transitions. Word has length 153 [2018-10-12 22:30:30,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:30,858 INFO L481 AbstractCegarLoop]: Abstraction has 274 states and 280 transitions. [2018-10-12 22:30:30,858 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-12 22:30:30,859 INFO L276 IsEmpty]: Start isEmpty. Operand 274 states and 280 transitions. [2018-10-12 22:30:30,862 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 208 [2018-10-12 22:30:30,866 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:30,866 INFO L375 BasicCegarLoop]: trace histogram [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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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:30:30,867 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:30,867 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:30,867 INFO L82 PathProgramCache]: Analyzing trace with hash -399933260, now seen corresponding path program 2 times [2018-10-12 22:30:30,871 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:30,902 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:31,183 INFO L134 CoverageAnalysis]: Checked inductivity of 152 backedges. 56 proven. 94 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-12 22:30:31,183 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:31,183 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2018-10-12 22:30:31,184 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-10-12 22:30:31,184 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-10-12 22:30:31,184 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-10-12 22:30:31,185 INFO L87 Difference]: Start difference. First operand 274 states and 280 transitions. Second operand 10 states. [2018-10-12 22:30:31,462 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:31,462 INFO L93 Difference]: Finished difference Result 306 states and 312 transitions. [2018-10-12 22:30:31,462 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-10-12 22:30:31,463 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 207 [2018-10-12 22:30:31,463 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:31,466 INFO L225 Difference]: With dead ends: 306 [2018-10-12 22:30:31,466 INFO L226 Difference]: Without dead ends: 306 [2018-10-12 22:30:31,467 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2018-10-12 22:30:31,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 306 states. [2018-10-12 22:30:31,472 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 306 to 275. [2018-10-12 22:30:31,472 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 275 states. [2018-10-12 22:30:31,473 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 275 states to 275 states and 281 transitions. [2018-10-12 22:30:31,474 INFO L78 Accepts]: Start accepts. Automaton has 275 states and 281 transitions. Word has length 207 [2018-10-12 22:30:31,474 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:31,474 INFO L481 AbstractCegarLoop]: Abstraction has 275 states and 281 transitions. [2018-10-12 22:30:31,474 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-10-12 22:30:31,474 INFO L276 IsEmpty]: Start isEmpty. Operand 275 states and 281 transitions. [2018-10-12 22:30:31,477 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 229 [2018-10-12 22:30:31,478 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:31,478 INFO L375 BasicCegarLoop]: trace histogram [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, 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, 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] [2018-10-12 22:30:31,478 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:31,478 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:31,479 INFO L82 PathProgramCache]: Analyzing trace with hash 1309680840, now seen corresponding path program 3 times [2018-10-12 22:30:31,479 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:31,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:32,288 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 56 proven. 118 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-12 22:30:32,288 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:32,289 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-10-12 22:30:32,289 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-12 22:30:32,289 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-12 22:30:32,289 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=107, Unknown=0, NotChecked=0, Total=132 [2018-10-12 22:30:32,290 INFO L87 Difference]: Start difference. First operand 275 states and 281 transitions. Second operand 12 states. [2018-10-12 22:30:32,823 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:32,823 INFO L93 Difference]: Finished difference Result 308 states and 314 transitions. [2018-10-12 22:30:32,823 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-12 22:30:32,824 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 228 [2018-10-12 22:30:32,824 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:32,826 INFO L225 Difference]: With dead ends: 308 [2018-10-12 22:30:32,827 INFO L226 Difference]: Without dead ends: 308 [2018-10-12 22:30:32,828 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=123, Invalid=477, Unknown=0, NotChecked=0, Total=600 [2018-10-12 22:30:32,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 308 states. [2018-10-12 22:30:32,832 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 308 to 296. [2018-10-12 22:30:32,832 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 296 states. [2018-10-12 22:30:32,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 296 states to 296 states and 302 transitions. [2018-10-12 22:30:32,834 INFO L78 Accepts]: Start accepts. Automaton has 296 states and 302 transitions. Word has length 228 [2018-10-12 22:30:32,834 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:32,834 INFO L481 AbstractCegarLoop]: Abstraction has 296 states and 302 transitions. [2018-10-12 22:30:32,834 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-12 22:30:32,834 INFO L276 IsEmpty]: Start isEmpty. Operand 296 states and 302 transitions. [2018-10-12 22:30:32,837 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 250 [2018-10-12 22:30:32,837 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:32,838 INFO L375 BasicCegarLoop]: trace histogram [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, 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, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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] [2018-10-12 22:30:32,838 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:32,838 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:32,838 INFO L82 PathProgramCache]: Analyzing trace with hash -504720076, now seen corresponding path program 4 times [2018-10-12 22:30:32,839 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:32,860 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:33,147 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 102 proven. 23 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2018-10-12 22:30:33,148 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:33,148 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-12 22:30:33,148 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-12 22:30:33,149 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-12 22:30:33,149 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2018-10-12 22:30:33,149 INFO L87 Difference]: Start difference. First operand 296 states and 302 transitions. Second operand 9 states. [2018-10-12 22:30:33,576 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:33,576 INFO L93 Difference]: Finished difference Result 751 states and 766 transitions. [2018-10-12 22:30:33,576 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-12 22:30:33,577 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 249 [2018-10-12 22:30:33,577 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:33,581 INFO L225 Difference]: With dead ends: 751 [2018-10-12 22:30:33,581 INFO L226 Difference]: Without dead ends: 751 [2018-10-12 22:30:33,581 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=106, Invalid=356, Unknown=0, NotChecked=0, Total=462 [2018-10-12 22:30:33,582 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 751 states. [2018-10-12 22:30:33,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 751 to 328. [2018-10-12 22:30:33,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 328 states. [2018-10-12 22:30:33,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 328 states to 328 states and 336 transitions. [2018-10-12 22:30:33,589 INFO L78 Accepts]: Start accepts. Automaton has 328 states and 336 transitions. Word has length 249 [2018-10-12 22:30:33,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:33,590 INFO L481 AbstractCegarLoop]: Abstraction has 328 states and 336 transitions. [2018-10-12 22:30:33,590 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-12 22:30:33,590 INFO L276 IsEmpty]: Start isEmpty. Operand 328 states and 336 transitions. [2018-10-12 22:30:33,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 264 [2018-10-12 22:30:33,594 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:33,594 INFO L375 BasicCegarLoop]: trace histogram [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, 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, 3, 3, 3, 3, 3, 3, 3, 3, 3, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:30:33,594 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:33,595 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:33,595 INFO L82 PathProgramCache]: Analyzing trace with hash 2036556768, now seen corresponding path program 5 times [2018-10-12 22:30:33,595 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:33,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:33,839 INFO L134 CoverageAnalysis]: Checked inductivity of 238 backedges. 118 proven. 24 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2018-10-12 22:30:33,839 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:33,840 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2018-10-12 22:30:33,840 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-12 22:30:33,840 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-12 22:30:33,841 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2018-10-12 22:30:33,841 INFO L87 Difference]: Start difference. First operand 328 states and 336 transitions. Second operand 11 states. [2018-10-12 22:30:34,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:34,395 INFO L93 Difference]: Finished difference Result 757 states and 772 transitions. [2018-10-12 22:30:34,401 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-12 22:30:34,401 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 263 [2018-10-12 22:30:34,401 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:34,404 INFO L225 Difference]: With dead ends: 757 [2018-10-12 22:30:34,404 INFO L226 Difference]: Without dead ends: 757 [2018-10-12 22:30:34,405 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 156 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=175, Invalid=637, Unknown=0, NotChecked=0, Total=812 [2018-10-12 22:30:34,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 757 states. [2018-10-12 22:30:34,412 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 757 to 399. [2018-10-12 22:30:34,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 399 states. [2018-10-12 22:30:34,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 399 states to 399 states and 408 transitions. [2018-10-12 22:30:34,414 INFO L78 Accepts]: Start accepts. Automaton has 399 states and 408 transitions. Word has length 263 [2018-10-12 22:30:34,414 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:34,414 INFO L481 AbstractCegarLoop]: Abstraction has 399 states and 408 transitions. [2018-10-12 22:30:34,414 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-12 22:30:34,414 INFO L276 IsEmpty]: Start isEmpty. Operand 399 states and 408 transitions. [2018-10-12 22:30:34,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 278 [2018-10-12 22:30:34,416 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:34,416 INFO L375 BasicCegarLoop]: trace histogram [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, 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, 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, 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] [2018-10-12 22:30:34,416 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:34,417 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:34,417 INFO L82 PathProgramCache]: Analyzing trace with hash -1916332660, now seen corresponding path program 6 times [2018-10-12 22:30:34,418 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:34,442 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:36,592 INFO L134 CoverageAnalysis]: Checked inductivity of 269 backedges. 0 proven. 250 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2018-10-12 22:30:36,592 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:36,592 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35] total 35 [2018-10-12 22:30:36,593 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-10-12 22:30:36,593 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-10-12 22:30:36,593 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=1081, Unknown=0, NotChecked=0, Total=1190 [2018-10-12 22:30:36,594 INFO L87 Difference]: Start difference. First operand 399 states and 408 transitions. Second operand 35 states. [2018-10-12 22:30:39,834 WARN L178 SmtUtils]: Spent 180.00 ms on a formula simplification that was a NOOP. DAG size: 29 [2018-10-12 22:30:40,507 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:40,507 INFO L93 Difference]: Finished difference Result 544 states and 555 transitions. [2018-10-12 22:30:40,507 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-10-12 22:30:40,508 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 277 [2018-10-12 22:30:40,508 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:40,512 INFO L225 Difference]: With dead ends: 544 [2018-10-12 22:30:40,512 INFO L226 Difference]: Without dead ends: 544 [2018-10-12 22:30:40,514 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1095 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=417, Invalid=4005, Unknown=0, NotChecked=0, Total=4422 [2018-10-12 22:30:40,515 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 544 states. [2018-10-12 22:30:40,521 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 544 to 523. [2018-10-12 22:30:40,521 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 523 states. [2018-10-12 22:30:40,522 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 523 states to 523 states and 534 transitions. [2018-10-12 22:30:40,522 INFO L78 Accepts]: Start accepts. Automaton has 523 states and 534 transitions. Word has length 277 [2018-10-12 22:30:40,523 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:40,523 INFO L481 AbstractCegarLoop]: Abstraction has 523 states and 534 transitions. [2018-10-12 22:30:40,523 INFO L482 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-10-12 22:30:40,523 INFO L276 IsEmpty]: Start isEmpty. Operand 523 states and 534 transitions. [2018-10-12 22:30:40,525 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 402 [2018-10-12 22:30:40,525 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:40,525 INFO L375 BasicCegarLoop]: trace histogram [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, 5, 5, 5, 5, 5, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:30:40,525 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:40,526 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:40,526 INFO L82 PathProgramCache]: Analyzing trace with hash 1895534006, now seen corresponding path program 7 times [2018-10-12 22:30:40,526 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:40,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:41,128 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 187 proven. 439 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-10-12 22:30:41,128 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:41,128 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2018-10-12 22:30:41,129 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-10-12 22:30:41,129 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-10-12 22:30:41,129 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=263, Unknown=0, NotChecked=0, Total=306 [2018-10-12 22:30:41,129 INFO L87 Difference]: Start difference. First operand 523 states and 534 transitions. Second operand 18 states. [2018-10-12 22:30:42,052 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:42,053 INFO L93 Difference]: Finished difference Result 610 states and 622 transitions. [2018-10-12 22:30:42,053 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-10-12 22:30:42,053 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 401 [2018-10-12 22:30:42,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:42,058 INFO L225 Difference]: With dead ends: 610 [2018-10-12 22:30:42,058 INFO L226 Difference]: Without dead ends: 610 [2018-10-12 22:30:42,059 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 261 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=308, Invalid=1252, Unknown=0, NotChecked=0, Total=1560 [2018-10-12 22:30:42,060 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 610 states. [2018-10-12 22:30:42,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 610 to 537. [2018-10-12 22:30:42,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 537 states. [2018-10-12 22:30:42,067 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 537 states to 537 states and 548 transitions. [2018-10-12 22:30:42,067 INFO L78 Accepts]: Start accepts. Automaton has 537 states and 548 transitions. Word has length 401 [2018-10-12 22:30:42,068 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:42,068 INFO L481 AbstractCegarLoop]: Abstraction has 537 states and 548 transitions. [2018-10-12 22:30:42,068 INFO L482 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-10-12 22:30:42,068 INFO L276 IsEmpty]: Start isEmpty. Operand 537 states and 548 transitions. [2018-10-12 22:30:42,070 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 416 [2018-10-12 22:30:42,071 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:42,071 INFO L375 BasicCegarLoop]: trace histogram [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, 5, 5, 5, 5, 5, 5, 5, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:30:42,071 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:42,071 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:42,072 INFO L82 PathProgramCache]: Analyzing trace with hash -1664200478, now seen corresponding path program 8 times [2018-10-12 22:30:42,072 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:42,098 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:43,504 INFO L134 CoverageAnalysis]: Checked inductivity of 764 backedges. 385 proven. 37 refuted. 0 times theorem prover too weak. 342 trivial. 0 not checked. [2018-10-12 22:30:43,504 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:43,504 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-10-12 22:30:43,505 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-12 22:30:43,505 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-12 22:30:43,505 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2018-10-12 22:30:43,506 INFO L87 Difference]: Start difference. First operand 537 states and 548 transitions. Second operand 15 states. [2018-10-12 22:30:45,125 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:45,125 INFO L93 Difference]: Finished difference Result 1594 states and 1623 transitions. [2018-10-12 22:30:45,125 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-10-12 22:30:45,125 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 415 [2018-10-12 22:30:45,126 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:45,132 INFO L225 Difference]: With dead ends: 1594 [2018-10-12 22:30:45,132 INFO L226 Difference]: Without dead ends: 1554 [2018-10-12 22:30:45,134 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 79 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2242 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=1134, Invalid=5346, Unknown=0, NotChecked=0, Total=6480 [2018-10-12 22:30:45,136 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1554 states. [2018-10-12 22:30:45,150 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1554 to 762. [2018-10-12 22:30:45,150 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 762 states. [2018-10-12 22:30:45,152 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 762 states to 762 states and 779 transitions. [2018-10-12 22:30:45,152 INFO L78 Accepts]: Start accepts. Automaton has 762 states and 779 transitions. Word has length 415 [2018-10-12 22:30:45,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:45,153 INFO L481 AbstractCegarLoop]: Abstraction has 762 states and 779 transitions. [2018-10-12 22:30:45,153 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-12 22:30:45,153 INFO L276 IsEmpty]: Start isEmpty. Operand 762 states and 779 transitions. [2018-10-12 22:30:45,156 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 437 [2018-10-12 22:30:45,156 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:45,156 INFO L375 BasicCegarLoop]: trace histogram [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, 6, 6, 6, 6, 6, 6, 6, 6, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:30:45,156 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:45,157 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:45,157 INFO L82 PathProgramCache]: Analyzing trace with hash 1298752482, now seen corresponding path program 9 times [2018-10-12 22:30:45,158 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:45,195 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:48,006 INFO L134 CoverageAnalysis]: Checked inductivity of 873 backedges. 0 proven. 795 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2018-10-12 22:30:48,007 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:48,007 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [50] total 50 [2018-10-12 22:30:48,008 INFO L460 AbstractCegarLoop]: Interpolant automaton has 50 states [2018-10-12 22:30:48,008 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2018-10-12 22:30:48,009 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=196, Invalid=2254, Unknown=0, NotChecked=0, Total=2450 [2018-10-12 22:30:48,009 INFO L87 Difference]: Start difference. First operand 762 states and 779 transitions. Second operand 50 states. [2018-10-12 22:30:52,691 WARN L178 SmtUtils]: Spent 120.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 38 [2018-10-12 22:30:54,130 WARN L178 SmtUtils]: Spent 294.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 45 [2018-10-12 22:30:56,046 WARN L178 SmtUtils]: Spent 295.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 39 [2018-10-12 22:30:57,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:30:57,139 INFO L93 Difference]: Finished difference Result 1022 states and 1043 transitions. [2018-10-12 22:30:57,140 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 73 states. [2018-10-12 22:30:57,140 INFO L78 Accepts]: Start accepts. Automaton has 50 states. Word has length 436 [2018-10-12 22:30:57,141 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:30:57,145 INFO L225 Difference]: With dead ends: 1022 [2018-10-12 22:30:57,145 INFO L226 Difference]: Without dead ends: 1022 [2018-10-12 22:30:57,149 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 9 SyntacticMatches, 4 SemanticMatches, 114 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3822 ImplicationChecksByTransitivity, 7.8s TimeCoverageRelationStatistics Valid=1770, Invalid=11570, Unknown=0, NotChecked=0, Total=13340 [2018-10-12 22:30:57,150 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1022 states. [2018-10-12 22:30:57,161 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1022 to 921. [2018-10-12 22:30:57,161 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 921 states. [2018-10-12 22:30:57,163 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 921 states to 921 states and 940 transitions. [2018-10-12 22:30:57,163 INFO L78 Accepts]: Start accepts. Automaton has 921 states and 940 transitions. Word has length 436 [2018-10-12 22:30:57,164 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:30:57,164 INFO L481 AbstractCegarLoop]: Abstraction has 921 states and 940 transitions. [2018-10-12 22:30:57,164 INFO L482 AbstractCegarLoop]: Interpolant automaton has 50 states. [2018-10-12 22:30:57,164 INFO L276 IsEmpty]: Start isEmpty. Operand 921 states and 940 transitions. [2018-10-12 22:30:57,168 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 596 [2018-10-12 22:30:57,169 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:30:57,169 INFO L375 BasicCegarLoop]: trace histogram [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, 9, 9, 9, 9, 9, 9, 9, 9, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:30:57,169 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:30:57,169 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:30:57,170 INFO L82 PathProgramCache]: Analyzing trace with hash 1029319372, now seen corresponding path program 10 times [2018-10-12 22:30:57,170 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:30:57,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:30:59,105 INFO L134 CoverageAnalysis]: Checked inductivity of 1858 backedges. 648 proven. 992 refuted. 0 times theorem prover too weak. 218 trivial. 0 not checked. [2018-10-12 22:30:59,106 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:30:59,106 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2018-10-12 22:30:59,107 INFO L460 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-10-12 22:30:59,107 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-10-12 22:30:59,107 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=401, Unknown=0, NotChecked=0, Total=462 [2018-10-12 22:30:59,107 INFO L87 Difference]: Start difference. First operand 921 states and 940 transitions. Second operand 22 states. [2018-10-12 22:31:00,219 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:31:00,220 INFO L93 Difference]: Finished difference Result 1029 states and 1049 transitions. [2018-10-12 22:31:00,220 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-12 22:31:00,220 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 595 [2018-10-12 22:31:00,222 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:31:00,229 INFO L225 Difference]: With dead ends: 1029 [2018-10-12 22:31:00,229 INFO L226 Difference]: Without dead ends: 1029 [2018-10-12 22:31:00,230 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 453 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=473, Invalid=1977, Unknown=0, NotChecked=0, Total=2450 [2018-10-12 22:31:00,231 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1029 states. [2018-10-12 22:31:00,245 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1029 to 935. [2018-10-12 22:31:00,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 935 states. [2018-10-12 22:31:00,248 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 935 states to 935 states and 954 transitions. [2018-10-12 22:31:00,248 INFO L78 Accepts]: Start accepts. Automaton has 935 states and 954 transitions. Word has length 595 [2018-10-12 22:31:00,249 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:31:00,249 INFO L481 AbstractCegarLoop]: Abstraction has 935 states and 954 transitions. [2018-10-12 22:31:00,249 INFO L482 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-10-12 22:31:00,249 INFO L276 IsEmpty]: Start isEmpty. Operand 935 states and 954 transitions. [2018-10-12 22:31:00,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 610 [2018-10-12 22:31:00,253 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:31:00,254 INFO L375 BasicCegarLoop]: trace histogram [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, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:31:00,254 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:31:00,254 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:31:00,254 INFO L82 PathProgramCache]: Analyzing trace with hash -1246670984, now seen corresponding path program 11 times [2018-10-12 22:31:00,255 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:31:00,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:31:01,674 INFO L134 CoverageAnalysis]: Checked inductivity of 1989 backedges. 923 proven. 93 refuted. 0 times theorem prover too weak. 973 trivial. 0 not checked. [2018-10-12 22:31:01,674 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:31:01,675 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-10-12 22:31:01,675 INFO L460 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-12 22:31:01,675 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-12 22:31:01,676 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=292, Unknown=0, NotChecked=0, Total=342 [2018-10-12 22:31:01,676 INFO L87 Difference]: Start difference. First operand 935 states and 954 transitions. Second operand 19 states. [2018-10-12 22:31:02,638 WARN L178 SmtUtils]: Spent 183.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 11 [2018-10-12 22:31:04,208 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:31:04,208 INFO L93 Difference]: Finished difference Result 2443 states and 2486 transitions. [2018-10-12 22:31:04,208 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2018-10-12 22:31:04,208 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 609 [2018-10-12 22:31:04,209 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:31:04,217 INFO L225 Difference]: With dead ends: 2443 [2018-10-12 22:31:04,217 INFO L226 Difference]: Without dead ends: 2389 [2018-10-12 22:31:04,223 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4879 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=1993, Invalid=11117, Unknown=0, NotChecked=0, Total=13110 [2018-10-12 22:31:04,224 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2389 states. [2018-10-12 22:31:04,246 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2389 to 1173. [2018-10-12 22:31:04,246 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1173 states. [2018-10-12 22:31:04,248 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1173 states to 1173 states and 1197 transitions. [2018-10-12 22:31:04,249 INFO L78 Accepts]: Start accepts. Automaton has 1173 states and 1197 transitions. Word has length 609 [2018-10-12 22:31:04,249 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:31:04,249 INFO L481 AbstractCegarLoop]: Abstraction has 1173 states and 1197 transitions. [2018-10-12 22:31:04,249 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-12 22:31:04,250 INFO L276 IsEmpty]: Start isEmpty. Operand 1173 states and 1197 transitions. [2018-10-12 22:31:04,254 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 631 [2018-10-12 22:31:04,255 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:31:04,255 INFO L375 BasicCegarLoop]: trace histogram [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, 10, 10, 10, 10, 10, 10, 10, 10, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:31:04,255 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:31:04,256 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:31:04,256 INFO L82 PathProgramCache]: Analyzing trace with hash 1730869220, now seen corresponding path program 12 times [2018-10-12 22:31:04,256 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:31:04,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:31:08,232 INFO L134 CoverageAnalysis]: Checked inductivity of 2183 backedges. 0 proven. 1902 refuted. 0 times theorem prover too weak. 281 trivial. 0 not checked. [2018-10-12 22:31:08,232 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:31:08,232 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [54] total 54 [2018-10-12 22:31:08,233 INFO L460 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-10-12 22:31:08,233 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-10-12 22:31:08,234 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=176, Invalid=2686, Unknown=0, NotChecked=0, Total=2862 [2018-10-12 22:31:08,235 INFO L87 Difference]: Start difference. First operand 1173 states and 1197 transitions. Second operand 54 states. [2018-10-12 22:31:15,707 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:31:15,707 INFO L93 Difference]: Finished difference Result 1388 states and 1414 transitions. [2018-10-12 22:31:15,708 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-10-12 22:31:15,709 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 630 [2018-10-12 22:31:15,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:31:15,715 INFO L225 Difference]: With dead ends: 1388 [2018-10-12 22:31:15,715 INFO L226 Difference]: Without dead ends: 1388 [2018-10-12 22:31:15,718 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 10 SyntacticMatches, 5 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3088 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=692, Invalid=10438, Unknown=0, NotChecked=0, Total=11130 [2018-10-12 22:31:15,719 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1388 states. [2018-10-12 22:31:15,734 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1388 to 1367. [2018-10-12 22:31:15,734 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1367 states. [2018-10-12 22:31:15,736 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1367 states to 1367 states and 1393 transitions. [2018-10-12 22:31:15,736 INFO L78 Accepts]: Start accepts. Automaton has 1367 states and 1393 transitions. Word has length 630 [2018-10-12 22:31:15,737 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:31:15,737 INFO L481 AbstractCegarLoop]: Abstraction has 1367 states and 1393 transitions. [2018-10-12 22:31:15,737 INFO L482 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-10-12 22:31:15,737 INFO L276 IsEmpty]: Start isEmpty. Operand 1367 states and 1393 transitions. [2018-10-12 22:31:15,744 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 825 [2018-10-12 22:31:15,744 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:31:15,745 INFO L375 BasicCegarLoop]: trace histogram [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, 14, 14, 14, 14, 14, 14, 14, 14, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:31:15,745 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:31:15,745 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:31:15,745 INFO L82 PathProgramCache]: Analyzing trace with hash -2097126554, now seen corresponding path program 13 times [2018-10-12 22:31:15,746 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:31:15,796 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:31:17,157 INFO L134 CoverageAnalysis]: Checked inductivity of 4123 backedges. 2341 proven. 1324 refuted. 0 times theorem prover too weak. 458 trivial. 0 not checked. [2018-10-12 22:31:17,157 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:31:17,157 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2018-10-12 22:31:17,158 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-10-12 22:31:17,158 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-10-12 22:31:17,159 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=473, Unknown=0, NotChecked=0, Total=552 [2018-10-12 22:31:17,159 INFO L87 Difference]: Start difference. First operand 1367 states and 1393 transitions. Second operand 24 states. [2018-10-12 22:31:18,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:31:18,438 INFO L93 Difference]: Finished difference Result 1400 states and 1426 transitions. [2018-10-12 22:31:18,439 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-10-12 22:31:18,439 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 824 [2018-10-12 22:31:18,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:31:18,446 INFO L225 Difference]: With dead ends: 1400 [2018-10-12 22:31:18,446 INFO L226 Difference]: Without dead ends: 1400 [2018-10-12 22:31:18,447 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 593 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=564, Invalid=2406, Unknown=0, NotChecked=0, Total=2970 [2018-10-12 22:31:18,448 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1400 states. [2018-10-12 22:31:18,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1400 to 1388. [2018-10-12 22:31:18,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1388 states. [2018-10-12 22:31:18,464 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1388 states to 1388 states and 1414 transitions. [2018-10-12 22:31:18,465 INFO L78 Accepts]: Start accepts. Automaton has 1388 states and 1414 transitions. Word has length 824 [2018-10-12 22:31:18,465 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:31:18,465 INFO L481 AbstractCegarLoop]: Abstraction has 1388 states and 1414 transitions. [2018-10-12 22:31:18,466 INFO L482 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-10-12 22:31:18,466 INFO L276 IsEmpty]: Start isEmpty. Operand 1388 states and 1414 transitions. [2018-10-12 22:31:18,473 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 846 [2018-10-12 22:31:18,473 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:31:18,474 INFO L375 BasicCegarLoop]: trace histogram [15, 15, 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, 14, 14, 14, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:31:18,474 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:31:18,474 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:31:18,474 INFO L82 PathProgramCache]: Analyzing trace with hash 1315521718, now seen corresponding path program 14 times [2018-10-12 22:31:18,475 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:31:18,524 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:31:19,247 INFO L134 CoverageAnalysis]: Checked inductivity of 4423 backedges. 1879 proven. 234 refuted. 0 times theorem prover too weak. 2310 trivial. 0 not checked. [2018-10-12 22:31:19,247 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:31:19,248 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2018-10-12 22:31:19,248 INFO L460 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-12 22:31:19,248 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-12 22:31:19,249 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=436, Unknown=0, NotChecked=0, Total=506 [2018-10-12 22:31:19,249 INFO L87 Difference]: Start difference. First operand 1388 states and 1414 transitions. Second operand 23 states. [2018-10-12 22:31:21,258 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:31:21,258 INFO L93 Difference]: Finished difference Result 3123 states and 3178 transitions. [2018-10-12 22:31:21,258 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2018-10-12 22:31:21,258 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 845 [2018-10-12 22:31:21,259 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:31:21,269 INFO L225 Difference]: With dead ends: 3123 [2018-10-12 22:31:21,270 INFO L226 Difference]: Without dead ends: 3123 [2018-10-12 22:31:21,271 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1325 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=926, Invalid=4186, Unknown=0, NotChecked=0, Total=5112 [2018-10-12 22:31:21,273 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3123 states. [2018-10-12 22:31:21,295 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3123 to 1715. [2018-10-12 22:31:21,295 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1715 states. [2018-10-12 22:31:21,299 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1715 states to 1715 states and 1746 transitions. [2018-10-12 22:31:21,299 INFO L78 Accepts]: Start accepts. Automaton has 1715 states and 1746 transitions. Word has length 845 [2018-10-12 22:31:21,300 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:31:21,300 INFO L481 AbstractCegarLoop]: Abstraction has 1715 states and 1746 transitions. [2018-10-12 22:31:21,300 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-12 22:31:21,300 INFO L276 IsEmpty]: Start isEmpty. Operand 1715 states and 1746 transitions. [2018-10-12 22:31:21,308 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 860 [2018-10-12 22:31:21,308 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:31:21,309 INFO L375 BasicCegarLoop]: trace histogram [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, 15, 15, 15, 15, 15, 15, 15, 15, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:31:21,309 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:31:21,309 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:31:21,310 INFO L82 PathProgramCache]: Analyzing trace with hash -797980702, now seen corresponding path program 15 times [2018-10-12 22:31:21,310 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:31:21,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:31:27,562 INFO L134 CoverageAnalysis]: Checked inductivity of 4625 backedges. 0 proven. 4052 refuted. 0 times theorem prover too weak. 573 trivial. 0 not checked. [2018-10-12 22:31:27,562 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:31:27,563 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [66] total 66 [2018-10-12 22:31:27,563 INFO L460 AbstractCegarLoop]: Interpolant automaton has 66 states [2018-10-12 22:31:27,563 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 66 interpolants. [2018-10-12 22:31:27,564 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=220, Invalid=4070, Unknown=0, NotChecked=0, Total=4290 [2018-10-12 22:31:27,564 INFO L87 Difference]: Start difference. First operand 1715 states and 1746 transitions. Second operand 66 states. [2018-10-12 22:31:38,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:31:38,180 INFO L93 Difference]: Finished difference Result 1971 states and 2004 transitions. [2018-10-12 22:31:38,180 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 81 states. [2018-10-12 22:31:38,180 INFO L78 Accepts]: Start accepts. Automaton has 66 states. Word has length 859 [2018-10-12 22:31:38,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:31:38,187 INFO L225 Difference]: With dead ends: 1971 [2018-10-12 22:31:38,187 INFO L226 Difference]: Without dead ends: 1971 [2018-10-12 22:31:38,188 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 147 GetRequests, 11 SyntacticMatches, 8 SemanticMatches, 128 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4842 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=871, Invalid=15899, Unknown=0, NotChecked=0, Total=16770 [2018-10-12 22:31:38,189 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1971 states. [2018-10-12 22:31:38,204 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1971 to 1944. [2018-10-12 22:31:38,205 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1944 states. [2018-10-12 22:31:38,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1944 states to 1944 states and 1977 transitions. [2018-10-12 22:31:38,208 INFO L78 Accepts]: Start accepts. Automaton has 1944 states and 1977 transitions. Word has length 859 [2018-10-12 22:31:38,208 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:31:38,208 INFO L481 AbstractCegarLoop]: Abstraction has 1944 states and 1977 transitions. [2018-10-12 22:31:38,209 INFO L482 AbstractCegarLoop]: Interpolant automaton has 66 states. [2018-10-12 22:31:38,209 INFO L276 IsEmpty]: Start isEmpty. Operand 1944 states and 1977 transitions. [2018-10-12 22:31:38,219 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1089 [2018-10-12 22:31:38,219 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:31:38,220 INFO L375 BasicCegarLoop]: trace histogram [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, 20, 20, 20, 20, 20, 20, 20, 20, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:31:38,220 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:31:38,221 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:31:38,221 INFO L82 PathProgramCache]: Analyzing trace with hash -788361564, now seen corresponding path program 16 times [2018-10-12 22:31:38,221 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:31:38,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:31:40,006 INFO L134 CoverageAnalysis]: Checked inductivity of 8016 backedges. 4901 proven. 2240 refuted. 0 times theorem prover too weak. 875 trivial. 0 not checked. [2018-10-12 22:31:40,006 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:31:40,007 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28] total 28 [2018-10-12 22:31:40,008 INFO L460 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-10-12 22:31:40,008 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-10-12 22:31:40,008 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=651, Unknown=0, NotChecked=0, Total=756 [2018-10-12 22:31:40,009 INFO L87 Difference]: Start difference. First operand 1944 states and 1977 transitions. Second operand 28 states. [2018-10-12 22:31:41,761 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:31:41,761 INFO L93 Difference]: Finished difference Result 1977 states and 2010 transitions. [2018-10-12 22:31:41,761 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2018-10-12 22:31:41,761 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 1088 [2018-10-12 22:31:41,763 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:31:41,769 INFO L225 Difference]: With dead ends: 1977 [2018-10-12 22:31:41,769 INFO L226 Difference]: Without dead ends: 1977 [2018-10-12 22:31:41,770 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 865 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=787, Invalid=3373, Unknown=0, NotChecked=0, Total=4160 [2018-10-12 22:31:41,770 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1977 states. [2018-10-12 22:31:41,785 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1977 to 1965. [2018-10-12 22:31:41,785 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1965 states. [2018-10-12 22:31:41,788 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1965 states to 1965 states and 1998 transitions. [2018-10-12 22:31:41,788 INFO L78 Accepts]: Start accepts. Automaton has 1965 states and 1998 transitions. Word has length 1088 [2018-10-12 22:31:41,789 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:31:41,789 INFO L481 AbstractCegarLoop]: Abstraction has 1965 states and 1998 transitions. [2018-10-12 22:31:41,789 INFO L482 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-10-12 22:31:41,789 INFO L276 IsEmpty]: Start isEmpty. Operand 1965 states and 1998 transitions. [2018-10-12 22:31:41,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1110 [2018-10-12 22:31:41,800 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:31:41,801 INFO L375 BasicCegarLoop]: trace histogram [21, 21, 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, 20, 20, 20, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:31:41,801 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:31:41,802 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:31:41,802 INFO L82 PathProgramCache]: Analyzing trace with hash -1095677168, now seen corresponding path program 17 times [2018-10-12 22:31:41,802 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:31:41,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:31:43,051 INFO L134 CoverageAnalysis]: Checked inductivity of 8443 backedges. 3332 proven. 332 refuted. 0 times theorem prover too weak. 4779 trivial. 0 not checked. [2018-10-12 22:31:43,052 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:31:43,052 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2018-10-12 22:31:43,053 INFO L460 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-10-12 22:31:43,053 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-10-12 22:31:43,053 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=608, Unknown=0, NotChecked=0, Total=702 [2018-10-12 22:31:43,053 INFO L87 Difference]: Start difference. First operand 1965 states and 1998 transitions. Second operand 27 states. [2018-10-12 22:31:45,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:31:45,732 INFO L93 Difference]: Finished difference Result 4510 states and 4585 transitions. [2018-10-12 22:31:45,732 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-10-12 22:31:45,732 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 1109 [2018-10-12 22:31:45,733 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:31:45,744 INFO L225 Difference]: With dead ends: 4510 [2018-10-12 22:31:45,744 INFO L226 Difference]: Without dead ends: 4510 [2018-10-12 22:31:45,745 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1971 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1316, Invalid=5994, Unknown=0, NotChecked=0, Total=7310 [2018-10-12 22:31:45,748 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4510 states. [2018-10-12 22:31:45,770 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4510 to 2237. [2018-10-12 22:31:45,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2237 states. [2018-10-12 22:31:45,772 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2237 states to 2237 states and 2276 transitions. [2018-10-12 22:31:45,773 INFO L78 Accepts]: Start accepts. Automaton has 2237 states and 2276 transitions. Word has length 1109 [2018-10-12 22:31:45,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:31:45,773 INFO L481 AbstractCegarLoop]: Abstraction has 2237 states and 2276 transitions. [2018-10-12 22:31:45,773 INFO L482 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-10-12 22:31:45,773 INFO L276 IsEmpty]: Start isEmpty. Operand 2237 states and 2276 transitions. [2018-10-12 22:31:45,785 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1124 [2018-10-12 22:31:45,786 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:31:45,786 INFO L375 BasicCegarLoop]: trace histogram [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, 21, 21, 21, 21, 21, 21, 21, 21, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:31:45,787 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:31:45,787 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:31:45,787 INFO L82 PathProgramCache]: Analyzing trace with hash -564614980, now seen corresponding path program 18 times [2018-10-12 22:31:45,788 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:31:45,894 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:31:53,315 INFO L134 CoverageAnalysis]: Checked inductivity of 8730 backedges. 0 proven. 7610 refuted. 0 times theorem prover too weak. 1120 trivial. 0 not checked. [2018-10-12 22:31:53,315 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:31:53,316 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67] total 67 [2018-10-12 22:31:53,316 INFO L460 AbstractCegarLoop]: Interpolant automaton has 67 states [2018-10-12 22:31:53,317 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 67 interpolants. [2018-10-12 22:31:53,317 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=214, Invalid=4208, Unknown=0, NotChecked=0, Total=4422 [2018-10-12 22:31:53,317 INFO L87 Difference]: Start difference. First operand 2237 states and 2276 transitions. Second operand 67 states. [2018-10-12 22:32:04,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:32:04,334 INFO L93 Difference]: Finished difference Result 2530 states and 2571 transitions. [2018-10-12 22:32:04,334 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 85 states. [2018-10-12 22:32:04,334 INFO L78 Accepts]: Start accepts. Automaton has 67 states. Word has length 1123 [2018-10-12 22:32:04,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:32:04,343 INFO L225 Difference]: With dead ends: 2530 [2018-10-12 22:32:04,343 INFO L226 Difference]: Without dead ends: 2530 [2018-10-12 22:32:04,345 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 14 SyntacticMatches, 3 SemanticMatches, 131 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4868 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=848, Invalid=16708, Unknown=0, NotChecked=0, Total=17556 [2018-10-12 22:32:04,346 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2530 states. [2018-10-12 22:32:04,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2530 to 2501. [2018-10-12 22:32:04,365 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2501 states. [2018-10-12 22:32:04,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2501 states to 2501 states and 2542 transitions. [2018-10-12 22:32:04,368 INFO L78 Accepts]: Start accepts. Automaton has 2501 states and 2542 transitions. Word has length 1123 [2018-10-12 22:32:04,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:32:04,369 INFO L481 AbstractCegarLoop]: Abstraction has 2501 states and 2542 transitions. [2018-10-12 22:32:04,369 INFO L482 AbstractCegarLoop]: Interpolant automaton has 67 states. [2018-10-12 22:32:04,369 INFO L276 IsEmpty]: Start isEmpty. Operand 2501 states and 2542 transitions. [2018-10-12 22:32:04,385 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1388 [2018-10-12 22:32:04,386 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:32:04,386 INFO L375 BasicCegarLoop]: trace histogram [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, 27, 27, 27, 27, 27, 27, 27, 27, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:32:04,387 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:32:04,387 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:32:04,387 INFO L82 PathProgramCache]: Analyzing trace with hash -367472746, now seen corresponding path program 19 times [2018-10-12 22:32:04,388 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:32:04,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:32:06,393 INFO L134 CoverageAnalysis]: Checked inductivity of 14173 backedges. 9172 proven. 3518 refuted. 0 times theorem prover too weak. 1483 trivial. 0 not checked. [2018-10-12 22:32:06,393 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:32:06,394 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32] total 32 [2018-10-12 22:32:06,394 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-10-12 22:32:06,395 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-10-12 22:32:06,395 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=857, Unknown=0, NotChecked=0, Total=992 [2018-10-12 22:32:06,395 INFO L87 Difference]: Start difference. First operand 2501 states and 2542 transitions. Second operand 32 states. [2018-10-12 22:32:08,783 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:32:08,783 INFO L93 Difference]: Finished difference Result 2534 states and 2575 transitions. [2018-10-12 22:32:08,786 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-12 22:32:08,786 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 1387 [2018-10-12 22:32:08,787 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:32:08,794 INFO L225 Difference]: With dead ends: 2534 [2018-10-12 22:32:08,794 INFO L226 Difference]: Without dead ends: 2534 [2018-10-12 22:32:08,794 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1188 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1048, Invalid=4502, Unknown=0, NotChecked=0, Total=5550 [2018-10-12 22:32:08,795 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2534 states. [2018-10-12 22:32:08,811 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2534 to 2522. [2018-10-12 22:32:08,812 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2522 states. [2018-10-12 22:32:08,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2522 states to 2522 states and 2563 transitions. [2018-10-12 22:32:08,814 INFO L78 Accepts]: Start accepts. Automaton has 2522 states and 2563 transitions. Word has length 1387 [2018-10-12 22:32:08,815 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:32:08,815 INFO L481 AbstractCegarLoop]: Abstraction has 2522 states and 2563 transitions. [2018-10-12 22:32:08,815 INFO L482 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-10-12 22:32:08,815 INFO L276 IsEmpty]: Start isEmpty. Operand 2522 states and 2563 transitions. [2018-10-12 22:32:08,849 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1409 [2018-10-12 22:32:08,850 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:32:08,851 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 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, 27, 27, 27, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:32:08,851 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:32:08,851 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:32:08,851 INFO L82 PathProgramCache]: Analyzing trace with hash -841958858, now seen corresponding path program 20 times [2018-10-12 22:32:08,852 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:32:08,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:32:10,419 INFO L134 CoverageAnalysis]: Checked inductivity of 14748 backedges. 5393 proven. 444 refuted. 0 times theorem prover too weak. 8911 trivial. 0 not checked. [2018-10-12 22:32:10,419 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:32:10,419 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31] total 31 [2018-10-12 22:32:10,420 INFO L460 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-10-12 22:32:10,420 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-10-12 22:32:10,420 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=808, Unknown=0, NotChecked=0, Total=930 [2018-10-12 22:32:10,421 INFO L87 Difference]: Start difference. First operand 2522 states and 2563 transitions. Second operand 31 states. [2018-10-12 22:32:13,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:32:13,318 INFO L93 Difference]: Finished difference Result 6218 states and 6316 transitions. [2018-10-12 22:32:13,318 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 78 states. [2018-10-12 22:32:13,318 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 1408 [2018-10-12 22:32:13,319 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:32:13,337 INFO L225 Difference]: With dead ends: 6218 [2018-10-12 22:32:13,337 INFO L226 Difference]: Without dead ends: 6218 [2018-10-12 22:32:13,339 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 98 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2744 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=1777, Invalid=8123, Unknown=0, NotChecked=0, Total=9900 [2018-10-12 22:32:13,342 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6218 states. [2018-10-12 22:32:13,371 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6218 to 2837. [2018-10-12 22:32:13,371 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2837 states. [2018-10-12 22:32:13,375 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2837 states to 2837 states and 2885 transitions. [2018-10-12 22:32:13,376 INFO L78 Accepts]: Start accepts. Automaton has 2837 states and 2885 transitions. Word has length 1408 [2018-10-12 22:32:13,377 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:32:13,377 INFO L481 AbstractCegarLoop]: Abstraction has 2837 states and 2885 transitions. [2018-10-12 22:32:13,377 INFO L482 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-10-12 22:32:13,377 INFO L276 IsEmpty]: Start isEmpty. Operand 2837 states and 2885 transitions. [2018-10-12 22:32:13,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1423 [2018-10-12 22:32:13,394 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:32:13,395 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:32:13,396 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:32:13,396 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:32:13,396 INFO L82 PathProgramCache]: Analyzing trace with hash 81501538, now seen corresponding path program 21 times [2018-10-12 22:32:13,397 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:32:13,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:32:15,075 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-10-12 22:32:24,832 INFO L134 CoverageAnalysis]: Checked inductivity of 15134 backedges. 0 proven. 13335 refuted. 0 times theorem prover too weak. 1799 trivial. 0 not checked. [2018-10-12 22:32:24,832 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:32:24,833 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [78] total 78 [2018-10-12 22:32:24,834 INFO L460 AbstractCegarLoop]: Interpolant automaton has 78 states [2018-10-12 22:32:24,834 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 78 interpolants. [2018-10-12 22:32:24,834 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=253, Invalid=5753, Unknown=0, NotChecked=0, Total=6006 [2018-10-12 22:32:24,835 INFO L87 Difference]: Start difference. First operand 2837 states and 2885 transitions. Second operand 78 states. [2018-10-12 22:32:39,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:32:39,418 INFO L93 Difference]: Finished difference Result 3171 states and 3221 transitions. [2018-10-12 22:32:39,418 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 99 states. [2018-10-12 22:32:39,419 INFO L78 Accepts]: Start accepts. Automaton has 78 states. Word has length 1422 [2018-10-12 22:32:39,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:32:39,424 INFO L225 Difference]: With dead ends: 3171 [2018-10-12 22:32:39,424 INFO L226 Difference]: Without dead ends: 3171 [2018-10-12 22:32:39,425 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 15 SyntacticMatches, 4 SemanticMatches, 154 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6849 ImplicationChecksByTransitivity, 9.1s TimeCoverageRelationStatistics Valid=1015, Invalid=23165, Unknown=0, NotChecked=0, Total=24180 [2018-10-12 22:32:39,427 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3171 states. [2018-10-12 22:32:39,442 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3171 to 3136. [2018-10-12 22:32:39,443 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3136 states. [2018-10-12 22:32:39,445 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3136 states to 3136 states and 3186 transitions. [2018-10-12 22:32:39,445 INFO L78 Accepts]: Start accepts. Automaton has 3136 states and 3186 transitions. Word has length 1422 [2018-10-12 22:32:39,446 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:32:39,446 INFO L481 AbstractCegarLoop]: Abstraction has 3136 states and 3186 transitions. [2018-10-12 22:32:39,446 INFO L482 AbstractCegarLoop]: Interpolant automaton has 78 states. [2018-10-12 22:32:39,446 INFO L276 IsEmpty]: Start isEmpty. Operand 3136 states and 3186 transitions. [2018-10-12 22:32:39,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1722 [2018-10-12 22:32:39,463 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:32:39,464 INFO L375 BasicCegarLoop]: trace histogram [35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:32:39,464 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:32:39,464 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:32:39,464 INFO L82 PathProgramCache]: Analyzing trace with hash -592626436, now seen corresponding path program 22 times [2018-10-12 22:32:39,465 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:32:39,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:32:42,514 INFO L134 CoverageAnalysis]: Checked inductivity of 23335 backedges. 15797 proven. 5221 refuted. 0 times theorem prover too weak. 2317 trivial. 0 not checked. [2018-10-12 22:32:42,514 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:32:42,515 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [36] total 36 [2018-10-12 22:32:42,516 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-10-12 22:32:42,516 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-10-12 22:32:42,516 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=1091, Unknown=0, NotChecked=0, Total=1260 [2018-10-12 22:32:42,517 INFO L87 Difference]: Start difference. First operand 3136 states and 3186 transitions. Second operand 36 states. [2018-10-12 22:32:45,511 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:32:45,512 INFO L93 Difference]: Finished difference Result 3169 states and 3219 transitions. [2018-10-12 22:32:45,512 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-10-12 22:32:45,512 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 1721 [2018-10-12 22:32:45,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:32:45,519 INFO L225 Difference]: With dead ends: 3169 [2018-10-12 22:32:45,519 INFO L226 Difference]: Without dead ends: 3169 [2018-10-12 22:32:45,520 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1562 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=1347, Invalid=5793, Unknown=0, NotChecked=0, Total=7140 [2018-10-12 22:32:45,522 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3169 states. [2018-10-12 22:32:45,538 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3169 to 3157. [2018-10-12 22:32:45,539 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3157 states. [2018-10-12 22:32:45,541 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3157 states to 3157 states and 3207 transitions. [2018-10-12 22:32:45,541 INFO L78 Accepts]: Start accepts. Automaton has 3157 states and 3207 transitions. Word has length 1721 [2018-10-12 22:32:45,542 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:32:45,542 INFO L481 AbstractCegarLoop]: Abstraction has 3157 states and 3207 transitions. [2018-10-12 22:32:45,542 INFO L482 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-10-12 22:32:45,542 INFO L276 IsEmpty]: Start isEmpty. Operand 3157 states and 3207 transitions. [2018-10-12 22:32:45,559 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1743 [2018-10-12 22:32:45,559 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:32:45,560 INFO L375 BasicCegarLoop]: trace histogram [36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:32:45,561 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:32:45,561 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:32:45,561 INFO L82 PathProgramCache]: Analyzing trace with hash -554126488, now seen corresponding path program 23 times [2018-10-12 22:32:45,562 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:32:45,651 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:32:48,037 INFO L134 CoverageAnalysis]: Checked inductivity of 24079 backedges. 8167 proven. 570 refuted. 0 times theorem prover too weak. 15342 trivial. 0 not checked. [2018-10-12 22:32:48,038 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:32:48,038 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35] total 35 [2018-10-12 22:32:48,039 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-10-12 22:32:48,039 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-10-12 22:32:48,039 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2018-10-12 22:32:48,040 INFO L87 Difference]: Start difference. First operand 3157 states and 3207 transitions. Second operand 35 states. [2018-10-12 22:32:52,652 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:32:52,652 INFO L93 Difference]: Finished difference Result 8275 states and 8399 transitions. [2018-10-12 22:32:52,653 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-10-12 22:32:52,653 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 1742 [2018-10-12 22:32:52,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:32:52,668 INFO L225 Difference]: With dead ends: 8275 [2018-10-12 22:32:52,668 INFO L226 Difference]: Without dead ends: 8275 [2018-10-12 22:32:52,669 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3644 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=2309, Invalid=10573, Unknown=0, NotChecked=0, Total=12882 [2018-10-12 22:32:52,674 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8275 states. [2018-10-12 22:32:52,711 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8275 to 3515. [2018-10-12 22:32:52,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3515 states. [2018-10-12 22:32:52,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3515 states to 3515 states and 3573 transitions. [2018-10-12 22:32:52,715 INFO L78 Accepts]: Start accepts. Automaton has 3515 states and 3573 transitions. Word has length 1742 [2018-10-12 22:32:52,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:32:52,716 INFO L481 AbstractCegarLoop]: Abstraction has 3515 states and 3573 transitions. [2018-10-12 22:32:52,716 INFO L482 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-10-12 22:32:52,716 INFO L276 IsEmpty]: Start isEmpty. Operand 3515 states and 3573 transitions. [2018-10-12 22:32:52,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1757 [2018-10-12 22:32:52,739 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:32:52,740 INFO L375 BasicCegarLoop]: trace histogram [36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:32:52,740 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:32:52,741 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:32:52,741 INFO L82 PathProgramCache]: Analyzing trace with hash 2096535316, now seen corresponding path program 24 times [2018-10-12 22:32:52,741 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:32:52,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:33:07,727 INFO L134 CoverageAnalysis]: Checked inductivity of 24578 backedges. 0 proven. 21845 refuted. 0 times theorem prover too weak. 2733 trivial. 0 not checked. [2018-10-12 22:33:07,727 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:33:07,727 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-12 22:33:07,728 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-12 22:33:07,728 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-12 22:33:07,729 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=292, Invalid=7540, Unknown=0, NotChecked=0, Total=7832 [2018-10-12 22:33:07,729 INFO L87 Difference]: Start difference. First operand 3515 states and 3573 transitions. Second operand 89 states. [2018-10-12 22:33:28,402 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:33:28,402 INFO L93 Difference]: Finished difference Result 3896 states and 3956 transitions. [2018-10-12 22:33:28,403 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 113 states. [2018-10-12 22:33:28,403 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 1756 [2018-10-12 22:33:28,404 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:33:28,409 INFO L225 Difference]: With dead ends: 3896 [2018-10-12 22:33:28,409 INFO L226 Difference]: Without dead ends: 3896 [2018-10-12 22:33:28,411 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 198 GetRequests, 16 SyntacticMatches, 5 SemanticMatches, 177 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9173 ImplicationChecksByTransitivity, 10.6s TimeCoverageRelationStatistics Valid=1180, Invalid=30682, Unknown=0, NotChecked=0, Total=31862 [2018-10-12 22:33:28,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3896 states. [2018-10-12 22:33:28,436 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3896 to 3849. [2018-10-12 22:33:28,436 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3849 states. [2018-10-12 22:33:28,441 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3849 states to 3849 states and 3909 transitions. [2018-10-12 22:33:28,441 INFO L78 Accepts]: Start accepts. Automaton has 3849 states and 3909 transitions. Word has length 1756 [2018-10-12 22:33:28,442 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:33:28,442 INFO L481 AbstractCegarLoop]: Abstraction has 3849 states and 3909 transitions. [2018-10-12 22:33:28,442 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-12 22:33:28,442 INFO L276 IsEmpty]: Start isEmpty. Operand 3849 states and 3909 transitions. [2018-10-12 22:33:28,476 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2091 [2018-10-12 22:33:28,476 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:33:28,477 INFO L375 BasicCegarLoop]: trace histogram [44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:33:28,477 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:33:28,478 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:33:28,478 INFO L82 PathProgramCache]: Analyzing trace with hash -245046970, now seen corresponding path program 25 times [2018-10-12 22:33:28,479 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:33:28,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:33:32,510 INFO L134 CoverageAnalysis]: Checked inductivity of 36348 backedges. 25524 proven. 7412 refuted. 0 times theorem prover too weak. 3412 trivial. 0 not checked. [2018-10-12 22:33:32,510 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:33:32,510 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [40] total 40 [2018-10-12 22:33:32,511 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-10-12 22:33:32,511 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-10-12 22:33:32,511 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=207, Invalid=1353, Unknown=0, NotChecked=0, Total=1560 [2018-10-12 22:33:32,512 INFO L87 Difference]: Start difference. First operand 3849 states and 3909 transitions. Second operand 40 states. [2018-10-12 22:33:36,202 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:33:36,202 INFO L93 Difference]: Finished difference Result 3882 states and 3942 transitions. [2018-10-12 22:33:36,202 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-10-12 22:33:36,202 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 2090 [2018-10-12 22:33:36,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:33:36,207 INFO L225 Difference]: With dead ends: 3882 [2018-10-12 22:33:36,207 INFO L226 Difference]: Without dead ends: 3882 [2018-10-12 22:33:36,208 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1987 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=1684, Invalid=7246, Unknown=0, NotChecked=0, Total=8930 [2018-10-12 22:33:36,210 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3882 states. [2018-10-12 22:33:36,232 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3882 to 3870. [2018-10-12 22:33:36,232 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3870 states. [2018-10-12 22:33:36,236 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3870 states to 3870 states and 3930 transitions. [2018-10-12 22:33:36,237 INFO L78 Accepts]: Start accepts. Automaton has 3870 states and 3930 transitions. Word has length 2090 [2018-10-12 22:33:36,238 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:33:36,238 INFO L481 AbstractCegarLoop]: Abstraction has 3870 states and 3930 transitions. [2018-10-12 22:33:36,238 INFO L482 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-10-12 22:33:36,238 INFO L276 IsEmpty]: Start isEmpty. Operand 3870 states and 3930 transitions. [2018-10-12 22:33:36,279 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2112 [2018-10-12 22:33:36,280 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:33:36,281 INFO L375 BasicCegarLoop]: trace histogram [45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:33:36,281 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:33:36,281 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:33:36,282 INFO L82 PathProgramCache]: Analyzing trace with hash 399872566, now seen corresponding path program 26 times [2018-10-12 22:33:36,282 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:33:36,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:33:39,033 INFO L134 CoverageAnalysis]: Checked inductivity of 37282 backedges. 11759 proven. 710 refuted. 0 times theorem prover too weak. 24813 trivial. 0 not checked. [2018-10-12 22:33:39,034 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:33:39,034 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39] total 39 [2018-10-12 22:33:39,035 INFO L460 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-10-12 22:33:39,035 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-10-12 22:33:39,035 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=190, Invalid=1292, Unknown=0, NotChecked=0, Total=1482 [2018-10-12 22:33:39,035 INFO L87 Difference]: Start difference. First operand 3870 states and 3930 transitions. Second operand 39 states. [2018-10-12 22:33:44,762 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:33:44,763 INFO L93 Difference]: Finished difference Result 10709 states and 10862 transitions. [2018-10-12 22:33:44,766 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-10-12 22:33:44,766 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 2111 [2018-10-12 22:33:44,768 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:33:44,779 INFO L225 Difference]: With dead ends: 10709 [2018-10-12 22:33:44,779 INFO L226 Difference]: Without dead ends: 10709 [2018-10-12 22:33:44,781 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 126 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4671 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=2912, Invalid=13344, Unknown=0, NotChecked=0, Total=16256 [2018-10-12 22:33:44,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10709 states. [2018-10-12 22:33:44,834 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10709 to 4271. [2018-10-12 22:33:44,834 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4271 states. [2018-10-12 22:33:44,839 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4271 states to 4271 states and 4340 transitions. [2018-10-12 22:33:44,839 INFO L78 Accepts]: Start accepts. Automaton has 4271 states and 4340 transitions. Word has length 2111 [2018-10-12 22:33:44,840 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:33:44,840 INFO L481 AbstractCegarLoop]: Abstraction has 4271 states and 4340 transitions. [2018-10-12 22:33:44,840 INFO L482 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-10-12 22:33:44,841 INFO L276 IsEmpty]: Start isEmpty. Operand 4271 states and 4340 transitions. [2018-10-12 22:33:44,879 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2126 [2018-10-12 22:33:44,879 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:33:44,880 INFO L375 BasicCegarLoop]: trace histogram [45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:33:44,881 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:33:44,881 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:33:44,881 INFO L82 PathProgramCache]: Analyzing trace with hash -1719241374, now seen corresponding path program 27 times [2018-10-12 22:33:44,882 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:33:45,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:34:04,950 INFO L134 CoverageAnalysis]: Checked inductivity of 37908 backedges. 0 proven. 33991 refuted. 0 times theorem prover too weak. 3917 trivial. 0 not checked. [2018-10-12 22:34:04,950 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:34:04,950 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [100] total 100 [2018-10-12 22:34:04,951 INFO L460 AbstractCegarLoop]: Interpolant automaton has 100 states [2018-10-12 22:34:04,951 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 100 interpolants. [2018-10-12 22:34:04,952 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=331, Invalid=9569, Unknown=0, NotChecked=0, Total=9900 [2018-10-12 22:34:04,952 INFO L87 Difference]: Start difference. First operand 4271 states and 4340 transitions. Second operand 100 states. [2018-10-12 22:34:05,790 WARN L178 SmtUtils]: Spent 185.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-10-12 22:34:32,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:34:32,115 INFO L93 Difference]: Finished difference Result 4697 states and 4768 transitions. [2018-10-12 22:34:32,115 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 126 states. [2018-10-12 22:34:32,115 INFO L78 Accepts]: Start accepts. Automaton has 100 states. Word has length 2125 [2018-10-12 22:34:32,118 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:34:32,121 INFO L225 Difference]: With dead ends: 4697 [2018-10-12 22:34:32,121 INFO L226 Difference]: Without dead ends: 4697 [2018-10-12 22:34:32,124 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 224 GetRequests, 17 SyntacticMatches, 6 SemanticMatches, 201 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11976 ImplicationChecksByTransitivity, 13.2s TimeCoverageRelationStatistics Valid=1368, Invalid=39638, Unknown=0, NotChecked=0, Total=41006 [2018-10-12 22:34:32,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4697 states. [2018-10-12 22:34:32,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4697 to 4640. [2018-10-12 22:34:32,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4640 states. [2018-10-12 22:34:32,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4640 states to 4640 states and 4711 transitions. [2018-10-12 22:34:32,148 INFO L78 Accepts]: Start accepts. Automaton has 4640 states and 4711 transitions. Word has length 2125 [2018-10-12 22:34:32,149 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:34:32,149 INFO L481 AbstractCegarLoop]: Abstraction has 4640 states and 4711 transitions. [2018-10-12 22:34:32,149 INFO L482 AbstractCegarLoop]: Interpolant automaton has 100 states. [2018-10-12 22:34:32,149 INFO L276 IsEmpty]: Start isEmpty. Operand 4640 states and 4711 transitions. [2018-10-12 22:34:32,178 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2495 [2018-10-12 22:34:32,178 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:34:32,179 INFO L375 BasicCegarLoop]: trace histogram [54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:34:32,179 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:34:32,179 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:34:32,180 INFO L82 PathProgramCache]: Analyzing trace with hash 1351623892, now seen corresponding path program 28 times [2018-10-12 22:34:32,180 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:34:32,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:34:37,289 INFO L134 CoverageAnalysis]: Checked inductivity of 54163 backedges. 39206 proven. 10154 refuted. 0 times theorem prover too weak. 4803 trivial. 0 not checked. [2018-10-12 22:34:37,289 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:34:37,290 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [44] total 44 [2018-10-12 22:34:37,291 INFO L460 AbstractCegarLoop]: Interpolant automaton has 44 states [2018-10-12 22:34:37,291 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2018-10-12 22:34:37,291 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=249, Invalid=1643, Unknown=0, NotChecked=0, Total=1892 [2018-10-12 22:34:37,292 INFO L87 Difference]: Start difference. First operand 4640 states and 4711 transitions. Second operand 44 states. [2018-10-12 22:34:41,628 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:34:41,628 INFO L93 Difference]: Finished difference Result 4673 states and 4744 transitions. [2018-10-12 22:34:41,628 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 74 states. [2018-10-12 22:34:41,629 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 2494 [2018-10-12 22:34:41,631 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:34:41,634 INFO L225 Difference]: With dead ends: 4673 [2018-10-12 22:34:41,634 INFO L226 Difference]: Without dead ends: 4673 [2018-10-12 22:34:41,636 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2463 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=2059, Invalid=8861, Unknown=0, NotChecked=0, Total=10920 [2018-10-12 22:34:41,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4673 states. [2018-10-12 22:34:41,659 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4673 to 4661. [2018-10-12 22:34:41,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4661 states. [2018-10-12 22:34:41,662 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4661 states to 4661 states and 4732 transitions. [2018-10-12 22:34:41,662 INFO L78 Accepts]: Start accepts. Automaton has 4661 states and 4732 transitions. Word has length 2494 [2018-10-12 22:34:41,663 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:34:41,664 INFO L481 AbstractCegarLoop]: Abstraction has 4661 states and 4732 transitions. [2018-10-12 22:34:41,664 INFO L482 AbstractCegarLoop]: Interpolant automaton has 44 states. [2018-10-12 22:34:41,664 INFO L276 IsEmpty]: Start isEmpty. Operand 4661 states and 4732 transitions. [2018-10-12 22:34:41,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2516 [2018-10-12 22:34:41,698 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:34:41,699 INFO L375 BasicCegarLoop]: trace histogram [55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:34:41,699 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:34:41,700 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:34:41,700 INFO L82 PathProgramCache]: Analyzing trace with hash 1507027520, now seen corresponding path program 29 times [2018-10-12 22:34:41,701 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:34:41,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:34:45,910 INFO L134 CoverageAnalysis]: Checked inductivity of 55308 backedges. 16274 proven. 864 refuted. 0 times theorem prover too weak. 38170 trivial. 0 not checked. [2018-10-12 22:34:45,910 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:34:45,911 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43] total 43 [2018-10-12 22:34:45,912 INFO L460 AbstractCegarLoop]: Interpolant automaton has 43 states [2018-10-12 22:34:45,912 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2018-10-12 22:34:45,912 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=230, Invalid=1576, Unknown=0, NotChecked=0, Total=1806 [2018-10-12 22:34:45,912 INFO L87 Difference]: Start difference. First operand 4661 states and 4732 transitions. Second operand 43 states. [2018-10-12 22:34:50,159 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:34:50,159 INFO L93 Difference]: Finished difference Result 13548 states and 13733 transitions. [2018-10-12 22:34:50,159 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 111 states. [2018-10-12 22:34:50,159 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 2515 [2018-10-12 22:34:50,161 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:34:50,169 INFO L225 Difference]: With dead ends: 13548 [2018-10-12 22:34:50,170 INFO L226 Difference]: Without dead ends: 13548 [2018-10-12 22:34:50,172 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5825 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=3586, Invalid=16436, Unknown=0, NotChecked=0, Total=20022 [2018-10-12 22:34:50,177 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13548 states. [2018-10-12 22:34:50,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13548 to 5105. [2018-10-12 22:34:50,216 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5105 states. [2018-10-12 22:34:50,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5105 states to 5105 states and 5186 transitions. [2018-10-12 22:34:50,219 INFO L78 Accepts]: Start accepts. Automaton has 5105 states and 5186 transitions. Word has length 2515 [2018-10-12 22:34:50,220 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:34:50,220 INFO L481 AbstractCegarLoop]: Abstraction has 5105 states and 5186 transitions. [2018-10-12 22:34:50,221 INFO L482 AbstractCegarLoop]: Interpolant automaton has 43 states. [2018-10-12 22:34:50,221 INFO L276 IsEmpty]: Start isEmpty. Operand 5105 states and 5186 transitions. [2018-10-12 22:34:50,252 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2530 [2018-10-12 22:34:50,252 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:34:50,253 INFO L375 BasicCegarLoop]: trace histogram [55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:34:50,253 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:34:50,253 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:34:50,253 INFO L82 PathProgramCache]: Analyzing trace with hash -1057197076, now seen corresponding path program 30 times [2018-10-12 22:34:50,254 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:34:50,445 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:35:16,696 INFO L134 CoverageAnalysis]: Checked inductivity of 56075 backedges. 0 proven. 50593 refuted. 0 times theorem prover too weak. 5482 trivial. 0 not checked. [2018-10-12 22:35:16,697 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:35:16,697 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [111] total 111 [2018-10-12 22:35:16,699 INFO L460 AbstractCegarLoop]: Interpolant automaton has 111 states [2018-10-12 22:35:16,699 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 111 interpolants. [2018-10-12 22:35:16,700 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=370, Invalid=11840, Unknown=0, NotChecked=0, Total=12210 [2018-10-12 22:35:16,700 INFO L87 Difference]: Start difference. First operand 5105 states and 5186 transitions. Second operand 111 states. [2018-10-12 22:35:45,842 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:35:45,843 INFO L93 Difference]: Finished difference Result 5590 states and 5673 transitions. [2018-10-12 22:35:45,843 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 141 states. [2018-10-12 22:35:45,843 INFO L78 Accepts]: Start accepts. Automaton has 111 states. Word has length 2529 [2018-10-12 22:35:45,845 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:35:45,848 INFO L225 Difference]: With dead ends: 5590 [2018-10-12 22:35:45,848 INFO L226 Difference]: Without dead ends: 5590 [2018-10-12 22:35:45,852 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 244 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 225 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14940 ImplicationChecksByTransitivity, 15.4s TimeCoverageRelationStatistics Valid=1540, Invalid=49762, Unknown=0, NotChecked=0, Total=51302 [2018-10-12 22:35:45,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5590 states. [2018-10-12 22:35:45,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5590 to 5509. [2018-10-12 22:35:45,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5509 states. [2018-10-12 22:35:45,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5509 states to 5509 states and 5592 transitions. [2018-10-12 22:35:45,883 INFO L78 Accepts]: Start accepts. Automaton has 5509 states and 5592 transitions. Word has length 2529 [2018-10-12 22:35:45,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:35:45,884 INFO L481 AbstractCegarLoop]: Abstraction has 5509 states and 5592 transitions. [2018-10-12 22:35:45,884 INFO L482 AbstractCegarLoop]: Interpolant automaton has 111 states. [2018-10-12 22:35:45,884 INFO L276 IsEmpty]: Start isEmpty. Operand 5509 states and 5592 transitions. [2018-10-12 22:35:45,928 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2934 [2018-10-12 22:35:45,928 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:35:45,929 INFO L375 BasicCegarLoop]: trace histogram [65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:35:45,929 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:35:45,929 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:35:45,930 INFO L82 PathProgramCache]: Analyzing trace with hash 936634742, now seen corresponding path program 31 times [2018-10-12 22:35:45,930 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:35:46,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:35:52,217 INFO L134 CoverageAnalysis]: Checked inductivity of 77836 backedges. 57801 proven. 13510 refuted. 0 times theorem prover too weak. 6525 trivial. 0 not checked. [2018-10-12 22:35:52,218 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:35:52,218 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [48] total 48 [2018-10-12 22:35:52,219 INFO L460 AbstractCegarLoop]: Interpolant automaton has 48 states [2018-10-12 22:35:52,220 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2018-10-12 22:35:52,220 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=295, Invalid=1961, Unknown=0, NotChecked=0, Total=2256 [2018-10-12 22:35:52,220 INFO L87 Difference]: Start difference. First operand 5509 states and 5592 transitions. Second operand 48 states. [2018-10-12 22:35:55,686 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:35:55,687 INFO L93 Difference]: Finished difference Result 5542 states and 5625 transitions. [2018-10-12 22:35:55,687 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 81 states. [2018-10-12 22:35:55,687 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 2933 [2018-10-12 22:35:55,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:35:55,693 INFO L225 Difference]: With dead ends: 5542 [2018-10-12 22:35:55,693 INFO L226 Difference]: Without dead ends: 5542 [2018-10-12 22:35:55,694 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2990 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=2472, Invalid=10638, Unknown=0, NotChecked=0, Total=13110 [2018-10-12 22:35:55,696 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5542 states. [2018-10-12 22:35:55,725 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5542 to 5530. [2018-10-12 22:35:55,725 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5530 states. [2018-10-12 22:35:55,730 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5530 states to 5530 states and 5613 transitions. [2018-10-12 22:35:55,730 INFO L78 Accepts]: Start accepts. Automaton has 5530 states and 5613 transitions. Word has length 2933 [2018-10-12 22:35:55,732 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:35:55,732 INFO L481 AbstractCegarLoop]: Abstraction has 5530 states and 5613 transitions. [2018-10-12 22:35:55,732 INFO L482 AbstractCegarLoop]: Interpolant automaton has 48 states. [2018-10-12 22:35:55,732 INFO L276 IsEmpty]: Start isEmpty. Operand 5530 states and 5613 transitions. [2018-10-12 22:35:55,785 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2955 [2018-10-12 22:35:55,786 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:35:55,787 INFO L375 BasicCegarLoop]: trace histogram [66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:35:55,787 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:35:55,787 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:35:55,787 INFO L82 PathProgramCache]: Analyzing trace with hash -1784603722, now seen corresponding path program 32 times [2018-10-12 22:35:55,788 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:35:55,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:36:00,037 INFO L134 CoverageAnalysis]: Checked inductivity of 79213 backedges. 21817 proven. 1032 refuted. 0 times theorem prover too weak. 56364 trivial. 0 not checked. [2018-10-12 22:36:00,037 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:36:00,038 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [47] total 47 [2018-10-12 22:36:00,039 INFO L460 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-10-12 22:36:00,039 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-10-12 22:36:00,039 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=274, Invalid=1888, Unknown=0, NotChecked=0, Total=2162 [2018-10-12 22:36:00,039 INFO L87 Difference]: Start difference. First operand 5530 states and 5613 transitions. Second operand 47 states. [2018-10-12 22:36:06,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:36:06,196 INFO L93 Difference]: Finished difference Result 16820 states and 17040 transitions. [2018-10-12 22:36:06,196 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 122 states. [2018-10-12 22:36:06,197 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 2954 [2018-10-12 22:36:06,198 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:36:06,210 INFO L225 Difference]: With dead ends: 16820 [2018-10-12 22:36:06,211 INFO L226 Difference]: Without dead ends: 16820 [2018-10-12 22:36:06,213 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 154 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7106 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=4331, Invalid=19849, Unknown=0, NotChecked=0, Total=24180 [2018-10-12 22:36:06,220 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16820 states. [2018-10-12 22:36:06,285 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16820 to 6017. [2018-10-12 22:36:06,286 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6017 states. [2018-10-12 22:36:06,291 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6017 states to 6017 states and 6111 transitions. [2018-10-12 22:36:06,291 INFO L78 Accepts]: Start accepts. Automaton has 6017 states and 6111 transitions. Word has length 2954 [2018-10-12 22:36:06,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:36:06,293 INFO L481 AbstractCegarLoop]: Abstraction has 6017 states and 6111 transitions. [2018-10-12 22:36:06,293 INFO L482 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-10-12 22:36:06,293 INFO L276 IsEmpty]: Start isEmpty. Operand 6017 states and 6111 transitions. [2018-10-12 22:36:06,390 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2969 [2018-10-12 22:36:06,390 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:36:06,391 INFO L375 BasicCegarLoop]: trace histogram [66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:36:06,391 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:36:06,392 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:36:06,392 INFO L82 PathProgramCache]: Analyzing trace with hash -240951582, now seen corresponding path program 33 times [2018-10-12 22:36:06,393 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:36:06,675 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-12 22:36:40,967 INFO L134 CoverageAnalysis]: Checked inductivity of 80135 backedges. 0 proven. 72989 refuted. 0 times theorem prover too weak. 7146 trivial. 0 not checked. [2018-10-12 22:36:40,968 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-12 22:36:40,968 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [120] total 120 [2018-10-12 22:36:40,970 INFO L460 AbstractCegarLoop]: Interpolant automaton has 120 states [2018-10-12 22:36:40,970 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 120 interpolants. [2018-10-12 22:36:40,971 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=403, Invalid=13877, Unknown=0, NotChecked=0, Total=14280 [2018-10-12 22:36:40,971 INFO L87 Difference]: Start difference. First operand 6017 states and 6111 transitions. Second operand 120 states. [2018-10-12 22:37:17,668 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-12 22:37:17,669 INFO L93 Difference]: Finished difference Result 6531 states and 6627 transitions. [2018-10-12 22:37:17,669 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 150 states. [2018-10-12 22:37:17,669 INFO L78 Accepts]: Start accepts. Automaton has 120 states. Word has length 2968 [2018-10-12 22:37:17,670 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-12 22:37:17,674 INFO L225 Difference]: With dead ends: 6531 [2018-10-12 22:37:17,674 INFO L226 Difference]: Without dead ends: 6531 [2018-10-12 22:37:17,676 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 266 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 242 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17373 ImplicationChecksByTransitivity, 17.4s TimeCoverageRelationStatistics Valid=1666, Invalid=57626, Unknown=0, NotChecked=0, Total=59292 [2018-10-12 22:37:17,678 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6531 states. [2018-10-12 22:37:17,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6531 to 6456. [2018-10-12 22:37:17,704 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6456 states. [2018-10-12 22:37:17,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6456 states to 6456 states and 6552 transitions. [2018-10-12 22:37:17,709 INFO L78 Accepts]: Start accepts. Automaton has 6456 states and 6552 transitions. Word has length 2968 [2018-10-12 22:37:17,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-12 22:37:17,710 INFO L481 AbstractCegarLoop]: Abstraction has 6456 states and 6552 transitions. [2018-10-12 22:37:17,710 INFO L482 AbstractCegarLoop]: Interpolant automaton has 120 states. [2018-10-12 22:37:17,710 INFO L276 IsEmpty]: Start isEmpty. Operand 6456 states and 6552 transitions. [2018-10-12 22:37:17,765 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3408 [2018-10-12 22:37:17,765 INFO L367 BasicCegarLoop]: Found error trace [2018-10-12 22:37:17,767 INFO L375 BasicCegarLoop]: trace histogram [77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-12 22:37:17,767 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-12 22:37:17,767 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-12 22:37:17,767 INFO L82 PathProgramCache]: Analyzing trace with hash 2135226156, now seen corresponding path program 34 times [2018-10-12 22:37:17,768 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-12 22:37:17,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat