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/standard_strcpy_original_false-valid-deref.i_9.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-b8f97f7-m [2018-10-10 16:47:20,884 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-10 16:47:20,886 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-10 16:47:20,898 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-10 16:47:20,898 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-10 16:47:20,899 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-10 16:47:20,900 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-10 16:47:20,902 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-10 16:47:20,904 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-10 16:47:20,905 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-10 16:47:20,906 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-10 16:47:20,906 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-10 16:47:20,907 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-10 16:47:20,908 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-10 16:47:20,909 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-10 16:47:20,910 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-10 16:47:20,910 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-10 16:47:20,912 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-10 16:47:20,915 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-10 16:47:20,916 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-10 16:47:20,917 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-10 16:47:20,919 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-10 16:47:20,921 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-10 16:47:20,921 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-10 16:47:20,921 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-10 16:47:20,922 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-10 16:47:20,923 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-10 16:47:20,924 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-10 16:47:20,925 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-10 16:47:20,926 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-10 16:47:20,926 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-10 16:47:20,927 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-10 16:47:20,927 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-10 16:47:20,927 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-10 16:47:20,928 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-10 16:47:20,929 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-10 16:47:20,929 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/heapseparator/heapsep-2018-09-18.epf [2018-10-10 16:47:20,939 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-10 16:47:20,940 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-10 16:47:20,940 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-10 16:47:20,941 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-10 16:47:20,942 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-10 16:47:20,942 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-10 16:47:20,943 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-10 16:47:20,943 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-10 16:47:20,943 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-10 16:47:20,943 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-10 16:47:20,944 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-10 16:47:20,944 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-10 16:47:20,944 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-10 16:47:20,945 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-10 16:47:20,945 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-10 16:47:20,990 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-10 16:47:21,006 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-10 16:47:21,012 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-10 16:47:21,014 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-10 16:47:21,015 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-10 16:47:21,015 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/standard_strcpy_original_false-valid-deref.i_9.bpl [2018-10-10 16:47:21,016 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/standard_strcpy_original_false-valid-deref.i_9.bpl' [2018-10-10 16:47:21,081 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-10 16:47:21,083 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-10-10 16:47:21,083 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-10 16:47:21,084 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-10 16:47:21,084 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-10 16:47:21,104 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:47:21" (1/1) ... [2018-10-10 16:47:21,106 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:47:21" (1/1) ... [2018-10-10 16:47:21,119 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:47:21" (1/1) ... [2018-10-10 16:47:21,120 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:47:21" (1/1) ... [2018-10-10 16:47:21,127 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:47:21" (1/1) ... [2018-10-10 16:47:21,129 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:47:21" (1/1) ... [2018-10-10 16:47:21,130 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:47:21" (1/1) ... [2018-10-10 16:47:21,133 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-10 16:47:21,134 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-10 16:47:21,134 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-10 16:47:21,134 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-10 16:47:21,135 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:47:21" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-10-10 16:47:21,229 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2018-10-10 16:47:21,229 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-10 16:47:21,230 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-10 16:47:21,803 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-10 16:47:21,804 INFO L202 PluginConnector]: Adding new model standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 04:47:21 BoogieIcfgContainer [2018-10-10 16:47:21,804 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-10 16:47:21,804 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-10-10 16:47:21,805 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-10-10 16:47:21,806 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-10-10 16:47:21,810 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 04:47:21" (1/1) ... [2018-10-10 16:47:21,821 INFO L137 apSepIcfgTransformer]: HeapSepIcfgTransformer: Starting heap partitioning [2018-10-10 16:47:21,821 INFO L138 apSepIcfgTransformer]: To be partitioned heap arrays found [#memory_int] [2018-10-10 16:47:21,863 INFO L191 apSepIcfgTransformer]: Heap separator: starting loc-array-style preprocessing [2018-10-10 16:47:21,937 INFO L217 apSepIcfgTransformer]: finished MemlocArrayUpdater [2018-10-10 16:47:21,960 INFO L280 apSepIcfgTransformer]: finished preprocessing for the equality analysis [2018-10-10 16:47:22,042 INFO L101 FixpointEngine]: Starting fixpoint engine with domain VPDomain (maxUnwinding=3, maxParallelStates=1) [2018-10-10 16:47:32,477 INFO L315 AbstractInterpreter]: Visited 58 different actions 120 times. Merged at 30 different actions 60 times. Never widened. Found 1 fixpoints after 1 different actions. Largest state had 0 variables. [2018-10-10 16:47:32,480 INFO L304 apSepIcfgTransformer]: finished equality analysis [2018-10-10 16:47:32,486 INFO L316 apSepIcfgTransformer]: Finished detection of select terms ("array reads") [2018-10-10 16:47:32,535 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_7|) at (assume #memory_int == write~int_old_#memory_int[write~int_#ptr.base := write~int_old_#memory_int[write~int_#ptr.base][write~int_#ptr.offset := write~int_#value]];) [2018-10-10 16:47:32,543 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-10 16:47:32,543 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-10 16:47:32,546 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-10 16:47:32,547 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-10 16:47:32,548 INFO L232 HeapPartitionManager]: partitioning result: [2018-10-10 16:47:32,553 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-10 16:47:32,553 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-10 16:47:32,553 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-10 16:47:32,553 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-10 16:47:32,554 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-10 16:47:32,554 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-10 16:47:32,554 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-10 16:47:32,554 INFO L237 HeapPartitionManager]: location blocks for array group [#memory_int, ULTIMATE.start_write~int_old_#memory_int] [2018-10-10 16:47:32,554 INFO L246 HeapPartitionManager]: at dimension 1 [2018-10-10 16:47:32,555 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-10 16:47:32,555 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-10 16:47:32,557 INFO L246 HeapPartitionManager]: at dimension 2 [2018-10-10 16:47:32,557 INFO L247 HeapPartitionManager]: # array writes (possibly including 1 dummy write/NoStoreIndexInfo) : 1 [2018-10-10 16:47:32,557 INFO L248 HeapPartitionManager]: # location blocks :1 [2018-10-10 16:47:32,558 INFO L145 ransitionTransformer]: executing heap partitioning transformation [2018-10-10 16:47:32,588 INFO L202 PluginConnector]: Adding new model standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 10.10 04:47:32 BasicIcfg [2018-10-10 16:47:32,588 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-10-10 16:47:32,589 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-10 16:47:32,589 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-10 16:47:32,595 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-10 16:47:32,595 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 04:47:21" (1/3) ... [2018-10-10 16:47:32,597 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@426f7e39 and model type standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.10 04:47:32, skipping insertion in model container [2018-10-10 16:47:32,597 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 04:47:21" (2/3) ... [2018-10-10 16:47:32,597 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@426f7e39 and model type standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 10.10 04:47:32, skipping insertion in model container [2018-10-10 16:47:32,597 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "standard_strcpy_original_false-valid-deref.i_9.bpl de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 10.10 04:47:32" (3/3) ... [2018-10-10 16:47:32,599 INFO L112 eAbstractionObserver]: Analyzing ICFG memPartitionedIcfg [2018-10-10 16:47:32,609 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-10 16:47:32,618 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-10 16:47:32,636 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-10 16:47:32,666 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-10 16:47:32,667 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-10 16:47:32,667 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-10 16:47:32,667 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-10 16:47:32,667 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-10 16:47:32,667 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-10 16:47:32,668 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-10 16:47:32,668 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-10 16:47:32,668 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-10 16:47:32,684 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states. [2018-10-10 16:47:32,697 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2018-10-10 16:47:32,697 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:32,698 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] [2018-10-10 16:47:32,699 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:32,705 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:32,706 INFO L82 PathProgramCache]: Analyzing trace with hash 216808173, now seen corresponding path program 1 times [2018-10-10 16:47:32,772 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:32,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:33,516 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:33,520 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-10 16:47:33,521 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-10-10 16:47:33,526 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-10-10 16:47:33,539 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-10-10 16:47:33,540 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2018-10-10 16:47:33,543 INFO L87 Difference]: Start difference. First operand 58 states. Second operand 8 states. [2018-10-10 16:47:34,414 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:34,416 INFO L93 Difference]: Finished difference Result 104 states and 104 transitions. [2018-10-10 16:47:34,416 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-10 16:47:34,418 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 49 [2018-10-10 16:47:34,418 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:34,508 INFO L225 Difference]: With dead ends: 104 [2018-10-10 16:47:34,509 INFO L226 Difference]: Without dead ends: 104 [2018-10-10 16:47:34,510 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=57, Invalid=99, Unknown=0, NotChecked=0, Total=156 [2018-10-10 16:47:34,530 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2018-10-10 16:47:34,550 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 78. [2018-10-10 16:47:34,552 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 78 states. [2018-10-10 16:47:34,553 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 78 transitions. [2018-10-10 16:47:34,555 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 78 transitions. Word has length 49 [2018-10-10 16:47:34,555 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:34,555 INFO L481 AbstractCegarLoop]: Abstraction has 78 states and 78 transitions. [2018-10-10 16:47:34,556 INFO L482 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-10-10 16:47:34,556 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 78 transitions. [2018-10-10 16:47:34,558 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2018-10-10 16:47:34,558 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:34,559 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:34,559 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:34,559 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:34,560 INFO L82 PathProgramCache]: Analyzing trace with hash -783516803, now seen corresponding path program 1 times [2018-10-10 16:47:34,561 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:34,592 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:35,240 WARN L178 SmtUtils]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-10-10 16:47:35,437 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:35,437 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:35,437 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-10 16:47:35,439 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-10 16:47:35,440 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-10 16:47:35,440 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2018-10-10 16:47:35,440 INFO L87 Difference]: Start difference. First operand 78 states and 78 transitions. Second operand 13 states. [2018-10-10 16:47:36,244 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:36,244 INFO L93 Difference]: Finished difference Result 132 states and 132 transitions. [2018-10-10 16:47:36,246 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-10-10 16:47:36,246 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 77 [2018-10-10 16:47:36,248 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:36,251 INFO L225 Difference]: With dead ends: 132 [2018-10-10 16:47:36,252 INFO L226 Difference]: Without dead ends: 132 [2018-10-10 16:47:36,253 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=129, Invalid=291, Unknown=0, NotChecked=0, Total=420 [2018-10-10 16:47:36,255 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2018-10-10 16:47:36,275 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 106. [2018-10-10 16:47:36,277 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 106 states. [2018-10-10 16:47:36,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 106 transitions. [2018-10-10 16:47:36,280 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 106 transitions. Word has length 77 [2018-10-10 16:47:36,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:36,281 INFO L481 AbstractCegarLoop]: Abstraction has 106 states and 106 transitions. [2018-10-10 16:47:36,281 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-10 16:47:36,282 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 106 transitions. [2018-10-10 16:47:36,288 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2018-10-10 16:47:36,288 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:36,289 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, 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-10 16:47:36,289 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:36,289 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:36,289 INFO L82 PathProgramCache]: Analyzing trace with hash 2076001293, now seen corresponding path program 2 times [2018-10-10 16:47:36,291 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:36,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:36,782 INFO L134 CoverageAnalysis]: Checked inductivity of 72 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:36,782 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:36,782 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2018-10-10 16:47:36,783 INFO L460 AbstractCegarLoop]: Interpolant automaton has 14 states [2018-10-10 16:47:36,783 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2018-10-10 16:47:36,783 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2018-10-10 16:47:36,784 INFO L87 Difference]: Start difference. First operand 106 states and 106 transitions. Second operand 14 states. [2018-10-10 16:47:37,469 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:37,469 INFO L93 Difference]: Finished difference Result 160 states and 160 transitions. [2018-10-10 16:47:37,472 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-10 16:47:37,472 INFO L78 Accepts]: Start accepts. Automaton has 14 states. Word has length 105 [2018-10-10 16:47:37,473 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:37,474 INFO L225 Difference]: With dead ends: 160 [2018-10-10 16:47:37,474 INFO L226 Difference]: Without dead ends: 160 [2018-10-10 16:47:37,475 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=145, Invalid=361, Unknown=0, NotChecked=0, Total=506 [2018-10-10 16:47:37,475 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2018-10-10 16:47:37,483 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 134. [2018-10-10 16:47:37,484 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 134 states. [2018-10-10 16:47:37,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 134 transitions. [2018-10-10 16:47:37,485 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 134 transitions. Word has length 105 [2018-10-10 16:47:37,485 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:37,486 INFO L481 AbstractCegarLoop]: Abstraction has 134 states and 134 transitions. [2018-10-10 16:47:37,486 INFO L482 AbstractCegarLoop]: Interpolant automaton has 14 states. [2018-10-10 16:47:37,486 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 134 transitions. [2018-10-10 16:47:37,488 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 134 [2018-10-10 16:47:37,488 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:37,488 INFO L375 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:37,488 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:37,489 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:37,489 INFO L82 PathProgramCache]: Analyzing trace with hash -979200867, now seen corresponding path program 3 times [2018-10-10 16:47:37,490 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:37,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:37,991 INFO L134 CoverageAnalysis]: Checked inductivity of 150 backedges. 0 proven. 150 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:37,992 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:37,992 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-10-10 16:47:37,993 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-10 16:47:37,993 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-10 16:47:37,993 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=164, Unknown=0, NotChecked=0, Total=210 [2018-10-10 16:47:37,994 INFO L87 Difference]: Start difference. First operand 134 states and 134 transitions. Second operand 15 states. [2018-10-10 16:47:39,245 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:39,246 INFO L93 Difference]: Finished difference Result 188 states and 188 transitions. [2018-10-10 16:47:39,249 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-10 16:47:39,250 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 133 [2018-10-10 16:47:39,250 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:39,251 INFO L225 Difference]: With dead ends: 188 [2018-10-10 16:47:39,252 INFO L226 Difference]: Without dead ends: 188 [2018-10-10 16:47:39,252 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 74 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=161, Invalid=439, Unknown=0, NotChecked=0, Total=600 [2018-10-10 16:47:39,253 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2018-10-10 16:47:39,262 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 162. [2018-10-10 16:47:39,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 162 states. [2018-10-10 16:47:39,263 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 162 states to 162 states and 162 transitions. [2018-10-10 16:47:39,264 INFO L78 Accepts]: Start accepts. Automaton has 162 states and 162 transitions. Word has length 133 [2018-10-10 16:47:39,264 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:39,264 INFO L481 AbstractCegarLoop]: Abstraction has 162 states and 162 transitions. [2018-10-10 16:47:39,264 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-10 16:47:39,264 INFO L276 IsEmpty]: Start isEmpty. Operand 162 states and 162 transitions. [2018-10-10 16:47:39,267 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 162 [2018-10-10 16:47:39,267 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:39,267 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, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:39,267 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:39,268 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:39,268 INFO L82 PathProgramCache]: Analyzing trace with hash 710962477, now seen corresponding path program 4 times [2018-10-10 16:47:39,269 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:39,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:40,216 INFO L134 CoverageAnalysis]: Checked inductivity of 256 backedges. 0 proven. 256 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:40,216 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:40,217 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2018-10-10 16:47:40,217 INFO L460 AbstractCegarLoop]: Interpolant automaton has 16 states [2018-10-10 16:47:40,217 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2018-10-10 16:47:40,217 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=190, Unknown=0, NotChecked=0, Total=240 [2018-10-10 16:47:40,218 INFO L87 Difference]: Start difference. First operand 162 states and 162 transitions. Second operand 16 states. [2018-10-10 16:47:41,219 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:41,219 INFO L93 Difference]: Finished difference Result 216 states and 216 transitions. [2018-10-10 16:47:41,219 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-10-10 16:47:41,220 INFO L78 Accepts]: Start accepts. Automaton has 16 states. Word has length 161 [2018-10-10 16:47:41,220 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:41,221 INFO L225 Difference]: With dead ends: 216 [2018-10-10 16:47:41,221 INFO L226 Difference]: Without dead ends: 216 [2018-10-10 16:47:41,222 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=177, Invalid=525, Unknown=0, NotChecked=0, Total=702 [2018-10-10 16:47:41,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 216 states. [2018-10-10 16:47:41,231 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 216 to 190. [2018-10-10 16:47:41,231 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 190 states. [2018-10-10 16:47:41,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 190 transitions. [2018-10-10 16:47:41,232 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 190 transitions. Word has length 161 [2018-10-10 16:47:41,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:41,233 INFO L481 AbstractCegarLoop]: Abstraction has 190 states and 190 transitions. [2018-10-10 16:47:41,233 INFO L482 AbstractCegarLoop]: Interpolant automaton has 16 states. [2018-10-10 16:47:41,233 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 190 transitions. [2018-10-10 16:47:41,236 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 190 [2018-10-10 16:47:41,237 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:41,237 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, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:41,237 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:41,237 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:41,238 INFO L82 PathProgramCache]: Analyzing trace with hash -413479491, now seen corresponding path program 5 times [2018-10-10 16:47:41,238 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:41,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:41,841 INFO L134 CoverageAnalysis]: Checked inductivity of 390 backedges. 0 proven. 390 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:41,841 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:41,841 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-10 16:47:41,842 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-10 16:47:41,842 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-10 16:47:41,842 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=218, Unknown=0, NotChecked=0, Total=272 [2018-10-10 16:47:41,843 INFO L87 Difference]: Start difference. First operand 190 states and 190 transitions. Second operand 17 states. [2018-10-10 16:47:42,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:42,975 INFO L93 Difference]: Finished difference Result 244 states and 244 transitions. [2018-10-10 16:47:42,975 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-10 16:47:42,976 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 189 [2018-10-10 16:47:42,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:42,977 INFO L225 Difference]: With dead ends: 244 [2018-10-10 16:47:42,978 INFO L226 Difference]: Without dead ends: 244 [2018-10-10 16:47:42,979 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 105 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=193, Invalid=619, Unknown=0, NotChecked=0, Total=812 [2018-10-10 16:47:42,979 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 244 states. [2018-10-10 16:47:42,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 244 to 218. [2018-10-10 16:47:42,987 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 218 states. [2018-10-10 16:47:42,988 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 218 states to 218 states and 218 transitions. [2018-10-10 16:47:42,989 INFO L78 Accepts]: Start accepts. Automaton has 218 states and 218 transitions. Word has length 189 [2018-10-10 16:47:42,989 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:42,989 INFO L481 AbstractCegarLoop]: Abstraction has 218 states and 218 transitions. [2018-10-10 16:47:42,990 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-10 16:47:42,990 INFO L276 IsEmpty]: Start isEmpty. Operand 218 states and 218 transitions. [2018-10-10 16:47:42,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 218 [2018-10-10 16:47:42,994 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:42,994 INFO L375 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:42,995 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:42,995 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:42,995 INFO L82 PathProgramCache]: Analyzing trace with hash -67783091, now seen corresponding path program 6 times [2018-10-10 16:47:42,996 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:43,021 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:44,532 INFO L134 CoverageAnalysis]: Checked inductivity of 552 backedges. 0 proven. 552 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:44,533 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:44,533 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2018-10-10 16:47:44,533 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-10-10 16:47:44,534 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-10-10 16:47:44,534 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2018-10-10 16:47:44,535 INFO L87 Difference]: Start difference. First operand 218 states and 218 transitions. Second operand 18 states. [2018-10-10 16:47:45,848 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:45,849 INFO L93 Difference]: Finished difference Result 272 states and 272 transitions. [2018-10-10 16:47:45,849 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-10 16:47:45,849 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 217 [2018-10-10 16:47:45,850 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:45,852 INFO L225 Difference]: With dead ends: 272 [2018-10-10 16:47:45,852 INFO L226 Difference]: Without dead ends: 272 [2018-10-10 16:47:45,853 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 122 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=209, Invalid=721, Unknown=0, NotChecked=0, Total=930 [2018-10-10 16:47:45,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 272 states. [2018-10-10 16:47:45,860 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 272 to 246. [2018-10-10 16:47:45,860 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 246 states. [2018-10-10 16:47:45,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 246 states to 246 states and 246 transitions. [2018-10-10 16:47:45,861 INFO L78 Accepts]: Start accepts. Automaton has 246 states and 246 transitions. Word has length 217 [2018-10-10 16:47:45,862 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:45,862 INFO L481 AbstractCegarLoop]: Abstraction has 246 states and 246 transitions. [2018-10-10 16:47:45,862 INFO L482 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-10-10 16:47:45,862 INFO L276 IsEmpty]: Start isEmpty. Operand 246 states and 246 transitions. [2018-10-10 16:47:45,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 246 [2018-10-10 16:47:45,866 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:45,867 INFO L375 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:45,867 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:45,867 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:45,867 INFO L82 PathProgramCache]: Analyzing trace with hash 697640669, now seen corresponding path program 7 times [2018-10-10 16:47:45,868 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:45,893 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:46,589 INFO L134 CoverageAnalysis]: Checked inductivity of 742 backedges. 0 proven. 742 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:46,589 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:46,589 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-10-10 16:47:46,590 INFO L460 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-10 16:47:46,590 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-10 16:47:46,591 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=62, Invalid=280, Unknown=0, NotChecked=0, Total=342 [2018-10-10 16:47:46,591 INFO L87 Difference]: Start difference. First operand 246 states and 246 transitions. Second operand 19 states. [2018-10-10 16:47:48,245 WARN L178 SmtUtils]: Spent 201.00 ms on a formula simplification that was a NOOP. DAG size: 34 [2018-10-10 16:47:48,414 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:48,414 INFO L93 Difference]: Finished difference Result 300 states and 300 transitions. [2018-10-10 16:47:48,415 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-10-10 16:47:48,415 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 245 [2018-10-10 16:47:48,416 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:48,417 INFO L225 Difference]: With dead ends: 300 [2018-10-10 16:47:48,417 INFO L226 Difference]: Without dead ends: 300 [2018-10-10 16:47:48,418 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 140 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=225, Invalid=831, Unknown=0, NotChecked=0, Total=1056 [2018-10-10 16:47:48,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 300 states. [2018-10-10 16:47:48,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 300 to 274. [2018-10-10 16:47:48,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 274 states. [2018-10-10 16:47:48,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 274 transitions. [2018-10-10 16:47:48,424 INFO L78 Accepts]: Start accepts. Automaton has 274 states and 274 transitions. Word has length 245 [2018-10-10 16:47:48,425 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:48,425 INFO L481 AbstractCegarLoop]: Abstraction has 274 states and 274 transitions. [2018-10-10 16:47:48,425 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-10 16:47:48,425 INFO L276 IsEmpty]: Start isEmpty. Operand 274 states and 274 transitions. [2018-10-10 16:47:48,427 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 274 [2018-10-10 16:47:48,428 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:48,428 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, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:48,428 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:48,428 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:48,429 INFO L82 PathProgramCache]: Analyzing trace with hash -207806611, now seen corresponding path program 8 times [2018-10-10 16:47:48,429 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:48,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:49,324 INFO L134 CoverageAnalysis]: Checked inductivity of 960 backedges. 0 proven. 960 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:49,324 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:49,324 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [20] total 20 [2018-10-10 16:47:49,325 INFO L460 AbstractCegarLoop]: Interpolant automaton has 20 states [2018-10-10 16:47:49,325 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2018-10-10 16:47:49,326 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2018-10-10 16:47:49,326 INFO L87 Difference]: Start difference. First operand 274 states and 274 transitions. Second operand 20 states. [2018-10-10 16:47:51,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:51,335 INFO L93 Difference]: Finished difference Result 328 states and 328 transitions. [2018-10-10 16:47:51,336 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-10-10 16:47:51,336 INFO L78 Accepts]: Start accepts. Automaton has 20 states. Word has length 273 [2018-10-10 16:47:51,337 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:51,338 INFO L225 Difference]: With dead ends: 328 [2018-10-10 16:47:51,338 INFO L226 Difference]: Without dead ends: 328 [2018-10-10 16:47:51,339 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 159 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=241, Invalid=949, Unknown=0, NotChecked=0, Total=1190 [2018-10-10 16:47:51,340 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 328 states. [2018-10-10 16:47:51,344 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 328 to 302. [2018-10-10 16:47:51,344 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 302 states. [2018-10-10 16:47:51,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 302 states to 302 states and 302 transitions. [2018-10-10 16:47:51,345 INFO L78 Accepts]: Start accepts. Automaton has 302 states and 302 transitions. Word has length 273 [2018-10-10 16:47:51,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:51,346 INFO L481 AbstractCegarLoop]: Abstraction has 302 states and 302 transitions. [2018-10-10 16:47:51,346 INFO L482 AbstractCegarLoop]: Interpolant automaton has 20 states. [2018-10-10 16:47:51,346 INFO L276 IsEmpty]: Start isEmpty. Operand 302 states and 302 transitions. [2018-10-10 16:47:51,348 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 302 [2018-10-10 16:47:51,348 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:51,348 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, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:51,349 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:51,349 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:51,349 INFO L82 PathProgramCache]: Analyzing trace with hash -1619943427, now seen corresponding path program 9 times [2018-10-10 16:47:51,350 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:51,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:52,528 INFO L134 CoverageAnalysis]: Checked inductivity of 1206 backedges. 0 proven. 1206 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:52,528 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:52,528 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-10 16:47:52,529 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-10 16:47:52,529 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-10 16:47:52,530 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2018-10-10 16:47:52,530 INFO L87 Difference]: Start difference. First operand 302 states and 302 transitions. Second operand 21 states. [2018-10-10 16:47:54,656 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:54,656 INFO L93 Difference]: Finished difference Result 356 states and 356 transitions. [2018-10-10 16:47:54,657 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-10-10 16:47:54,657 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 301 [2018-10-10 16:47:54,658 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:54,659 INFO L225 Difference]: With dead ends: 356 [2018-10-10 16:47:54,659 INFO L226 Difference]: Without dead ends: 356 [2018-10-10 16:47:54,660 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=257, Invalid=1075, Unknown=0, NotChecked=0, Total=1332 [2018-10-10 16:47:54,661 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 356 states. [2018-10-10 16:47:54,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 356 to 330. [2018-10-10 16:47:54,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 330 states. [2018-10-10 16:47:54,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 330 states to 330 states and 330 transitions. [2018-10-10 16:47:54,667 INFO L78 Accepts]: Start accepts. Automaton has 330 states and 330 transitions. Word has length 301 [2018-10-10 16:47:54,667 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:54,667 INFO L481 AbstractCegarLoop]: Abstraction has 330 states and 330 transitions. [2018-10-10 16:47:54,668 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-10 16:47:54,668 INFO L276 IsEmpty]: Start isEmpty. Operand 330 states and 330 transitions. [2018-10-10 16:47:54,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 330 [2018-10-10 16:47:54,669 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:54,669 INFO L375 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:54,669 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:54,670 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:54,670 INFO L82 PathProgramCache]: Analyzing trace with hash 880191629, now seen corresponding path program 10 times [2018-10-10 16:47:54,671 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:54,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:55,879 INFO L134 CoverageAnalysis]: Checked inductivity of 1480 backedges. 0 proven. 1480 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:55,880 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:55,880 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2018-10-10 16:47:55,881 INFO L460 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-10-10 16:47:55,881 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-10-10 16:47:55,881 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=388, Unknown=0, NotChecked=0, Total=462 [2018-10-10 16:47:55,882 INFO L87 Difference]: Start difference. First operand 330 states and 330 transitions. Second operand 22 states. [2018-10-10 16:47:57,998 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:47:57,999 INFO L93 Difference]: Finished difference Result 384 states and 384 transitions. [2018-10-10 16:47:57,999 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-10-10 16:47:57,999 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 329 [2018-10-10 16:47:58,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:47:58,001 INFO L225 Difference]: With dead ends: 384 [2018-10-10 16:47:58,002 INFO L226 Difference]: Without dead ends: 384 [2018-10-10 16:47:58,002 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 200 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=273, Invalid=1209, Unknown=0, NotChecked=0, Total=1482 [2018-10-10 16:47:58,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 384 states. [2018-10-10 16:47:58,007 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 384 to 358. [2018-10-10 16:47:58,007 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 358 states. [2018-10-10 16:47:58,008 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 358 states to 358 states and 358 transitions. [2018-10-10 16:47:58,008 INFO L78 Accepts]: Start accepts. Automaton has 358 states and 358 transitions. Word has length 329 [2018-10-10 16:47:58,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:47:58,009 INFO L481 AbstractCegarLoop]: Abstraction has 358 states and 358 transitions. [2018-10-10 16:47:58,009 INFO L482 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-10-10 16:47:58,009 INFO L276 IsEmpty]: Start isEmpty. Operand 358 states and 358 transitions. [2018-10-10 16:47:58,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 358 [2018-10-10 16:47:58,011 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:47:58,012 INFO L375 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:47:58,012 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:47:58,012 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:47:58,012 INFO L82 PathProgramCache]: Analyzing trace with hash 2081437981, now seen corresponding path program 11 times [2018-10-10 16:47:58,013 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:47:58,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:47:59,231 INFO L134 CoverageAnalysis]: Checked inductivity of 1782 backedges. 0 proven. 1782 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:47:59,232 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:47:59,232 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2018-10-10 16:47:59,233 INFO L460 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-10 16:47:59,233 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-10 16:47:59,233 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=78, Invalid=428, Unknown=0, NotChecked=0, Total=506 [2018-10-10 16:47:59,233 INFO L87 Difference]: Start difference. First operand 358 states and 358 transitions. Second operand 23 states. [2018-10-10 16:48:01,781 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:48:01,782 INFO L93 Difference]: Finished difference Result 412 states and 412 transitions. [2018-10-10 16:48:01,782 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-10 16:48:01,783 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 357 [2018-10-10 16:48:01,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:48:01,785 INFO L225 Difference]: With dead ends: 412 [2018-10-10 16:48:01,785 INFO L226 Difference]: Without dead ends: 412 [2018-10-10 16:48:01,786 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 222 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=289, Invalid=1351, Unknown=0, NotChecked=0, Total=1640 [2018-10-10 16:48:01,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 412 states. [2018-10-10 16:48:01,791 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 412 to 386. [2018-10-10 16:48:01,792 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 386 states. [2018-10-10 16:48:01,793 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 386 states to 386 states and 386 transitions. [2018-10-10 16:48:01,793 INFO L78 Accepts]: Start accepts. Automaton has 386 states and 386 transitions. Word has length 357 [2018-10-10 16:48:01,794 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:48:01,794 INFO L481 AbstractCegarLoop]: Abstraction has 386 states and 386 transitions. [2018-10-10 16:48:01,794 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-10 16:48:01,794 INFO L276 IsEmpty]: Start isEmpty. Operand 386 states and 386 transitions. [2018-10-10 16:48:01,796 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 386 [2018-10-10 16:48:01,796 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:48:01,797 INFO L375 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:48:01,797 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:48:01,797 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:48:01,797 INFO L82 PathProgramCache]: Analyzing trace with hash 27414957, now seen corresponding path program 12 times [2018-10-10 16:48:01,798 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:48:01,830 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:48:03,003 INFO L134 CoverageAnalysis]: Checked inductivity of 2112 backedges. 0 proven. 2112 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:48:03,003 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:48:03,003 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2018-10-10 16:48:03,004 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-10-10 16:48:03,004 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-10-10 16:48:03,004 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=470, Unknown=0, NotChecked=0, Total=552 [2018-10-10 16:48:03,005 INFO L87 Difference]: Start difference. First operand 386 states and 386 transitions. Second operand 24 states. [2018-10-10 16:48:05,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:48:05,785 INFO L93 Difference]: Finished difference Result 440 states and 440 transitions. [2018-10-10 16:48:05,785 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-10 16:48:05,785 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 385 [2018-10-10 16:48:05,786 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:48:05,787 INFO L225 Difference]: With dead ends: 440 [2018-10-10 16:48:05,788 INFO L226 Difference]: Without dead ends: 440 [2018-10-10 16:48:05,789 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 245 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=305, Invalid=1501, Unknown=0, NotChecked=0, Total=1806 [2018-10-10 16:48:05,789 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 440 states. [2018-10-10 16:48:05,794 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 440 to 414. [2018-10-10 16:48:05,794 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 414 states. [2018-10-10 16:48:05,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 414 states to 414 states and 414 transitions. [2018-10-10 16:48:05,796 INFO L78 Accepts]: Start accepts. Automaton has 414 states and 414 transitions. Word has length 385 [2018-10-10 16:48:05,797 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:48:05,797 INFO L481 AbstractCegarLoop]: Abstraction has 414 states and 414 transitions. [2018-10-10 16:48:05,797 INFO L482 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-10-10 16:48:05,797 INFO L276 IsEmpty]: Start isEmpty. Operand 414 states and 414 transitions. [2018-10-10 16:48:05,799 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 414 [2018-10-10 16:48:05,799 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:48:05,800 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, 13, 13, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:48:05,800 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:48:05,800 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:48:05,801 INFO L82 PathProgramCache]: Analyzing trace with hash 311489085, now seen corresponding path program 13 times [2018-10-10 16:48:05,801 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:48:05,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:48:07,651 INFO L134 CoverageAnalysis]: Checked inductivity of 2470 backedges. 0 proven. 2470 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:48:07,652 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:48:07,652 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-10 16:48:07,652 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-10 16:48:07,652 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-10 16:48:07,653 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=86, Invalid=514, Unknown=0, NotChecked=0, Total=600 [2018-10-10 16:48:07,653 INFO L87 Difference]: Start difference. First operand 414 states and 414 transitions. Second operand 25 states. [2018-10-10 16:48:11,122 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:48:11,122 INFO L93 Difference]: Finished difference Result 468 states and 468 transitions. [2018-10-10 16:48:11,122 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-10-10 16:48:11,122 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 413 [2018-10-10 16:48:11,123 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:48:11,125 INFO L225 Difference]: With dead ends: 468 [2018-10-10 16:48:11,125 INFO L226 Difference]: Without dead ends: 468 [2018-10-10 16:48:11,126 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 269 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=321, Invalid=1659, Unknown=0, NotChecked=0, Total=1980 [2018-10-10 16:48:11,127 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 468 states. [2018-10-10 16:48:11,132 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 468 to 442. [2018-10-10 16:48:11,132 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 442 states. [2018-10-10 16:48:11,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 442 states to 442 states and 442 transitions. [2018-10-10 16:48:11,134 INFO L78 Accepts]: Start accepts. Automaton has 442 states and 442 transitions. Word has length 413 [2018-10-10 16:48:11,135 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:48:11,135 INFO L481 AbstractCegarLoop]: Abstraction has 442 states and 442 transitions. [2018-10-10 16:48:11,135 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-10 16:48:11,136 INFO L276 IsEmpty]: Start isEmpty. Operand 442 states and 442 transitions. [2018-10-10 16:48:11,138 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 442 [2018-10-10 16:48:11,138 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:48:11,139 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:48:11,139 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:48:11,139 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:48:11,139 INFO L82 PathProgramCache]: Analyzing trace with hash -1103095091, now seen corresponding path program 14 times [2018-10-10 16:48:11,140 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:48:11,177 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:48:11,967 WARN L178 SmtUtils]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-10-10 16:48:12,397 WARN L178 SmtUtils]: Spent 110.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-10-10 16:48:13,556 INFO L134 CoverageAnalysis]: Checked inductivity of 2856 backedges. 0 proven. 2856 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:48:13,556 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:48:13,556 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [26] total 26 [2018-10-10 16:48:13,557 INFO L460 AbstractCegarLoop]: Interpolant automaton has 26 states [2018-10-10 16:48:13,557 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2018-10-10 16:48:13,557 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=560, Unknown=0, NotChecked=0, Total=650 [2018-10-10 16:48:13,558 INFO L87 Difference]: Start difference. First operand 442 states and 442 transitions. Second operand 26 states. [2018-10-10 16:48:17,163 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:48:17,163 INFO L93 Difference]: Finished difference Result 496 states and 496 transitions. [2018-10-10 16:48:17,163 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-10-10 16:48:17,163 INFO L78 Accepts]: Start accepts. Automaton has 26 states. Word has length 441 [2018-10-10 16:48:17,164 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:48:17,166 INFO L225 Difference]: With dead ends: 496 [2018-10-10 16:48:17,166 INFO L226 Difference]: Without dead ends: 496 [2018-10-10 16:48:17,167 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 294 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=337, Invalid=1825, Unknown=0, NotChecked=0, Total=2162 [2018-10-10 16:48:17,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 496 states. [2018-10-10 16:48:17,173 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 496 to 470. [2018-10-10 16:48:17,173 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 470 states. [2018-10-10 16:48:17,174 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 470 states to 470 states and 470 transitions. [2018-10-10 16:48:17,174 INFO L78 Accepts]: Start accepts. Automaton has 470 states and 470 transitions. Word has length 441 [2018-10-10 16:48:17,175 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:48:17,175 INFO L481 AbstractCegarLoop]: Abstraction has 470 states and 470 transitions. [2018-10-10 16:48:17,175 INFO L482 AbstractCegarLoop]: Interpolant automaton has 26 states. [2018-10-10 16:48:17,175 INFO L276 IsEmpty]: Start isEmpty. Operand 470 states and 470 transitions. [2018-10-10 16:48:17,178 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 470 [2018-10-10 16:48:17,178 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:48:17,178 INFO L375 BasicCegarLoop]: trace histogram [16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:48:17,178 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:48:17,179 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:48:17,179 INFO L82 PathProgramCache]: Analyzing trace with hash -703345827, now seen corresponding path program 15 times [2018-10-10 16:48:17,180 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:48:17,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:48:19,220 INFO L134 CoverageAnalysis]: Checked inductivity of 3270 backedges. 0 proven. 3270 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:48:19,220 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:48:19,221 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2018-10-10 16:48:19,221 INFO L460 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-10-10 16:48:19,222 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-10-10 16:48:19,222 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=608, Unknown=0, NotChecked=0, Total=702 [2018-10-10 16:48:19,222 INFO L87 Difference]: Start difference. First operand 470 states and 470 transitions. Second operand 27 states. [2018-10-10 16:48:22,921 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:48:22,921 INFO L93 Difference]: Finished difference Result 524 states and 524 transitions. [2018-10-10 16:48:22,923 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-10-10 16:48:22,923 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 469 [2018-10-10 16:48:22,924 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:48:22,926 INFO L225 Difference]: With dead ends: 524 [2018-10-10 16:48:22,926 INFO L226 Difference]: Without dead ends: 524 [2018-10-10 16:48:22,927 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 320 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=353, Invalid=1999, Unknown=0, NotChecked=0, Total=2352 [2018-10-10 16:48:22,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 524 states. [2018-10-10 16:48:22,933 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 524 to 498. [2018-10-10 16:48:22,933 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 498 states. [2018-10-10 16:48:22,934 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 498 states to 498 states and 498 transitions. [2018-10-10 16:48:22,935 INFO L78 Accepts]: Start accepts. Automaton has 498 states and 498 transitions. Word has length 469 [2018-10-10 16:48:22,935 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:48:22,935 INFO L481 AbstractCegarLoop]: Abstraction has 498 states and 498 transitions. [2018-10-10 16:48:22,935 INFO L482 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-10-10 16:48:22,935 INFO L276 IsEmpty]: Start isEmpty. Operand 498 states and 498 transitions. [2018-10-10 16:48:22,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 498 [2018-10-10 16:48:22,938 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:48:22,939 INFO L375 BasicCegarLoop]: trace histogram [17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 16, 16, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:48:22,939 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:48:22,939 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:48:22,940 INFO L82 PathProgramCache]: Analyzing trace with hash -311426067, now seen corresponding path program 16 times [2018-10-10 16:48:22,940 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:48:22,984 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:48:24,242 WARN L178 SmtUtils]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-10-10 16:48:24,547 WARN L178 SmtUtils]: Spent 143.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-10-10 16:48:24,993 WARN L178 SmtUtils]: Spent 117.00 ms on a formula simplification that was a NOOP. DAG size: 17 [2018-10-10 16:48:26,503 INFO L134 CoverageAnalysis]: Checked inductivity of 3712 backedges. 0 proven. 3712 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:48:26,504 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:48:26,504 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28] total 28 [2018-10-10 16:48:26,504 INFO L460 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-10-10 16:48:26,504 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-10-10 16:48:26,505 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=658, Unknown=0, NotChecked=0, Total=756 [2018-10-10 16:48:26,505 INFO L87 Difference]: Start difference. First operand 498 states and 498 transitions. Second operand 28 states. [2018-10-10 16:48:28,753 WARN L178 SmtUtils]: Spent 149.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2018-10-10 16:48:31,187 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:48:31,187 INFO L93 Difference]: Finished difference Result 552 states and 552 transitions. [2018-10-10 16:48:31,187 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-10-10 16:48:31,188 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 497 [2018-10-10 16:48:31,188 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:48:31,190 INFO L225 Difference]: With dead ends: 552 [2018-10-10 16:48:31,190 INFO L226 Difference]: Without dead ends: 552 [2018-10-10 16:48:31,191 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 347 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=369, Invalid=2181, Unknown=0, NotChecked=0, Total=2550 [2018-10-10 16:48:31,192 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 552 states. [2018-10-10 16:48:31,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 552 to 526. [2018-10-10 16:48:31,197 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 526 states. [2018-10-10 16:48:31,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 526 states to 526 states and 526 transitions. [2018-10-10 16:48:31,198 INFO L78 Accepts]: Start accepts. Automaton has 526 states and 526 transitions. Word has length 497 [2018-10-10 16:48:31,198 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:48:31,199 INFO L481 AbstractCegarLoop]: Abstraction has 526 states and 526 transitions. [2018-10-10 16:48:31,199 INFO L482 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-10-10 16:48:31,199 INFO L276 IsEmpty]: Start isEmpty. Operand 526 states and 526 transitions. [2018-10-10 16:48:31,202 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 526 [2018-10-10 16:48:31,202 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:48:31,202 INFO L375 BasicCegarLoop]: trace histogram [18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 17, 17, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:48:31,203 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:48:31,203 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:48:31,203 INFO L82 PathProgramCache]: Analyzing trace with hash 1505281149, now seen corresponding path program 17 times [2018-10-10 16:48:31,204 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:48:31,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:48:33,732 INFO L134 CoverageAnalysis]: Checked inductivity of 4182 backedges. 0 proven. 4182 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:48:33,733 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:48:33,733 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-10 16:48:33,733 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-10 16:48:33,733 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-10 16:48:33,734 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=102, Invalid=710, Unknown=0, NotChecked=0, Total=812 [2018-10-10 16:48:33,734 INFO L87 Difference]: Start difference. First operand 526 states and 526 transitions. Second operand 29 states. [2018-10-10 16:48:38,263 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:48:38,264 INFO L93 Difference]: Finished difference Result 580 states and 580 transitions. [2018-10-10 16:48:38,264 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-10-10 16:48:38,264 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 525 [2018-10-10 16:48:38,265 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:48:38,267 INFO L225 Difference]: With dead ends: 580 [2018-10-10 16:48:38,267 INFO L226 Difference]: Without dead ends: 580 [2018-10-10 16:48:38,268 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 375 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=385, Invalid=2371, Unknown=0, NotChecked=0, Total=2756 [2018-10-10 16:48:38,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 580 states. [2018-10-10 16:48:38,273 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 580 to 554. [2018-10-10 16:48:38,274 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 554 states. [2018-10-10 16:48:38,275 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 554 states to 554 states and 554 transitions. [2018-10-10 16:48:38,275 INFO L78 Accepts]: Start accepts. Automaton has 554 states and 554 transitions. Word has length 525 [2018-10-10 16:48:38,276 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:48:38,276 INFO L481 AbstractCegarLoop]: Abstraction has 554 states and 554 transitions. [2018-10-10 16:48:38,276 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-10 16:48:38,276 INFO L276 IsEmpty]: Start isEmpty. Operand 554 states and 554 transitions. [2018-10-10 16:48:38,279 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 554 [2018-10-10 16:48:38,280 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:48:38,280 INFO L375 BasicCegarLoop]: trace histogram [19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:48:38,280 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:48:38,280 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:48:38,281 INFO L82 PathProgramCache]: Analyzing trace with hash 844238093, now seen corresponding path program 18 times [2018-10-10 16:48:38,281 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:48:38,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:48:39,113 WARN L178 SmtUtils]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-10-10 16:48:40,823 INFO L134 CoverageAnalysis]: Checked inductivity of 4680 backedges. 0 proven. 4680 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:48:40,823 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:48:40,824 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [30] total 30 [2018-10-10 16:48:40,824 INFO L460 AbstractCegarLoop]: Interpolant automaton has 30 states [2018-10-10 16:48:40,824 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2018-10-10 16:48:40,825 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=764, Unknown=0, NotChecked=0, Total=870 [2018-10-10 16:48:40,825 INFO L87 Difference]: Start difference. First operand 554 states and 554 transitions. Second operand 30 states. [2018-10-10 16:48:45,757 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:48:45,757 INFO L93 Difference]: Finished difference Result 608 states and 608 transitions. [2018-10-10 16:48:45,757 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-10 16:48:45,758 INFO L78 Accepts]: Start accepts. Automaton has 30 states. Word has length 553 [2018-10-10 16:48:45,758 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:48:45,763 INFO L225 Difference]: With dead ends: 608 [2018-10-10 16:48:45,764 INFO L226 Difference]: Without dead ends: 608 [2018-10-10 16:48:45,765 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 404 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=401, Invalid=2569, Unknown=0, NotChecked=0, Total=2970 [2018-10-10 16:48:45,766 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 608 states. [2018-10-10 16:48:45,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 608 to 582. [2018-10-10 16:48:45,772 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 582 states. [2018-10-10 16:48:45,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 582 states to 582 states and 582 transitions. [2018-10-10 16:48:45,773 INFO L78 Accepts]: Start accepts. Automaton has 582 states and 582 transitions. Word has length 553 [2018-10-10 16:48:45,773 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:48:45,774 INFO L481 AbstractCegarLoop]: Abstraction has 582 states and 582 transitions. [2018-10-10 16:48:45,774 INFO L482 AbstractCegarLoop]: Interpolant automaton has 30 states. [2018-10-10 16:48:45,774 INFO L276 IsEmpty]: Start isEmpty. Operand 582 states and 582 transitions. [2018-10-10 16:48:45,777 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 582 [2018-10-10 16:48:45,778 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:48:45,778 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, 19, 19, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:48:45,779 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:48:45,779 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:48:45,779 INFO L82 PathProgramCache]: Analyzing trace with hash 1352654237, now seen corresponding path program 19 times [2018-10-10 16:48:45,780 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:48:45,830 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:48:47,254 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-10-10 16:48:48,918 INFO L134 CoverageAnalysis]: Checked inductivity of 5206 backedges. 0 proven. 5206 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:48:48,918 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:48:48,918 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31] total 31 [2018-10-10 16:48:48,919 INFO L460 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-10-10 16:48:48,919 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-10-10 16:48:48,919 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=110, Invalid=820, Unknown=0, NotChecked=0, Total=930 [2018-10-10 16:48:48,920 INFO L87 Difference]: Start difference. First operand 582 states and 582 transitions. Second operand 31 states. [2018-10-10 16:48:54,188 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:48:54,188 INFO L93 Difference]: Finished difference Result 636 states and 636 transitions. [2018-10-10 16:48:54,188 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2018-10-10 16:48:54,189 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 581 [2018-10-10 16:48:54,189 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:48:54,191 INFO L225 Difference]: With dead ends: 636 [2018-10-10 16:48:54,191 INFO L226 Difference]: Without dead ends: 636 [2018-10-10 16:48:54,192 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 434 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=417, Invalid=2775, Unknown=0, NotChecked=0, Total=3192 [2018-10-10 16:48:54,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 636 states. [2018-10-10 16:48:54,198 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 636 to 610. [2018-10-10 16:48:54,198 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 610 states. [2018-10-10 16:48:54,199 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 610 states to 610 states and 610 transitions. [2018-10-10 16:48:54,200 INFO L78 Accepts]: Start accepts. Automaton has 610 states and 610 transitions. Word has length 581 [2018-10-10 16:48:54,200 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:48:54,200 INFO L481 AbstractCegarLoop]: Abstraction has 610 states and 610 transitions. [2018-10-10 16:48:54,200 INFO L482 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-10-10 16:48:54,201 INFO L276 IsEmpty]: Start isEmpty. Operand 610 states and 610 transitions. [2018-10-10 16:48:54,204 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 610 [2018-10-10 16:48:54,205 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:48:54,205 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:48:54,205 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:48:54,206 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:48:54,206 INFO L82 PathProgramCache]: Analyzing trace with hash 1342584365, now seen corresponding path program 20 times [2018-10-10 16:48:54,206 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:48:54,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:48:56,905 INFO L134 CoverageAnalysis]: Checked inductivity of 5760 backedges. 0 proven. 5760 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:48:56,906 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:48:56,906 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32] total 32 [2018-10-10 16:48:56,906 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-10-10 16:48:56,907 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-10-10 16:48:56,907 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=114, Invalid=878, Unknown=0, NotChecked=0, Total=992 [2018-10-10 16:48:56,908 INFO L87 Difference]: Start difference. First operand 610 states and 610 transitions. Second operand 32 states. [2018-10-10 16:49:02,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:49:02,743 INFO L93 Difference]: Finished difference Result 664 states and 664 transitions. [2018-10-10 16:49:02,743 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-10-10 16:49:02,743 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 609 [2018-10-10 16:49:02,744 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:49:02,746 INFO L225 Difference]: With dead ends: 664 [2018-10-10 16:49:02,746 INFO L226 Difference]: Without dead ends: 664 [2018-10-10 16:49:02,747 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 465 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=433, Invalid=2989, Unknown=0, NotChecked=0, Total=3422 [2018-10-10 16:49:02,747 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 664 states. [2018-10-10 16:49:02,753 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 664 to 638. [2018-10-10 16:49:02,753 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 638 states. [2018-10-10 16:49:02,755 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 638 states to 638 states and 638 transitions. [2018-10-10 16:49:02,755 INFO L78 Accepts]: Start accepts. Automaton has 638 states and 638 transitions. Word has length 609 [2018-10-10 16:49:02,755 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:49:02,756 INFO L481 AbstractCegarLoop]: Abstraction has 638 states and 638 transitions. [2018-10-10 16:49:02,756 INFO L482 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-10-10 16:49:02,756 INFO L276 IsEmpty]: Start isEmpty. Operand 638 states and 638 transitions. [2018-10-10 16:49:02,760 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 638 [2018-10-10 16:49:02,760 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:49:02,761 INFO L375 BasicCegarLoop]: trace histogram [22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 21, 21, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:49:02,761 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:49:02,761 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:49:02,761 INFO L82 PathProgramCache]: Analyzing trace with hash -1914104131, now seen corresponding path program 21 times [2018-10-10 16:49:02,762 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:49:02,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:49:05,757 INFO L134 CoverageAnalysis]: Checked inductivity of 6342 backedges. 0 proven. 6342 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:49:05,758 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:49:05,758 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-10 16:49:05,758 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-10 16:49:05,758 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-10 16:49:05,759 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=938, Unknown=0, NotChecked=0, Total=1056 [2018-10-10 16:49:05,759 INFO L87 Difference]: Start difference. First operand 638 states and 638 transitions. Second operand 33 states. [2018-10-10 16:49:12,323 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:49:12,323 INFO L93 Difference]: Finished difference Result 692 states and 692 transitions. [2018-10-10 16:49:12,325 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-10-10 16:49:12,325 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 637 [2018-10-10 16:49:12,326 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:49:12,328 INFO L225 Difference]: With dead ends: 692 [2018-10-10 16:49:12,328 INFO L226 Difference]: Without dead ends: 692 [2018-10-10 16:49:12,330 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 497 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=449, Invalid=3211, Unknown=0, NotChecked=0, Total=3660 [2018-10-10 16:49:12,330 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 692 states. [2018-10-10 16:49:12,335 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 692 to 666. [2018-10-10 16:49:12,336 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 666 states. [2018-10-10 16:49:12,337 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 666 states to 666 states and 666 transitions. [2018-10-10 16:49:12,337 INFO L78 Accepts]: Start accepts. Automaton has 666 states and 666 transitions. Word has length 637 [2018-10-10 16:49:12,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:49:12,338 INFO L481 AbstractCegarLoop]: Abstraction has 666 states and 666 transitions. [2018-10-10 16:49:12,338 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-10 16:49:12,338 INFO L276 IsEmpty]: Start isEmpty. Operand 666 states and 666 transitions. [2018-10-10 16:49:12,342 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 666 [2018-10-10 16:49:12,342 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:49:12,343 INFO L375 BasicCegarLoop]: trace histogram [23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:49:12,343 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:49:12,343 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:49:12,344 INFO L82 PathProgramCache]: Analyzing trace with hash 699170637, now seen corresponding path program 22 times [2018-10-10 16:49:12,344 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:49:12,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:49:15,252 INFO L134 CoverageAnalysis]: Checked inductivity of 6952 backedges. 0 proven. 6952 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:49:15,252 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:49:15,253 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [34] total 34 [2018-10-10 16:49:15,253 INFO L460 AbstractCegarLoop]: Interpolant automaton has 34 states [2018-10-10 16:49:15,254 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2018-10-10 16:49:15,254 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=1000, Unknown=0, NotChecked=0, Total=1122 [2018-10-10 16:49:15,254 INFO L87 Difference]: Start difference. First operand 666 states and 666 transitions. Second operand 34 states. [2018-10-10 16:49:21,949 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:49:21,949 INFO L93 Difference]: Finished difference Result 720 states and 720 transitions. [2018-10-10 16:49:21,950 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2018-10-10 16:49:21,950 INFO L78 Accepts]: Start accepts. Automaton has 34 states. Word has length 665 [2018-10-10 16:49:21,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:49:21,954 INFO L225 Difference]: With dead ends: 720 [2018-10-10 16:49:21,954 INFO L226 Difference]: Without dead ends: 720 [2018-10-10 16:49:21,955 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 530 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=465, Invalid=3441, Unknown=0, NotChecked=0, Total=3906 [2018-10-10 16:49:21,956 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 720 states. [2018-10-10 16:49:21,961 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 720 to 694. [2018-10-10 16:49:21,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 694 states. [2018-10-10 16:49:21,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 694 states to 694 states and 694 transitions. [2018-10-10 16:49:21,963 INFO L78 Accepts]: Start accepts. Automaton has 694 states and 694 transitions. Word has length 665 [2018-10-10 16:49:21,964 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:49:21,964 INFO L481 AbstractCegarLoop]: Abstraction has 694 states and 694 transitions. [2018-10-10 16:49:21,964 INFO L482 AbstractCegarLoop]: Interpolant automaton has 34 states. [2018-10-10 16:49:21,964 INFO L276 IsEmpty]: Start isEmpty. Operand 694 states and 694 transitions. [2018-10-10 16:49:21,969 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 694 [2018-10-10 16:49:21,969 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:49:21,969 INFO L375 BasicCegarLoop]: trace histogram [24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:49:21,970 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:49:21,970 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:49:21,970 INFO L82 PathProgramCache]: Analyzing trace with hash 78933981, now seen corresponding path program 23 times [2018-10-10 16:49:21,971 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:49:22,031 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:49:25,259 INFO L134 CoverageAnalysis]: Checked inductivity of 7590 backedges. 0 proven. 7590 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:49:25,259 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:49:25,259 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35] total 35 [2018-10-10 16:49:25,260 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-10-10 16:49:25,260 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-10-10 16:49:25,261 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=126, Invalid=1064, Unknown=0, NotChecked=0, Total=1190 [2018-10-10 16:49:25,261 INFO L87 Difference]: Start difference. First operand 694 states and 694 transitions. Second operand 35 states. [2018-10-10 16:49:32,802 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:49:32,802 INFO L93 Difference]: Finished difference Result 748 states and 748 transitions. [2018-10-10 16:49:32,802 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-10 16:49:32,803 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 693 [2018-10-10 16:49:32,803 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:49:32,805 INFO L225 Difference]: With dead ends: 748 [2018-10-10 16:49:32,805 INFO L226 Difference]: Without dead ends: 748 [2018-10-10 16:49:32,806 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 564 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=481, Invalid=3679, Unknown=0, NotChecked=0, Total=4160 [2018-10-10 16:49:32,807 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 748 states. [2018-10-10 16:49:32,812 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 748 to 722. [2018-10-10 16:49:32,812 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 722 states. [2018-10-10 16:49:32,813 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 722 states to 722 states and 722 transitions. [2018-10-10 16:49:32,813 INFO L78 Accepts]: Start accepts. Automaton has 722 states and 722 transitions. Word has length 693 [2018-10-10 16:49:32,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:49:32,814 INFO L481 AbstractCegarLoop]: Abstraction has 722 states and 722 transitions. [2018-10-10 16:49:32,814 INFO L482 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-10-10 16:49:32,814 INFO L276 IsEmpty]: Start isEmpty. Operand 722 states and 722 transitions. [2018-10-10 16:49:32,819 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 722 [2018-10-10 16:49:32,820 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:49:32,820 INFO L375 BasicCegarLoop]: trace histogram [25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 24, 24, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:49:32,820 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:49:32,821 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:49:32,821 INFO L82 PathProgramCache]: Analyzing trace with hash -1033574291, now seen corresponding path program 24 times [2018-10-10 16:49:32,822 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:49:32,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:49:34,139 WARN L178 SmtUtils]: Spent 119.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-10-10 16:49:34,416 WARN L178 SmtUtils]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-10-10 16:49:37,245 INFO L134 CoverageAnalysis]: Checked inductivity of 8256 backedges. 0 proven. 8256 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:49:37,245 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:49:37,245 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [36] total 36 [2018-10-10 16:49:37,246 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-10-10 16:49:37,246 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-10-10 16:49:37,246 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=130, Invalid=1130, Unknown=0, NotChecked=0, Total=1260 [2018-10-10 16:49:37,247 INFO L87 Difference]: Start difference. First operand 722 states and 722 transitions. Second operand 36 states. [2018-10-10 16:49:44,967 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:49:44,967 INFO L93 Difference]: Finished difference Result 776 states and 776 transitions. [2018-10-10 16:49:44,968 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-10-10 16:49:44,968 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 721 [2018-10-10 16:49:44,968 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:49:44,970 INFO L225 Difference]: With dead ends: 776 [2018-10-10 16:49:44,970 INFO L226 Difference]: Without dead ends: 776 [2018-10-10 16:49:44,971 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 599 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=497, Invalid=3925, Unknown=0, NotChecked=0, Total=4422 [2018-10-10 16:49:44,972 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 776 states. [2018-10-10 16:49:44,978 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 776 to 750. [2018-10-10 16:49:44,978 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 750 states. [2018-10-10 16:49:44,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 750 states to 750 states and 750 transitions. [2018-10-10 16:49:44,979 INFO L78 Accepts]: Start accepts. Automaton has 750 states and 750 transitions. Word has length 721 [2018-10-10 16:49:44,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:49:44,980 INFO L481 AbstractCegarLoop]: Abstraction has 750 states and 750 transitions. [2018-10-10 16:49:44,980 INFO L482 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-10-10 16:49:44,980 INFO L276 IsEmpty]: Start isEmpty. Operand 750 states and 750 transitions. [2018-10-10 16:49:44,986 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 750 [2018-10-10 16:49:44,986 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:49:44,986 INFO L375 BasicCegarLoop]: trace histogram [26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 25, 25, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:49:44,987 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:49:44,987 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:49:44,987 INFO L82 PathProgramCache]: Analyzing trace with hash -937301763, now seen corresponding path program 25 times [2018-10-10 16:49:44,988 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:49:45,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:49:49,018 INFO L134 CoverageAnalysis]: Checked inductivity of 8950 backedges. 0 proven. 8950 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:49:49,018 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:49:49,019 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-10 16:49:49,019 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-10 16:49:49,019 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-10 16:49:49,020 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=134, Invalid=1198, Unknown=0, NotChecked=0, Total=1332 [2018-10-10 16:49:49,020 INFO L87 Difference]: Start difference. First operand 750 states and 750 transitions. Second operand 37 states. [2018-10-10 16:49:57,455 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:49:57,455 INFO L93 Difference]: Finished difference Result 804 states and 804 transitions. [2018-10-10 16:49:57,455 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-10-10 16:49:57,455 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 749 [2018-10-10 16:49:57,456 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:49:57,458 INFO L225 Difference]: With dead ends: 804 [2018-10-10 16:49:57,458 INFO L226 Difference]: Without dead ends: 804 [2018-10-10 16:49:57,459 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 635 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=513, Invalid=4179, Unknown=0, NotChecked=0, Total=4692 [2018-10-10 16:49:57,459 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 804 states. [2018-10-10 16:49:57,464 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 804 to 778. [2018-10-10 16:49:57,464 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 778 states. [2018-10-10 16:49:57,465 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 778 states to 778 states and 778 transitions. [2018-10-10 16:49:57,466 INFO L78 Accepts]: Start accepts. Automaton has 778 states and 778 transitions. Word has length 749 [2018-10-10 16:49:57,466 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:49:57,466 INFO L481 AbstractCegarLoop]: Abstraction has 778 states and 778 transitions. [2018-10-10 16:49:57,466 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-10 16:49:57,467 INFO L276 IsEmpty]: Start isEmpty. Operand 778 states and 778 transitions. [2018-10-10 16:49:57,472 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 778 [2018-10-10 16:49:57,472 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:49:57,473 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, 26, 26, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:49:57,473 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:49:57,473 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:49:57,474 INFO L82 PathProgramCache]: Analyzing trace with hash 1028616589, now seen corresponding path program 26 times [2018-10-10 16:49:57,474 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:49:57,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:50:01,542 INFO L134 CoverageAnalysis]: Checked inductivity of 9672 backedges. 0 proven. 9672 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:50:01,543 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:50:01,543 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [38] total 38 [2018-10-10 16:50:01,544 INFO L460 AbstractCegarLoop]: Interpolant automaton has 38 states [2018-10-10 16:50:01,544 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 38 interpolants. [2018-10-10 16:50:01,544 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=138, Invalid=1268, Unknown=0, NotChecked=0, Total=1406 [2018-10-10 16:50:01,544 INFO L87 Difference]: Start difference. First operand 778 states and 778 transitions. Second operand 38 states. [2018-10-10 16:50:10,548 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:50:10,549 INFO L93 Difference]: Finished difference Result 832 states and 832 transitions. [2018-10-10 16:50:10,549 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2018-10-10 16:50:10,549 INFO L78 Accepts]: Start accepts. Automaton has 38 states. Word has length 777 [2018-10-10 16:50:10,550 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:50:10,552 INFO L225 Difference]: With dead ends: 832 [2018-10-10 16:50:10,553 INFO L226 Difference]: Without dead ends: 832 [2018-10-10 16:50:10,554 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 672 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=529, Invalid=4441, Unknown=0, NotChecked=0, Total=4970 [2018-10-10 16:50:10,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 832 states. [2018-10-10 16:50:10,559 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 832 to 806. [2018-10-10 16:50:10,559 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 806 states. [2018-10-10 16:50:10,561 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 806 states to 806 states and 806 transitions. [2018-10-10 16:50:10,561 INFO L78 Accepts]: Start accepts. Automaton has 806 states and 806 transitions. Word has length 777 [2018-10-10 16:50:10,561 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:50:10,562 INFO L481 AbstractCegarLoop]: Abstraction has 806 states and 806 transitions. [2018-10-10 16:50:10,562 INFO L482 AbstractCegarLoop]: Interpolant automaton has 38 states. [2018-10-10 16:50:10,562 INFO L276 IsEmpty]: Start isEmpty. Operand 806 states and 806 transitions. [2018-10-10 16:50:10,568 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 806 [2018-10-10 16:50:10,568 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:50:10,569 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:50:10,569 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:50:10,569 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:50:10,570 INFO L82 PathProgramCache]: Analyzing trace with hash 189891101, now seen corresponding path program 27 times [2018-10-10 16:50:10,570 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:50:10,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:50:14,512 INFO L134 CoverageAnalysis]: Checked inductivity of 10422 backedges. 0 proven. 10422 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:50:14,512 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:50:14,513 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39] total 39 [2018-10-10 16:50:14,513 INFO L460 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-10-10 16:50:14,514 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-10-10 16:50:14,514 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=142, Invalid=1340, Unknown=0, NotChecked=0, Total=1482 [2018-10-10 16:50:14,514 INFO L87 Difference]: Start difference. First operand 806 states and 806 transitions. Second operand 39 states. [2018-10-10 16:50:23,950 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:50:23,950 INFO L93 Difference]: Finished difference Result 860 states and 860 transitions. [2018-10-10 16:50:23,950 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-10-10 16:50:23,950 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 805 [2018-10-10 16:50:23,951 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:50:23,953 INFO L225 Difference]: With dead ends: 860 [2018-10-10 16:50:23,953 INFO L226 Difference]: Without dead ends: 860 [2018-10-10 16:50:23,954 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 710 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=545, Invalid=4711, Unknown=0, NotChecked=0, Total=5256 [2018-10-10 16:50:23,955 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 860 states. [2018-10-10 16:50:23,959 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 860 to 834. [2018-10-10 16:50:23,959 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 834 states. [2018-10-10 16:50:23,960 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 834 states to 834 states and 834 transitions. [2018-10-10 16:50:23,960 INFO L78 Accepts]: Start accepts. Automaton has 834 states and 834 transitions. Word has length 805 [2018-10-10 16:50:23,961 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:50:23,961 INFO L481 AbstractCegarLoop]: Abstraction has 834 states and 834 transitions. [2018-10-10 16:50:23,961 INFO L482 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-10-10 16:50:23,961 INFO L276 IsEmpty]: Start isEmpty. Operand 834 states and 834 transitions. [2018-10-10 16:50:23,967 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 834 [2018-10-10 16:50:23,967 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:50:23,967 INFO L375 BasicCegarLoop]: trace histogram [29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 28, 28, 28, 28, 28, 28, 28, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:50:23,968 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:50:23,968 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:50:23,968 INFO L82 PathProgramCache]: Analyzing trace with hash -578020691, now seen corresponding path program 28 times [2018-10-10 16:50:23,969 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:50:24,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:50:28,032 INFO L134 CoverageAnalysis]: Checked inductivity of 11200 backedges. 0 proven. 11200 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:50:28,033 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:50:28,033 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [40] total 40 [2018-10-10 16:50:28,033 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-10-10 16:50:28,034 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-10-10 16:50:28,034 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=146, Invalid=1414, Unknown=0, NotChecked=0, Total=1560 [2018-10-10 16:50:28,034 INFO L87 Difference]: Start difference. First operand 834 states and 834 transitions. Second operand 40 states. [2018-10-10 16:50:38,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:50:38,206 INFO L93 Difference]: Finished difference Result 888 states and 888 transitions. [2018-10-10 16:50:38,206 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 40 states. [2018-10-10 16:50:38,206 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 833 [2018-10-10 16:50:38,207 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:50:38,209 INFO L225 Difference]: With dead ends: 888 [2018-10-10 16:50:38,209 INFO L226 Difference]: Without dead ends: 888 [2018-10-10 16:50:38,210 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 749 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=561, Invalid=4989, Unknown=0, NotChecked=0, Total=5550 [2018-10-10 16:50:38,210 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 888 states. [2018-10-10 16:50:38,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 888 to 862. [2018-10-10 16:50:38,215 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 862 states. [2018-10-10 16:50:38,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 862 states to 862 states and 862 transitions. [2018-10-10 16:50:38,216 INFO L78 Accepts]: Start accepts. Automaton has 862 states and 862 transitions. Word has length 833 [2018-10-10 16:50:38,217 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:50:38,217 INFO L481 AbstractCegarLoop]: Abstraction has 862 states and 862 transitions. [2018-10-10 16:50:38,217 INFO L482 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-10-10 16:50:38,217 INFO L276 IsEmpty]: Start isEmpty. Operand 862 states and 862 transitions. [2018-10-10 16:50:38,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 862 [2018-10-10 16:50:38,224 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:50:38,224 INFO L375 BasicCegarLoop]: trace histogram [30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 29, 29, 29, 29, 29, 29, 29, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:50:38,225 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:50:38,225 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:50:38,225 INFO L82 PathProgramCache]: Analyzing trace with hash 560151357, now seen corresponding path program 29 times [2018-10-10 16:50:38,226 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:50:38,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:50:42,614 INFO L134 CoverageAnalysis]: Checked inductivity of 12006 backedges. 0 proven. 12006 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:50:42,615 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:50:42,615 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-10 16:50:42,616 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-10 16:50:42,616 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-10 16:50:42,616 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=1490, Unknown=0, NotChecked=0, Total=1640 [2018-10-10 16:50:42,616 INFO L87 Difference]: Start difference. First operand 862 states and 862 transitions. Second operand 41 states. [2018-10-10 16:50:53,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:50:53,179 INFO L93 Difference]: Finished difference Result 916 states and 916 transitions. [2018-10-10 16:50:53,179 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-10-10 16:50:53,179 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 861 [2018-10-10 16:50:53,180 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:50:53,183 INFO L225 Difference]: With dead ends: 916 [2018-10-10 16:50:53,183 INFO L226 Difference]: Without dead ends: 916 [2018-10-10 16:50:53,183 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 75 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 789 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=577, Invalid=5275, Unknown=0, NotChecked=0, Total=5852 [2018-10-10 16:50:53,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 916 states. [2018-10-10 16:50:53,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 916 to 890. [2018-10-10 16:50:53,189 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 890 states. [2018-10-10 16:50:53,190 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 890 states to 890 states and 890 transitions. [2018-10-10 16:50:53,190 INFO L78 Accepts]: Start accepts. Automaton has 890 states and 890 transitions. Word has length 861 [2018-10-10 16:50:53,190 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:50:53,190 INFO L481 AbstractCegarLoop]: Abstraction has 890 states and 890 transitions. [2018-10-10 16:50:53,190 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-10 16:50:53,190 INFO L276 IsEmpty]: Start isEmpty. Operand 890 states and 890 transitions. [2018-10-10 16:50:53,197 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 890 [2018-10-10 16:50:53,198 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:50:53,198 INFO L375 BasicCegarLoop]: trace histogram [31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 30, 30, 30, 30, 30, 30, 30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:50:53,198 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:50:53,199 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:50:53,199 INFO L82 PathProgramCache]: Analyzing trace with hash 104522701, now seen corresponding path program 30 times [2018-10-10 16:50:53,200 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:50:53,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:50:58,317 INFO L134 CoverageAnalysis]: Checked inductivity of 12840 backedges. 0 proven. 12840 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:50:58,318 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:50:58,318 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [42] total 42 [2018-10-10 16:50:58,319 INFO L460 AbstractCegarLoop]: Interpolant automaton has 42 states [2018-10-10 16:50:58,319 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2018-10-10 16:50:58,319 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=154, Invalid=1568, Unknown=0, NotChecked=0, Total=1722 [2018-10-10 16:50:58,319 INFO L87 Difference]: Start difference. First operand 890 states and 890 transitions. Second operand 42 states. [2018-10-10 16:51:09,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:51:09,908 INFO L93 Difference]: Finished difference Result 944 states and 944 transitions. [2018-10-10 16:51:09,908 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2018-10-10 16:51:09,908 INFO L78 Accepts]: Start accepts. Automaton has 42 states. Word has length 889 [2018-10-10 16:51:09,909 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:51:09,911 INFO L225 Difference]: With dead ends: 944 [2018-10-10 16:51:09,912 INFO L226 Difference]: Without dead ends: 944 [2018-10-10 16:51:09,912 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 830 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=593, Invalid=5569, Unknown=0, NotChecked=0, Total=6162 [2018-10-10 16:51:09,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 944 states. [2018-10-10 16:51:09,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 944 to 918. [2018-10-10 16:51:09,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 918 states. [2018-10-10 16:51:09,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 918 states to 918 states and 918 transitions. [2018-10-10 16:51:09,920 INFO L78 Accepts]: Start accepts. Automaton has 918 states and 918 transitions. Word has length 889 [2018-10-10 16:51:09,921 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:51:09,921 INFO L481 AbstractCegarLoop]: Abstraction has 918 states and 918 transitions. [2018-10-10 16:51:09,921 INFO L482 AbstractCegarLoop]: Interpolant automaton has 42 states. [2018-10-10 16:51:09,921 INFO L276 IsEmpty]: Start isEmpty. Operand 918 states and 918 transitions. [2018-10-10 16:51:09,927 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 918 [2018-10-10 16:51:09,927 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:51:09,928 INFO L375 BasicCegarLoop]: trace histogram [32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 31, 31, 31, 31, 31, 31, 31, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:51:09,928 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:51:09,928 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:51:09,928 INFO L82 PathProgramCache]: Analyzing trace with hash 2104955997, now seen corresponding path program 31 times [2018-10-10 16:51:09,930 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:51:10,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:51:14,695 INFO L134 CoverageAnalysis]: Checked inductivity of 13702 backedges. 0 proven. 13702 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:51:14,695 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:51:14,695 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43] total 43 [2018-10-10 16:51:14,696 INFO L460 AbstractCegarLoop]: Interpolant automaton has 43 states [2018-10-10 16:51:14,697 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2018-10-10 16:51:14,697 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=158, Invalid=1648, Unknown=0, NotChecked=0, Total=1806 [2018-10-10 16:51:14,697 INFO L87 Difference]: Start difference. First operand 918 states and 918 transitions. Second operand 43 states. [2018-10-10 16:51:26,682 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:51:26,682 INFO L93 Difference]: Finished difference Result 972 states and 972 transitions. [2018-10-10 16:51:26,683 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-10-10 16:51:26,683 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 917 [2018-10-10 16:51:26,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:51:26,687 INFO L225 Difference]: With dead ends: 972 [2018-10-10 16:51:26,687 INFO L226 Difference]: Without dead ends: 972 [2018-10-10 16:51:26,689 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 79 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 872 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=609, Invalid=5871, Unknown=0, NotChecked=0, Total=6480 [2018-10-10 16:51:26,689 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 972 states. [2018-10-10 16:51:26,696 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 972 to 946. [2018-10-10 16:51:26,696 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 946 states. [2018-10-10 16:51:26,698 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 946 states to 946 states and 946 transitions. [2018-10-10 16:51:26,698 INFO L78 Accepts]: Start accepts. Automaton has 946 states and 946 transitions. Word has length 917 [2018-10-10 16:51:26,698 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:51:26,699 INFO L481 AbstractCegarLoop]: Abstraction has 946 states and 946 transitions. [2018-10-10 16:51:26,699 INFO L482 AbstractCegarLoop]: Interpolant automaton has 43 states. [2018-10-10 16:51:26,699 INFO L276 IsEmpty]: Start isEmpty. Operand 946 states and 946 transitions. [2018-10-10 16:51:26,706 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 946 [2018-10-10 16:51:26,706 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:51:26,707 INFO L375 BasicCegarLoop]: trace histogram [33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 32, 32, 32, 32, 32, 32, 32, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:51:26,707 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:51:26,707 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:51:26,707 INFO L82 PathProgramCache]: Analyzing trace with hash 981191917, now seen corresponding path program 32 times [2018-10-10 16:51:26,708 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:51:26,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:51:31,697 INFO L134 CoverageAnalysis]: Checked inductivity of 14592 backedges. 0 proven. 14592 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:51:31,697 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:51:31,697 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [44] total 44 [2018-10-10 16:51:31,698 INFO L460 AbstractCegarLoop]: Interpolant automaton has 44 states [2018-10-10 16:51:31,699 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2018-10-10 16:51:31,699 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=162, Invalid=1730, Unknown=0, NotChecked=0, Total=1892 [2018-10-10 16:51:31,699 INFO L87 Difference]: Start difference. First operand 946 states and 946 transitions. Second operand 44 states. [2018-10-10 16:51:44,143 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:51:44,143 INFO L93 Difference]: Finished difference Result 1000 states and 1000 transitions. [2018-10-10 16:51:44,144 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-10-10 16:51:44,144 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 945 [2018-10-10 16:51:44,144 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:51:44,147 INFO L225 Difference]: With dead ends: 1000 [2018-10-10 16:51:44,147 INFO L226 Difference]: Without dead ends: 1000 [2018-10-10 16:51:44,148 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 915 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=625, Invalid=6181, Unknown=0, NotChecked=0, Total=6806 [2018-10-10 16:51:44,149 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1000 states. [2018-10-10 16:51:44,155 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1000 to 974. [2018-10-10 16:51:44,155 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 974 states. [2018-10-10 16:51:44,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 974 states to 974 states and 974 transitions. [2018-10-10 16:51:44,157 INFO L78 Accepts]: Start accepts. Automaton has 974 states and 974 transitions. Word has length 945 [2018-10-10 16:51:44,158 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:51:44,158 INFO L481 AbstractCegarLoop]: Abstraction has 974 states and 974 transitions. [2018-10-10 16:51:44,158 INFO L482 AbstractCegarLoop]: Interpolant automaton has 44 states. [2018-10-10 16:51:44,158 INFO L276 IsEmpty]: Start isEmpty. Operand 974 states and 974 transitions. [2018-10-10 16:51:44,165 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 974 [2018-10-10 16:51:44,165 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:51:44,166 INFO L375 BasicCegarLoop]: trace histogram [34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 33, 33, 33, 33, 33, 33, 33, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:51:44,166 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:51:44,166 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:51:44,166 INFO L82 PathProgramCache]: Analyzing trace with hash -1297281667, now seen corresponding path program 33 times [2018-10-10 16:51:44,167 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:51:44,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:51:49,387 INFO L134 CoverageAnalysis]: Checked inductivity of 15510 backedges. 0 proven. 15510 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:51:49,388 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:51:49,388 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-10 16:51:49,389 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-10 16:51:49,389 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-10 16:51:49,389 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=166, Invalid=1814, Unknown=0, NotChecked=0, Total=1980 [2018-10-10 16:51:49,389 INFO L87 Difference]: Start difference. First operand 974 states and 974 transitions. Second operand 45 states. [2018-10-10 16:52:03,053 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:52:03,053 INFO L93 Difference]: Finished difference Result 1028 states and 1028 transitions. [2018-10-10 16:52:03,053 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-10-10 16:52:03,054 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 973 [2018-10-10 16:52:03,054 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:52:03,057 INFO L225 Difference]: With dead ends: 1028 [2018-10-10 16:52:03,057 INFO L226 Difference]: Without dead ends: 1028 [2018-10-10 16:52:03,058 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 959 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=641, Invalid=6499, Unknown=0, NotChecked=0, Total=7140 [2018-10-10 16:52:03,058 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1028 states. [2018-10-10 16:52:03,063 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1028 to 1002. [2018-10-10 16:52:03,063 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1002 states. [2018-10-10 16:52:03,064 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1002 states to 1002 states and 1002 transitions. [2018-10-10 16:52:03,064 INFO L78 Accepts]: Start accepts. Automaton has 1002 states and 1002 transitions. Word has length 973 [2018-10-10 16:52:03,065 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:52:03,065 INFO L481 AbstractCegarLoop]: Abstraction has 1002 states and 1002 transitions. [2018-10-10 16:52:03,065 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-10 16:52:03,065 INFO L276 IsEmpty]: Start isEmpty. Operand 1002 states and 1002 transitions. [2018-10-10 16:52:03,071 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1002 [2018-10-10 16:52:03,071 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:52:03,072 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, 34, 34, 34, 34, 34, 34, 34, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:52:03,072 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:52:03,072 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:52:03,072 INFO L82 PathProgramCache]: Analyzing trace with hash 493803021, now seen corresponding path program 34 times [2018-10-10 16:52:03,073 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:52:03,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:52:08,513 INFO L134 CoverageAnalysis]: Checked inductivity of 16456 backedges. 0 proven. 16456 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:52:08,513 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:52:08,514 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [46] total 46 [2018-10-10 16:52:08,514 INFO L460 AbstractCegarLoop]: Interpolant automaton has 46 states [2018-10-10 16:52:08,514 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2018-10-10 16:52:08,515 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=170, Invalid=1900, Unknown=0, NotChecked=0, Total=2070 [2018-10-10 16:52:08,515 INFO L87 Difference]: Start difference. First operand 1002 states and 1002 transitions. Second operand 46 states. [2018-10-10 16:52:22,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:52:22,667 INFO L93 Difference]: Finished difference Result 1056 states and 1056 transitions. [2018-10-10 16:52:22,667 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2018-10-10 16:52:22,668 INFO L78 Accepts]: Start accepts. Automaton has 46 states. Word has length 1001 [2018-10-10 16:52:22,668 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:52:22,671 INFO L225 Difference]: With dead ends: 1056 [2018-10-10 16:52:22,672 INFO L226 Difference]: Without dead ends: 1056 [2018-10-10 16:52:22,672 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1004 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=657, Invalid=6825, Unknown=0, NotChecked=0, Total=7482 [2018-10-10 16:52:22,673 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1056 states. [2018-10-10 16:52:22,677 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1056 to 1030. [2018-10-10 16:52:22,678 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1030 states. [2018-10-10 16:52:22,679 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1030 states to 1030 states and 1030 transitions. [2018-10-10 16:52:22,679 INFO L78 Accepts]: Start accepts. Automaton has 1030 states and 1030 transitions. Word has length 1001 [2018-10-10 16:52:22,679 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:52:22,679 INFO L481 AbstractCegarLoop]: Abstraction has 1030 states and 1030 transitions. [2018-10-10 16:52:22,679 INFO L482 AbstractCegarLoop]: Interpolant automaton has 46 states. [2018-10-10 16:52:22,679 INFO L276 IsEmpty]: Start isEmpty. Operand 1030 states and 1030 transitions. [2018-10-10 16:52:22,685 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1030 [2018-10-10 16:52:22,685 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:52:22,685 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:52:22,686 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:52:22,686 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:52:22,686 INFO L82 PathProgramCache]: Analyzing trace with hash 1948591773, now seen corresponding path program 35 times [2018-10-10 16:52:22,686 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:52:22,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:52:28,548 INFO L134 CoverageAnalysis]: Checked inductivity of 17430 backedges. 0 proven. 17430 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:52:28,548 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:52:28,548 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [47] total 47 [2018-10-10 16:52:28,549 INFO L460 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-10-10 16:52:28,549 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-10-10 16:52:28,549 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=1988, Unknown=0, NotChecked=0, Total=2162 [2018-10-10 16:52:28,550 INFO L87 Difference]: Start difference. First operand 1030 states and 1030 transitions. Second operand 47 states. [2018-10-10 16:52:43,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:52:43,215 INFO L93 Difference]: Finished difference Result 1084 states and 1084 transitions. [2018-10-10 16:52:43,216 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-10-10 16:52:43,216 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 1029 [2018-10-10 16:52:43,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:52:43,219 INFO L225 Difference]: With dead ends: 1084 [2018-10-10 16:52:43,219 INFO L226 Difference]: Without dead ends: 1084 [2018-10-10 16:52:43,220 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 87 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1050 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=673, Invalid=7159, Unknown=0, NotChecked=0, Total=7832 [2018-10-10 16:52:43,221 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1084 states. [2018-10-10 16:52:43,227 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1084 to 1058. [2018-10-10 16:52:43,227 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1058 states. [2018-10-10 16:52:43,228 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1058 states to 1058 states and 1058 transitions. [2018-10-10 16:52:43,228 INFO L78 Accepts]: Start accepts. Automaton has 1058 states and 1058 transitions. Word has length 1029 [2018-10-10 16:52:43,229 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:52:43,229 INFO L481 AbstractCegarLoop]: Abstraction has 1058 states and 1058 transitions. [2018-10-10 16:52:43,229 INFO L482 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-10-10 16:52:43,229 INFO L276 IsEmpty]: Start isEmpty. Operand 1058 states and 1058 transitions. [2018-10-10 16:52:43,235 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1058 [2018-10-10 16:52:43,235 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:52:43,236 INFO L375 BasicCegarLoop]: trace histogram [37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 36, 36, 36, 36, 36, 36, 36, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:52:43,236 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:52:43,236 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:52:43,236 INFO L82 PathProgramCache]: Analyzing trace with hash 1916010285, now seen corresponding path program 36 times [2018-10-10 16:52:43,237 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:52:43,330 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:52:49,252 INFO L134 CoverageAnalysis]: Checked inductivity of 18432 backedges. 0 proven. 18432 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:52:49,252 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:52:49,253 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [48] total 48 [2018-10-10 16:52:49,253 INFO L460 AbstractCegarLoop]: Interpolant automaton has 48 states [2018-10-10 16:52:49,253 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2018-10-10 16:52:49,254 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=178, Invalid=2078, Unknown=0, NotChecked=0, Total=2256 [2018-10-10 16:52:49,254 INFO L87 Difference]: Start difference. First operand 1058 states and 1058 transitions. Second operand 48 states. [2018-10-10 16:53:05,056 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:53:05,057 INFO L93 Difference]: Finished difference Result 1112 states and 1112 transitions. [2018-10-10 16:53:05,057 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2018-10-10 16:53:05,057 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 1057 [2018-10-10 16:53:05,058 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:53:05,061 INFO L225 Difference]: With dead ends: 1112 [2018-10-10 16:53:05,061 INFO L226 Difference]: Without dead ends: 1112 [2018-10-10 16:53:05,062 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1097 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=689, Invalid=7501, Unknown=0, NotChecked=0, Total=8190 [2018-10-10 16:53:05,062 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1112 states. [2018-10-10 16:53:05,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1112 to 1086. [2018-10-10 16:53:05,068 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1086 states. [2018-10-10 16:53:05,069 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1086 states to 1086 states and 1086 transitions. [2018-10-10 16:53:05,069 INFO L78 Accepts]: Start accepts. Automaton has 1086 states and 1086 transitions. Word has length 1057 [2018-10-10 16:53:05,070 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:53:05,070 INFO L481 AbstractCegarLoop]: Abstraction has 1086 states and 1086 transitions. [2018-10-10 16:53:05,070 INFO L482 AbstractCegarLoop]: Interpolant automaton has 48 states. [2018-10-10 16:53:05,070 INFO L276 IsEmpty]: Start isEmpty. Operand 1086 states and 1086 transitions. [2018-10-10 16:53:05,077 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1086 [2018-10-10 16:53:05,078 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:53:05,078 INFO L375 BasicCegarLoop]: trace histogram [38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 37, 37, 37, 37, 37, 37, 37, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:53:05,078 INFO L424 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:53:05,079 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:53:05,079 INFO L82 PathProgramCache]: Analyzing trace with hash -1795203139, now seen corresponding path program 37 times [2018-10-10 16:53:05,079 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:53:05,175 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:53:11,431 INFO L134 CoverageAnalysis]: Checked inductivity of 19462 backedges. 0 proven. 19462 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:53:11,431 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:53:11,431 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-10 16:53:11,432 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-10 16:53:11,432 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-10 16:53:11,432 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=182, Invalid=2170, Unknown=0, NotChecked=0, Total=2352 [2018-10-10 16:53:11,433 INFO L87 Difference]: Start difference. First operand 1086 states and 1086 transitions. Second operand 49 states. [2018-10-10 16:53:27,676 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:53:27,677 INFO L93 Difference]: Finished difference Result 1140 states and 1140 transitions. [2018-10-10 16:53:27,677 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2018-10-10 16:53:27,677 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 1085 [2018-10-10 16:53:27,678 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:53:27,681 INFO L225 Difference]: With dead ends: 1140 [2018-10-10 16:53:27,681 INFO L226 Difference]: Without dead ends: 1140 [2018-10-10 16:53:27,682 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 91 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1145 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=705, Invalid=7851, Unknown=0, NotChecked=0, Total=8556 [2018-10-10 16:53:27,682 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1140 states. [2018-10-10 16:53:27,688 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1140 to 1114. [2018-10-10 16:53:27,688 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1114 states. [2018-10-10 16:53:27,690 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1114 states to 1114 states and 1114 transitions. [2018-10-10 16:53:27,690 INFO L78 Accepts]: Start accepts. Automaton has 1114 states and 1114 transitions. Word has length 1085 [2018-10-10 16:53:27,690 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:53:27,690 INFO L481 AbstractCegarLoop]: Abstraction has 1114 states and 1114 transitions. [2018-10-10 16:53:27,690 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-10 16:53:27,691 INFO L276 IsEmpty]: Start isEmpty. Operand 1114 states and 1114 transitions. [2018-10-10 16:53:27,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1114 [2018-10-10 16:53:27,698 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:53:27,699 INFO L375 BasicCegarLoop]: trace histogram [39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 38, 38, 38, 38, 38, 38, 38, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:53:27,699 INFO L424 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:53:27,699 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:53:27,699 INFO L82 PathProgramCache]: Analyzing trace with hash 468404301, now seen corresponding path program 38 times [2018-10-10 16:53:27,700 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:53:27,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:53:34,556 INFO L134 CoverageAnalysis]: Checked inductivity of 20520 backedges. 0 proven. 20520 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:53:34,556 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:53:34,556 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [50] total 50 [2018-10-10 16:53:34,557 INFO L460 AbstractCegarLoop]: Interpolant automaton has 50 states [2018-10-10 16:53:34,558 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2018-10-10 16:53:34,558 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=186, Invalid=2264, Unknown=0, NotChecked=0, Total=2450 [2018-10-10 16:53:34,558 INFO L87 Difference]: Start difference. First operand 1114 states and 1114 transitions. Second operand 50 states. [2018-10-10 16:53:52,763 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:53:52,764 INFO L93 Difference]: Finished difference Result 1168 states and 1168 transitions. [2018-10-10 16:53:52,764 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2018-10-10 16:53:52,764 INFO L78 Accepts]: Start accepts. Automaton has 50 states. Word has length 1113 [2018-10-10 16:53:52,765 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:53:52,768 INFO L225 Difference]: With dead ends: 1168 [2018-10-10 16:53:52,768 INFO L226 Difference]: Without dead ends: 1168 [2018-10-10 16:53:52,769 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1194 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=721, Invalid=8209, Unknown=0, NotChecked=0, Total=8930 [2018-10-10 16:53:52,770 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1168 states. [2018-10-10 16:53:52,776 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1168 to 1142. [2018-10-10 16:53:52,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1142 states. [2018-10-10 16:53:52,777 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1142 states to 1142 states and 1142 transitions. [2018-10-10 16:53:52,777 INFO L78 Accepts]: Start accepts. Automaton has 1142 states and 1142 transitions. Word has length 1113 [2018-10-10 16:53:52,778 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:53:52,778 INFO L481 AbstractCegarLoop]: Abstraction has 1142 states and 1142 transitions. [2018-10-10 16:53:52,778 INFO L482 AbstractCegarLoop]: Interpolant automaton has 50 states. [2018-10-10 16:53:52,778 INFO L276 IsEmpty]: Start isEmpty. Operand 1142 states and 1142 transitions. [2018-10-10 16:53:52,786 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1142 [2018-10-10 16:53:52,786 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:53:52,786 INFO L375 BasicCegarLoop]: trace histogram [40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 39, 39, 39, 39, 39, 39, 39, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:53:52,787 INFO L424 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:53:52,787 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:53:52,787 INFO L82 PathProgramCache]: Analyzing trace with hash 140228829, now seen corresponding path program 39 times [2018-10-10 16:53:52,788 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:53:52,905 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:53:59,919 INFO L134 CoverageAnalysis]: Checked inductivity of 21606 backedges. 0 proven. 21606 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:53:59,919 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:53:59,919 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [51] total 51 [2018-10-10 16:53:59,920 INFO L460 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-10-10 16:53:59,920 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-10-10 16:53:59,920 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=190, Invalid=2360, Unknown=0, NotChecked=0, Total=2550 [2018-10-10 16:53:59,921 INFO L87 Difference]: Start difference. First operand 1142 states and 1142 transitions. Second operand 51 states. [2018-10-10 16:54:18,561 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:54:18,561 INFO L93 Difference]: Finished difference Result 1196 states and 1196 transitions. [2018-10-10 16:54:18,562 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-10-10 16:54:18,562 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 1141 [2018-10-10 16:54:18,563 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:54:18,565 INFO L225 Difference]: With dead ends: 1196 [2018-10-10 16:54:18,566 INFO L226 Difference]: Without dead ends: 1196 [2018-10-10 16:54:18,566 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1244 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=737, Invalid=8575, Unknown=0, NotChecked=0, Total=9312 [2018-10-10 16:54:18,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1196 states. [2018-10-10 16:54:18,574 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1196 to 1170. [2018-10-10 16:54:18,574 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1170 states. [2018-10-10 16:54:18,575 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1170 states to 1170 states and 1170 transitions. [2018-10-10 16:54:18,575 INFO L78 Accepts]: Start accepts. Automaton has 1170 states and 1170 transitions. Word has length 1141 [2018-10-10 16:54:18,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:54:18,576 INFO L481 AbstractCegarLoop]: Abstraction has 1170 states and 1170 transitions. [2018-10-10 16:54:18,576 INFO L482 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-10-10 16:54:18,576 INFO L276 IsEmpty]: Start isEmpty. Operand 1170 states and 1170 transitions. [2018-10-10 16:54:18,585 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1170 [2018-10-10 16:54:18,585 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:54:18,585 INFO L375 BasicCegarLoop]: trace histogram [41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 40, 40, 40, 40, 40, 40, 40, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:54:18,586 INFO L424 AbstractCegarLoop]: === Iteration 41 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:54:18,586 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:54:18,586 INFO L82 PathProgramCache]: Analyzing trace with hash 498381165, now seen corresponding path program 40 times [2018-10-10 16:54:18,587 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:54:18,726 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:54:25,945 INFO L134 CoverageAnalysis]: Checked inductivity of 22720 backedges. 0 proven. 22720 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:54:25,946 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:54:25,946 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [52] total 52 [2018-10-10 16:54:25,947 INFO L460 AbstractCegarLoop]: Interpolant automaton has 52 states [2018-10-10 16:54:25,947 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2018-10-10 16:54:25,947 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=194, Invalid=2458, Unknown=0, NotChecked=0, Total=2652 [2018-10-10 16:54:25,947 INFO L87 Difference]: Start difference. First operand 1170 states and 1170 transitions. Second operand 52 states. [2018-10-10 16:54:33,305 WARN L178 SmtUtils]: Spent 203.00 ms on a formula simplification that was a NOOP. DAG size: 26 [2018-10-10 16:54:45,909 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:54:45,909 INFO L93 Difference]: Finished difference Result 1224 states and 1224 transitions. [2018-10-10 16:54:45,909 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-10-10 16:54:45,910 INFO L78 Accepts]: Start accepts. Automaton has 52 states. Word has length 1169 [2018-10-10 16:54:45,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:54:45,913 INFO L225 Difference]: With dead ends: 1224 [2018-10-10 16:54:45,913 INFO L226 Difference]: Without dead ends: 1224 [2018-10-10 16:54:45,914 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 97 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1295 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=753, Invalid=8949, Unknown=0, NotChecked=0, Total=9702 [2018-10-10 16:54:45,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1224 states. [2018-10-10 16:54:45,921 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1224 to 1198. [2018-10-10 16:54:45,921 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1198 states. [2018-10-10 16:54:45,922 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1198 states to 1198 states and 1198 transitions. [2018-10-10 16:54:45,922 INFO L78 Accepts]: Start accepts. Automaton has 1198 states and 1198 transitions. Word has length 1169 [2018-10-10 16:54:45,923 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:54:45,923 INFO L481 AbstractCegarLoop]: Abstraction has 1198 states and 1198 transitions. [2018-10-10 16:54:45,923 INFO L482 AbstractCegarLoop]: Interpolant automaton has 52 states. [2018-10-10 16:54:45,923 INFO L276 IsEmpty]: Start isEmpty. Operand 1198 states and 1198 transitions. [2018-10-10 16:54:45,932 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1198 [2018-10-10 16:54:45,932 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:54:45,933 INFO L375 BasicCegarLoop]: trace histogram [42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 41, 41, 41, 41, 41, 41, 41, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:54:45,933 INFO L424 AbstractCegarLoop]: === Iteration 42 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:54:45,933 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:54:45,933 INFO L82 PathProgramCache]: Analyzing trace with hash -514182659, now seen corresponding path program 41 times [2018-10-10 16:54:45,934 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:54:46,058 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:54:53,570 INFO L134 CoverageAnalysis]: Checked inductivity of 23862 backedges. 0 proven. 23862 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:54:53,570 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:54:53,570 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-10 16:54:53,571 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-10 16:54:53,571 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-10 16:54:53,571 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=198, Invalid=2558, Unknown=0, NotChecked=0, Total=2756 [2018-10-10 16:54:53,571 INFO L87 Difference]: Start difference. First operand 1198 states and 1198 transitions. Second operand 53 states. [2018-10-10 16:55:13,884 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:55:13,884 INFO L93 Difference]: Finished difference Result 1252 states and 1252 transitions. [2018-10-10 16:55:13,884 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-10 16:55:13,884 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 1197 [2018-10-10 16:55:13,885 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:55:13,888 INFO L225 Difference]: With dead ends: 1252 [2018-10-10 16:55:13,889 INFO L226 Difference]: Without dead ends: 1252 [2018-10-10 16:55:13,889 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 99 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1347 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=769, Invalid=9331, Unknown=0, NotChecked=0, Total=10100 [2018-10-10 16:55:13,890 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1252 states. [2018-10-10 16:55:13,896 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1252 to 1226. [2018-10-10 16:55:13,896 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1226 states. [2018-10-10 16:55:13,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1226 states to 1226 states and 1226 transitions. [2018-10-10 16:55:13,898 INFO L78 Accepts]: Start accepts. Automaton has 1226 states and 1226 transitions. Word has length 1197 [2018-10-10 16:55:13,898 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:55:13,898 INFO L481 AbstractCegarLoop]: Abstraction has 1226 states and 1226 transitions. [2018-10-10 16:55:13,899 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-10 16:55:13,899 INFO L276 IsEmpty]: Start isEmpty. Operand 1226 states and 1226 transitions. [2018-10-10 16:55:13,908 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1226 [2018-10-10 16:55:13,908 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:55:13,909 INFO L375 BasicCegarLoop]: trace histogram [43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 42, 42, 42, 42, 42, 42, 42, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:55:13,909 INFO L424 AbstractCegarLoop]: === Iteration 43 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:55:13,909 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:55:13,909 INFO L82 PathProgramCache]: Analyzing trace with hash -1699726707, now seen corresponding path program 42 times [2018-10-10 16:55:13,910 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:55:14,053 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:55:21,985 INFO L134 CoverageAnalysis]: Checked inductivity of 25032 backedges. 0 proven. 25032 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:55:21,986 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:55:21,986 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [54] total 54 [2018-10-10 16:55:21,987 INFO L460 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-10-10 16:55:21,988 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-10-10 16:55:21,988 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=202, Invalid=2660, Unknown=0, NotChecked=0, Total=2862 [2018-10-10 16:55:21,988 INFO L87 Difference]: Start difference. First operand 1226 states and 1226 transitions. Second operand 54 states. [2018-10-10 16:55:43,243 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 16:55:43,244 INFO L93 Difference]: Finished difference Result 1280 states and 1280 transitions. [2018-10-10 16:55:43,244 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-10-10 16:55:43,244 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 1225 [2018-10-10 16:55:43,245 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 16:55:43,248 INFO L225 Difference]: With dead ends: 1280 [2018-10-10 16:55:43,248 INFO L226 Difference]: Without dead ends: 1280 [2018-10-10 16:55:43,249 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1400 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=785, Invalid=9721, Unknown=0, NotChecked=0, Total=10506 [2018-10-10 16:55:43,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1280 states. [2018-10-10 16:55:43,256 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1280 to 1254. [2018-10-10 16:55:43,256 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1254 states. [2018-10-10 16:55:43,258 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1254 states to 1254 states and 1254 transitions. [2018-10-10 16:55:43,258 INFO L78 Accepts]: Start accepts. Automaton has 1254 states and 1254 transitions. Word has length 1225 [2018-10-10 16:55:43,258 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 16:55:43,258 INFO L481 AbstractCegarLoop]: Abstraction has 1254 states and 1254 transitions. [2018-10-10 16:55:43,258 INFO L482 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-10-10 16:55:43,259 INFO L276 IsEmpty]: Start isEmpty. Operand 1254 states and 1254 transitions. [2018-10-10 16:55:43,268 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1254 [2018-10-10 16:55:43,268 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 16:55:43,269 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, 43, 43, 43, 43, 43, 43, 43, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 16:55:43,269 INFO L424 AbstractCegarLoop]: === Iteration 44 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 16:55:43,269 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 16:55:43,269 INFO L82 PathProgramCache]: Analyzing trace with hash 1394264861, now seen corresponding path program 43 times [2018-10-10 16:55:43,270 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 16:55:43,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 16:55:51,725 INFO L134 CoverageAnalysis]: Checked inductivity of 26230 backedges. 0 proven. 26230 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 16:55:51,725 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 16:55:51,725 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55] total 55 [2018-10-10 16:55:51,726 INFO L460 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-10-10 16:55:51,726 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-10-10 16:55:51,727 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=206, Invalid=2764, Unknown=0, NotChecked=0, Total=2970 [2018-10-10 16:55:51,727 INFO L87 Difference]: Start difference. First operand 1254 states and 1254 transitions. Second operand 55 states.