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/AutomizerBpl.xml -s ../../../trunk/examples/settings/heapseparator/heapsep-2018-09-18.epf -i ../../../trunk/examples/programs/20181010-MemSafetyPathprograms/count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-b8f97f7-m [2018-10-10 15:29:03,268 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-10 15:29:03,270 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-10 15:29:03,286 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-10 15:29:03,286 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-10 15:29:03,287 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-10 15:29:03,288 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-10 15:29:03,290 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-10 15:29:03,292 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-10 15:29:03,293 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-10 15:29:03,294 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-10 15:29:03,294 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-10 15:29:03,295 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-10 15:29:03,296 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-10 15:29:03,297 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-10 15:29:03,298 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-10 15:29:03,299 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-10 15:29:03,302 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-10 15:29:03,307 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-10 15:29:03,311 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-10 15:29:03,313 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-10 15:29:03,314 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-10 15:29:03,318 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-10 15:29:03,319 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-10 15:29:03,319 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-10 15:29:03,323 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-10 15:29:03,324 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-10 15:29:03,328 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-10 15:29:03,329 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-10 15:29:03,330 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-10 15:29:03,331 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-10 15:29:03,332 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-10 15:29:03,332 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-10 15:29:03,333 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-10 15:29:03,334 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-10 15:29:03,337 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-10 15:29:03,338 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 15:29:03,356 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-10 15:29:03,356 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-10 15:29:03,357 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-10 15:29:03,357 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-10 15:29:03,361 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-10 15:29:03,361 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-10 15:29:03,362 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-10 15:29:03,362 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-10 15:29:03,363 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-10 15:29:03,363 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-10 15:29:03,363 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-10 15:29:03,363 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-10 15:29:03,363 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-10 15:29:03,364 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-10 15:29:03,364 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-10 15:29:03,432 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-10 15:29:03,449 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-10 15:29:03,453 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-10 15:29:03,454 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-10 15:29:03,455 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-10 15:29:03,455 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl [2018-10-10 15:29:03,456 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl' [2018-10-10 15:29:03,519 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-10 15:29:03,521 INFO L131 ToolchainWalker]: Walking toolchain with 3 elements. [2018-10-10 15:29:03,522 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-10 15:29:03,522 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-10 15:29:03,522 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-10 15:29:03,550 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 03:29:03" (1/1) ... [2018-10-10 15:29:03,552 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 03:29:03" (1/1) ... [2018-10-10 15:29:03,570 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 03:29:03" (1/1) ... [2018-10-10 15:29:03,571 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 03:29:03" (1/1) ... [2018-10-10 15:29:03,578 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 03:29:03" (1/1) ... [2018-10-10 15:29:03,583 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 03:29:03" (1/1) ... [2018-10-10 15:29:03,584 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 03:29:03" (1/1) ... [2018-10-10 15:29:03,592 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-10 15:29:03,593 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-10 15:29:03,593 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-10 15:29:03,594 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-10 15:29:03,595 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 03:29:03" (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 15:29:03,672 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2018-10-10 15:29:03,673 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-10 15:29:03,673 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-10 15:29:04,200 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-10 15:29:04,201 INFO L202 PluginConnector]: Adding new model count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 03:29:04 BoogieIcfgContainer [2018-10-10 15:29:04,201 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-10 15:29:04,202 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-10 15:29:04,202 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-10 15:29:04,205 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-10 15:29:04,206 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.10 03:29:03" (1/2) ... [2018-10-10 15:29:04,207 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@ea078f7 and model type count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.10 03:29:04, skipping insertion in model container [2018-10-10 15:29:04,207 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.10 03:29:04" (2/2) ... [2018-10-10 15:29:04,209 INFO L112 eAbstractionObserver]: Analyzing ICFG count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl [2018-10-10 15:29:04,219 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-10 15:29:04,227 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-10 15:29:04,244 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-10 15:29:04,270 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-10 15:29:04,271 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-10 15:29:04,271 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-10 15:29:04,271 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-10 15:29:04,271 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-10 15:29:04,271 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-10 15:29:04,271 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-10 15:29:04,272 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-10 15:29:04,272 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-10 15:29:04,287 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states. [2018-10-10 15:29:04,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-10-10 15:29:04,296 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:04,297 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:04,298 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:04,303 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:04,303 INFO L82 PathProgramCache]: Analyzing trace with hash 1633044116, now seen corresponding path program 1 times [2018-10-10 15:29:04,352 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:04,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:04,513 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 15:29:04,516 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-10 15:29:04,516 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-10 15:29:04,523 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-10 15:29:04,538 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-10 15:29:04,538 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-10 15:29:04,540 INFO L87 Difference]: Start difference. First operand 60 states. Second operand 4 states. [2018-10-10 15:29:04,676 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:04,677 INFO L93 Difference]: Finished difference Result 73 states and 74 transitions. [2018-10-10 15:29:04,677 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-10 15:29:04,678 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 32 [2018-10-10 15:29:04,679 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:04,690 INFO L225 Difference]: With dead ends: 73 [2018-10-10 15:29:04,690 INFO L226 Difference]: Without dead ends: 73 [2018-10-10 15:29:04,692 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-10 15:29:04,711 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2018-10-10 15:29:04,730 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 59. [2018-10-10 15:29:04,731 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2018-10-10 15:29:04,733 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 60 transitions. [2018-10-10 15:29:04,735 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 60 transitions. Word has length 32 [2018-10-10 15:29:04,735 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:04,735 INFO L481 AbstractCegarLoop]: Abstraction has 59 states and 60 transitions. [2018-10-10 15:29:04,735 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-10 15:29:04,736 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 60 transitions. [2018-10-10 15:29:04,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2018-10-10 15:29:04,737 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:04,738 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:04,738 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:04,738 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:04,739 INFO L82 PathProgramCache]: Analyzing trace with hash -60124276, now seen corresponding path program 1 times [2018-10-10 15:29:04,740 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:04,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:05,285 WARN L178 SmtUtils]: Spent 168.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 16 [2018-10-10 15:29:05,647 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:05,648 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:05,648 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-10-10 15:29:05,650 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-10 15:29:05,650 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-10 15:29:05,651 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2018-10-10 15:29:05,651 INFO L87 Difference]: Start difference. First operand 59 states and 60 transitions. Second operand 12 states. [2018-10-10 15:29:06,295 WARN L178 SmtUtils]: Spent 311.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 24 [2018-10-10 15:29:06,792 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:06,792 INFO L93 Difference]: Finished difference Result 121 states and 123 transitions. [2018-10-10 15:29:06,793 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-10 15:29:06,793 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 48 [2018-10-10 15:29:06,794 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:06,797 INFO L225 Difference]: With dead ends: 121 [2018-10-10 15:29:06,797 INFO L226 Difference]: Without dead ends: 121 [2018-10-10 15:29:06,799 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2018-10-10 15:29:06,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2018-10-10 15:29:06,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 80. [2018-10-10 15:29:06,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-10-10 15:29:06,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 82 transitions. [2018-10-10 15:29:06,810 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 82 transitions. Word has length 48 [2018-10-10 15:29:06,810 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:06,811 INFO L481 AbstractCegarLoop]: Abstraction has 80 states and 82 transitions. [2018-10-10 15:29:06,811 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-10 15:29:06,811 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 82 transitions. [2018-10-10 15:29:06,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-10-10 15:29:06,813 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:06,813 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:06,814 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:06,814 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:06,814 INFO L82 PathProgramCache]: Analyzing trace with hash -2063516096, now seen corresponding path program 1 times [2018-10-10 15:29:06,815 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:06,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:06,989 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:06,989 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:06,990 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-10 15:29:06,990 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-10 15:29:06,990 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-10 15:29:06,991 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-10-10 15:29:06,991 INFO L87 Difference]: Start difference. First operand 80 states and 82 transitions. Second operand 9 states. [2018-10-10 15:29:07,604 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:07,604 INFO L93 Difference]: Finished difference Result 105 states and 106 transitions. [2018-10-10 15:29:07,605 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-10 15:29:07,605 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 62 [2018-10-10 15:29:07,606 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:07,607 INFO L225 Difference]: With dead ends: 105 [2018-10-10 15:29:07,607 INFO L226 Difference]: Without dead ends: 89 [2018-10-10 15:29:07,608 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2018-10-10 15:29:07,608 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-10-10 15:29:07,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 75. [2018-10-10 15:29:07,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-10-10 15:29:07,616 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 76 transitions. [2018-10-10 15:29:07,616 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 76 transitions. Word has length 62 [2018-10-10 15:29:07,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:07,617 INFO L481 AbstractCegarLoop]: Abstraction has 75 states and 76 transitions. [2018-10-10 15:29:07,617 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-10 15:29:07,617 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 76 transitions. [2018-10-10 15:29:07,619 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-10-10 15:29:07,619 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:07,619 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:07,619 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:07,620 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:07,620 INFO L82 PathProgramCache]: Analyzing trace with hash -2114588540, now seen corresponding path program 2 times [2018-10-10 15:29:07,621 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:07,644 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:07,995 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-10-10 15:29:07,996 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:07,996 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-10 15:29:07,997 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-10 15:29:07,997 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-10 15:29:07,997 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-10-10 15:29:07,998 INFO L87 Difference]: Start difference. First operand 75 states and 76 transitions. Second operand 9 states. [2018-10-10 15:29:08,216 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:08,216 INFO L93 Difference]: Finished difference Result 88 states and 89 transitions. [2018-10-10 15:29:08,216 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-10 15:29:08,216 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 64 [2018-10-10 15:29:08,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:08,218 INFO L225 Difference]: With dead ends: 88 [2018-10-10 15:29:08,218 INFO L226 Difference]: Without dead ends: 88 [2018-10-10 15:29:08,219 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2018-10-10 15:29:08,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2018-10-10 15:29:08,225 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 79. [2018-10-10 15:29:08,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-10-10 15:29:08,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 80 transitions. [2018-10-10 15:29:08,227 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 80 transitions. Word has length 64 [2018-10-10 15:29:08,227 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:08,227 INFO L481 AbstractCegarLoop]: Abstraction has 79 states and 80 transitions. [2018-10-10 15:29:08,227 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-10 15:29:08,228 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 80 transitions. [2018-10-10 15:29:08,230 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2018-10-10 15:29:08,230 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:08,230 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:08,231 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:08,231 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:08,231 INFO L82 PathProgramCache]: Analyzing trace with hash -502625992, now seen corresponding path program 2 times [2018-10-10 15:29:08,232 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:08,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:08,544 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:08,544 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:08,545 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-10 15:29:08,545 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-10 15:29:08,545 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-10 15:29:08,546 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-10-10 15:29:08,546 INFO L87 Difference]: Start difference. First operand 79 states and 80 transitions. Second operand 13 states. [2018-10-10 15:29:09,762 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:09,763 INFO L93 Difference]: Finished difference Result 174 states and 176 transitions. [2018-10-10 15:29:09,763 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-10 15:29:09,764 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 78 [2018-10-10 15:29:09,764 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:09,767 INFO L225 Difference]: With dead ends: 174 [2018-10-10 15:29:09,767 INFO L226 Difference]: Without dead ends: 174 [2018-10-10 15:29:09,768 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 184 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=135, Invalid=735, Unknown=0, NotChecked=0, Total=870 [2018-10-10 15:29:09,769 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-10-10 15:29:09,776 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 93. [2018-10-10 15:29:09,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-10-10 15:29:09,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 94 transitions. [2018-10-10 15:29:09,784 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 94 transitions. Word has length 78 [2018-10-10 15:29:09,784 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:09,784 INFO L481 AbstractCegarLoop]: Abstraction has 93 states and 94 transitions. [2018-10-10 15:29:09,785 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-10 15:29:09,785 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 94 transitions. [2018-10-10 15:29:09,789 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2018-10-10 15:29:09,789 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:09,790 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:09,790 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:09,790 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:09,790 INFO L82 PathProgramCache]: Analyzing trace with hash 75224812, now seen corresponding path program 3 times [2018-10-10 15:29:09,791 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:09,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:09,961 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:09,961 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:09,962 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-10 15:29:09,962 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-10 15:29:09,962 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-10 15:29:09,963 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-10-10 15:29:09,963 INFO L87 Difference]: Start difference. First operand 93 states and 94 transitions. Second operand 13 states. [2018-10-10 15:29:10,427 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:10,428 INFO L93 Difference]: Finished difference Result 153 states and 154 transitions. [2018-10-10 15:29:10,429 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-10 15:29:10,430 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 92 [2018-10-10 15:29:10,430 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:10,431 INFO L225 Difference]: With dead ends: 153 [2018-10-10 15:29:10,431 INFO L226 Difference]: Without dead ends: 123 [2018-10-10 15:29:10,432 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=117, Invalid=483, Unknown=0, NotChecked=0, Total=600 [2018-10-10 15:29:10,432 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2018-10-10 15:29:10,438 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 109. [2018-10-10 15:29:10,439 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-10-10 15:29:10,440 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 110 transitions. [2018-10-10 15:29:10,440 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 110 transitions. Word has length 92 [2018-10-10 15:29:10,441 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:10,441 INFO L481 AbstractCegarLoop]: Abstraction has 109 states and 110 transitions. [2018-10-10 15:29:10,441 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-10 15:29:10,441 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 110 transitions. [2018-10-10 15:29:10,443 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2018-10-10 15:29:10,443 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:10,443 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:10,444 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:10,444 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:10,444 INFO L82 PathProgramCache]: Analyzing trace with hash 925474788, now seen corresponding path program 4 times [2018-10-10 15:29:10,445 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:10,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:10,903 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 0 proven. 73 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:10,903 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:10,903 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-10 15:29:10,904 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-10 15:29:10,904 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-10 15:29:10,904 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=238, Unknown=0, NotChecked=0, Total=272 [2018-10-10 15:29:10,905 INFO L87 Difference]: Start difference. First operand 109 states and 110 transitions. Second operand 17 states. [2018-10-10 15:29:12,550 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:12,550 INFO L93 Difference]: Finished difference Result 143 states and 144 transitions. [2018-10-10 15:29:12,550 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-10 15:29:12,551 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 108 [2018-10-10 15:29:12,551 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:12,552 INFO L225 Difference]: With dead ends: 143 [2018-10-10 15:29:12,552 INFO L226 Difference]: Without dead ends: 143 [2018-10-10 15:29:12,554 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=185, Invalid=1075, Unknown=0, NotChecked=0, Total=1260 [2018-10-10 15:29:12,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2018-10-10 15:29:12,560 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 123. [2018-10-10 15:29:12,560 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 123 states. [2018-10-10 15:29:12,562 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 124 transitions. [2018-10-10 15:29:12,562 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 124 transitions. Word has length 108 [2018-10-10 15:29:12,562 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:12,562 INFO L481 AbstractCegarLoop]: Abstraction has 123 states and 124 transitions. [2018-10-10 15:29:12,562 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-10 15:29:12,563 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 124 transitions. [2018-10-10 15:29:12,564 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2018-10-10 15:29:12,564 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:12,565 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:12,565 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:12,565 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:12,565 INFO L82 PathProgramCache]: Analyzing trace with hash -1310207848, now seen corresponding path program 5 times [2018-10-10 15:29:12,566 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:12,582 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:12,853 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 27 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:12,853 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:12,853 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-10 15:29:12,854 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-10 15:29:12,854 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-10 15:29:12,854 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2018-10-10 15:29:12,855 INFO L87 Difference]: Start difference. First operand 123 states and 124 transitions. Second operand 17 states. [2018-10-10 15:29:13,301 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:13,301 INFO L93 Difference]: Finished difference Result 197 states and 198 transitions. [2018-10-10 15:29:13,301 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-10 15:29:13,302 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 122 [2018-10-10 15:29:13,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:13,303 INFO L225 Difference]: With dead ends: 197 [2018-10-10 15:29:13,304 INFO L226 Difference]: Without dead ends: 153 [2018-10-10 15:29:13,305 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 216 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=198, Invalid=924, Unknown=0, NotChecked=0, Total=1122 [2018-10-10 15:29:13,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2018-10-10 15:29:13,310 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 139. [2018-10-10 15:29:13,311 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 139 states. [2018-10-10 15:29:13,312 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 140 transitions. [2018-10-10 15:29:13,312 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 140 transitions. Word has length 122 [2018-10-10 15:29:13,313 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:13,313 INFO L481 AbstractCegarLoop]: Abstraction has 139 states and 140 transitions. [2018-10-10 15:29:13,313 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-10 15:29:13,313 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 140 transitions. [2018-10-10 15:29:13,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2018-10-10 15:29:13,315 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:13,315 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:13,315 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:13,315 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:13,316 INFO L82 PathProgramCache]: Analyzing trace with hash -708208752, now seen corresponding path program 6 times [2018-10-10 15:29:13,316 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:13,331 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:13,837 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 14 proven. 140 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:13,837 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:13,837 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-10 15:29:13,838 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-10 15:29:13,838 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-10 15:29:13,838 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=375, Unknown=0, NotChecked=0, Total=420 [2018-10-10 15:29:13,838 INFO L87 Difference]: Start difference. First operand 139 states and 140 transitions. Second operand 21 states. [2018-10-10 15:29:15,600 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:15,600 INFO L93 Difference]: Finished difference Result 173 states and 174 transitions. [2018-10-10 15:29:15,601 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-10 15:29:15,601 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 138 [2018-10-10 15:29:15,601 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:15,603 INFO L225 Difference]: With dead ends: 173 [2018-10-10 15:29:15,603 INFO L226 Difference]: Without dead ends: 173 [2018-10-10 15:29:15,605 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 330 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=259, Invalid=1721, Unknown=0, NotChecked=0, Total=1980 [2018-10-10 15:29:15,605 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2018-10-10 15:29:15,611 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 153. [2018-10-10 15:29:15,611 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 153 states. [2018-10-10 15:29:15,612 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 154 transitions. [2018-10-10 15:29:15,613 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 154 transitions. Word has length 138 [2018-10-10 15:29:15,613 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:15,613 INFO L481 AbstractCegarLoop]: Abstraction has 153 states and 154 transitions. [2018-10-10 15:29:15,613 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-10 15:29:15,614 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 154 transitions. [2018-10-10 15:29:15,615 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 153 [2018-10-10 15:29:15,615 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:15,616 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:15,616 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:15,616 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:15,617 INFO L82 PathProgramCache]: Analyzing trace with hash -516494524, now seen corresponding path program 7 times [2018-10-10 15:29:15,617 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:15,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:15,992 INFO L134 CoverageAnalysis]: Checked inductivity of 200 backedges. 60 proven. 140 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:15,993 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:15,993 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-10 15:29:15,993 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-10 15:29:15,994 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-10 15:29:15,994 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=354, Unknown=0, NotChecked=0, Total=420 [2018-10-10 15:29:15,994 INFO L87 Difference]: Start difference. First operand 153 states and 154 transitions. Second operand 21 states. [2018-10-10 15:29:16,683 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:16,684 INFO L93 Difference]: Finished difference Result 241 states and 242 transitions. [2018-10-10 15:29:16,684 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-10-10 15:29:16,684 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 152 [2018-10-10 15:29:16,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:16,686 INFO L225 Difference]: With dead ends: 241 [2018-10-10 15:29:16,686 INFO L226 Difference]: Without dead ends: 183 [2018-10-10 15:29:16,687 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 384 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=303, Invalid=1503, Unknown=0, NotChecked=0, Total=1806 [2018-10-10 15:29:16,688 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2018-10-10 15:29:16,691 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 169. [2018-10-10 15:29:16,692 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 169 states. [2018-10-10 15:29:16,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 170 transitions. [2018-10-10 15:29:16,693 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 170 transitions. Word has length 152 [2018-10-10 15:29:16,693 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:16,693 INFO L481 AbstractCegarLoop]: Abstraction has 169 states and 170 transitions. [2018-10-10 15:29:16,693 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-10 15:29:16,694 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 170 transitions. [2018-10-10 15:29:16,695 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 169 [2018-10-10 15:29:16,695 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:16,696 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:16,696 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:16,696 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:16,696 INFO L82 PathProgramCache]: Analyzing trace with hash 297545788, now seen corresponding path program 8 times [2018-10-10 15:29:16,697 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:16,713 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:17,876 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 44 proven. 221 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:17,876 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:17,876 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-10 15:29:17,877 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-10 15:29:17,877 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-10 15:29:17,877 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=542, Unknown=0, NotChecked=0, Total=600 [2018-10-10 15:29:17,878 INFO L87 Difference]: Start difference. First operand 169 states and 170 transitions. Second operand 25 states. [2018-10-10 15:29:19,977 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:19,977 INFO L93 Difference]: Finished difference Result 203 states and 204 transitions. [2018-10-10 15:29:19,977 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-10-10 15:29:19,978 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 168 [2018-10-10 15:29:19,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:19,980 INFO L225 Difference]: With dead ends: 203 [2018-10-10 15:29:19,980 INFO L226 Difference]: Without dead ends: 203 [2018-10-10 15:29:19,981 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 523 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=349, Invalid=2513, Unknown=0, NotChecked=0, Total=2862 [2018-10-10 15:29:19,982 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2018-10-10 15:29:19,985 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 183. [2018-10-10 15:29:19,985 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 183 states. [2018-10-10 15:29:19,986 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 184 transitions. [2018-10-10 15:29:19,986 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 184 transitions. Word has length 168 [2018-10-10 15:29:19,988 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:19,989 INFO L481 AbstractCegarLoop]: Abstraction has 183 states and 184 transitions. [2018-10-10 15:29:19,989 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-10 15:29:19,989 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 184 transitions. [2018-10-10 15:29:19,990 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2018-10-10 15:29:19,991 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:19,991 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:19,991 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:19,991 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:19,992 INFO L82 PathProgramCache]: Analyzing trace with hash -198514960, now seen corresponding path program 9 times [2018-10-10 15:29:19,992 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:20,008 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:20,666 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 107 proven. 218 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:20,667 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:20,667 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-10 15:29:20,668 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-10 15:29:20,668 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-10 15:29:20,668 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=510, Unknown=0, NotChecked=0, Total=600 [2018-10-10 15:29:20,668 INFO L87 Difference]: Start difference. First operand 183 states and 184 transitions. Second operand 25 states. [2018-10-10 15:29:21,485 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:21,486 INFO L93 Difference]: Finished difference Result 285 states and 286 transitions. [2018-10-10 15:29:21,486 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-10 15:29:21,486 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 182 [2018-10-10 15:29:21,487 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:21,489 INFO L225 Difference]: With dead ends: 285 [2018-10-10 15:29:21,489 INFO L226 Difference]: Without dead ends: 213 [2018-10-10 15:29:21,490 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 599 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=432, Invalid=2220, Unknown=0, NotChecked=0, Total=2652 [2018-10-10 15:29:21,490 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-10-10 15:29:21,493 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-10-10 15:29:21,493 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-10-10 15:29:21,494 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 200 transitions. [2018-10-10 15:29:21,494 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 200 transitions. Word has length 182 [2018-10-10 15:29:21,495 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:21,495 INFO L481 AbstractCegarLoop]: Abstraction has 199 states and 200 transitions. [2018-10-10 15:29:21,495 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-10 15:29:21,495 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 200 transitions. [2018-10-10 15:29:21,497 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-10-10 15:29:21,497 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:21,498 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:21,498 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:21,498 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:21,499 INFO L82 PathProgramCache]: Analyzing trace with hash 1151543784, now seen corresponding path program 10 times [2018-10-10 15:29:21,499 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:21,517 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:22,054 INFO L134 CoverageAnalysis]: Checked inductivity of 406 backedges. 128 proven. 278 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:22,055 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:22,055 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-10 15:29:22,055 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-10 15:29:22,055 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-10 15:29:22,056 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=721, Unknown=0, NotChecked=0, Total=812 [2018-10-10 15:29:22,056 INFO L87 Difference]: Start difference. First operand 199 states and 200 transitions. Second operand 29 states. [2018-10-10 15:29:25,042 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:25,043 INFO L93 Difference]: Finished difference Result 233 states and 234 transitions. [2018-10-10 15:29:25,051 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-10-10 15:29:25,051 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 198 [2018-10-10 15:29:25,051 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:25,052 INFO L225 Difference]: With dead ends: 233 [2018-10-10 15:29:25,053 INFO L226 Difference]: Without dead ends: 233 [2018-10-10 15:29:25,054 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 914 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=742, Invalid=3418, Unknown=0, NotChecked=0, Total=4160 [2018-10-10 15:29:25,055 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2018-10-10 15:29:25,058 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 213. [2018-10-10 15:29:25,059 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-10-10 15:29:25,060 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 214 transitions. [2018-10-10 15:29:25,060 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 214 transitions. Word has length 198 [2018-10-10 15:29:25,060 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:25,061 INFO L481 AbstractCegarLoop]: Abstraction has 213 states and 214 transitions. [2018-10-10 15:29:25,061 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-10 15:29:25,061 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 214 transitions. [2018-10-10 15:29:25,062 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-10-10 15:29:25,062 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:25,062 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:25,063 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:25,063 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:25,063 INFO L82 PathProgramCache]: Analyzing trace with hash -430603364, now seen corresponding path program 11 times [2018-10-10 15:29:25,064 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:25,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:26,002 INFO L134 CoverageAnalysis]: Checked inductivity of 480 backedges. 168 proven. 312 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:26,002 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:26,003 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-10 15:29:26,003 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-10 15:29:26,003 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-10 15:29:26,004 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=694, Unknown=0, NotChecked=0, Total=812 [2018-10-10 15:29:26,004 INFO L87 Difference]: Start difference. First operand 213 states and 214 transitions. Second operand 29 states. [2018-10-10 15:29:27,444 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-10-10 15:29:27,623 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:27,623 INFO L93 Difference]: Finished difference Result 329 states and 330 transitions. [2018-10-10 15:29:27,624 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-10-10 15:29:27,624 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 212 [2018-10-10 15:29:27,625 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:27,626 INFO L225 Difference]: With dead ends: 329 [2018-10-10 15:29:27,626 INFO L226 Difference]: Without dead ends: 243 [2018-10-10 15:29:27,628 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 861 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=585, Invalid=3075, Unknown=0, NotChecked=0, Total=3660 [2018-10-10 15:29:27,628 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 243 states. [2018-10-10 15:29:27,632 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 243 to 229. [2018-10-10 15:29:27,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 229 states. [2018-10-10 15:29:27,633 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 230 transitions. [2018-10-10 15:29:27,634 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 230 transitions. Word has length 212 [2018-10-10 15:29:27,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:27,634 INFO L481 AbstractCegarLoop]: Abstraction has 229 states and 230 transitions. [2018-10-10 15:29:27,634 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-10 15:29:27,635 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 230 transitions. [2018-10-10 15:29:27,636 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 229 [2018-10-10 15:29:27,636 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:27,637 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:27,637 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:27,637 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:27,637 INFO L82 PathProgramCache]: Analyzing trace with hash 1508918420, now seen corresponding path program 12 times [2018-10-10 15:29:27,638 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:27,658 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:28,540 INFO L134 CoverageAnalysis]: Checked inductivity of 577 backedges. 200 proven. 377 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:28,540 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:28,540 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-10 15:29:28,541 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-10 15:29:28,541 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-10 15:29:28,541 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=948, Unknown=0, NotChecked=0, Total=1056 [2018-10-10 15:29:28,542 INFO L87 Difference]: Start difference. First operand 229 states and 230 transitions. Second operand 33 states. [2018-10-10 15:29:31,210 WARN L178 SmtUtils]: Spent 443.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 41 [2018-10-10 15:29:32,287 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:32,287 INFO L93 Difference]: Finished difference Result 263 states and 264 transitions. [2018-10-10 15:29:32,288 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2018-10-10 15:29:32,288 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 228 [2018-10-10 15:29:32,288 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:32,289 INFO L225 Difference]: With dead ends: 263 [2018-10-10 15:29:32,289 INFO L226 Difference]: Without dead ends: 263 [2018-10-10 15:29:32,291 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1181 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=869, Invalid=4387, Unknown=0, NotChecked=0, Total=5256 [2018-10-10 15:29:32,292 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 263 states. [2018-10-10 15:29:32,295 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 263 to 243. [2018-10-10 15:29:32,295 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 243 states. [2018-10-10 15:29:32,296 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 244 transitions. [2018-10-10 15:29:32,296 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 244 transitions. Word has length 228 [2018-10-10 15:29:32,297 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:32,297 INFO L481 AbstractCegarLoop]: Abstraction has 243 states and 244 transitions. [2018-10-10 15:29:32,297 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-10 15:29:32,297 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 244 transitions. [2018-10-10 15:29:32,298 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 243 [2018-10-10 15:29:32,298 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:32,298 INFO L375 BasicCegarLoop]: trace histogram [8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:32,299 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:32,299 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:32,299 INFO L82 PathProgramCache]: Analyzing trace with hash -652705464, now seen corresponding path program 13 times [2018-10-10 15:29:32,300 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:32,318 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:33,244 INFO L134 CoverageAnalysis]: Checked inductivity of 665 backedges. 243 proven. 422 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:33,244 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:33,245 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-10 15:29:33,245 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-10 15:29:33,245 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-10 15:29:33,246 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=906, Unknown=0, NotChecked=0, Total=1056 [2018-10-10 15:29:33,246 INFO L87 Difference]: Start difference. First operand 243 states and 244 transitions. Second operand 33 states. [2018-10-10 15:29:34,457 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:34,458 INFO L93 Difference]: Finished difference Result 373 states and 374 transitions. [2018-10-10 15:29:34,458 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-10-10 15:29:34,458 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 242 [2018-10-10 15:29:34,459 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:34,460 INFO L225 Difference]: With dead ends: 373 [2018-10-10 15:29:34,461 INFO L226 Difference]: Without dead ends: 273 [2018-10-10 15:29:34,462 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1170 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=762, Invalid=4068, Unknown=0, NotChecked=0, Total=4830 [2018-10-10 15:29:34,463 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 273 states. [2018-10-10 15:29:34,466 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 273 to 259. [2018-10-10 15:29:34,466 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 259 states. [2018-10-10 15:29:34,467 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 259 states to 259 states and 260 transitions. [2018-10-10 15:29:34,467 INFO L78 Accepts]: Start accepts. Automaton has 259 states and 260 transitions. Word has length 242 [2018-10-10 15:29:34,467 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:34,468 INFO L481 AbstractCegarLoop]: Abstraction has 259 states and 260 transitions. [2018-10-10 15:29:34,468 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-10 15:29:34,468 INFO L276 IsEmpty]: Start isEmpty. Operand 259 states and 260 transitions. [2018-10-10 15:29:34,469 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 259 [2018-10-10 15:29:34,469 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:34,469 INFO L375 BasicCegarLoop]: trace histogram [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:34,470 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:34,470 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:34,470 INFO L82 PathProgramCache]: Analyzing trace with hash 1524973632, now seen corresponding path program 14 times [2018-10-10 15:29:34,471 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:34,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:35,678 INFO L134 CoverageAnalysis]: Checked inductivity of 778 backedges. 288 proven. 490 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:35,678 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:35,678 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-10 15:29:35,679 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-10 15:29:35,679 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-10 15:29:35,679 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=1205, Unknown=0, NotChecked=0, Total=1332 [2018-10-10 15:29:35,679 INFO L87 Difference]: Start difference. First operand 259 states and 260 transitions. Second operand 37 states. [2018-10-10 15:29:39,638 WARN L178 SmtUtils]: Spent 138.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 41 [2018-10-10 15:29:40,174 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:40,174 INFO L93 Difference]: Finished difference Result 293 states and 294 transitions. [2018-10-10 15:29:40,176 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-10-10 15:29:40,176 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 258 [2018-10-10 15:29:40,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:40,178 INFO L225 Difference]: With dead ends: 293 [2018-10-10 15:29:40,178 INFO L226 Difference]: Without dead ends: 293 [2018-10-10 15:29:40,185 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1523 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=1031, Invalid=5611, Unknown=0, NotChecked=0, Total=6642 [2018-10-10 15:29:40,186 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-10-10 15:29:40,192 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 273. [2018-10-10 15:29:40,192 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 273 states. [2018-10-10 15:29:40,193 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 273 states to 273 states and 274 transitions. [2018-10-10 15:29:40,193 INFO L78 Accepts]: Start accepts. Automaton has 273 states and 274 transitions. Word has length 258 [2018-10-10 15:29:40,194 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:40,194 INFO L481 AbstractCegarLoop]: Abstraction has 273 states and 274 transitions. [2018-10-10 15:29:40,194 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-10 15:29:40,194 INFO L276 IsEmpty]: Start isEmpty. Operand 273 states and 274 transitions. [2018-10-10 15:29:40,195 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2018-10-10 15:29:40,195 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:40,196 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:40,196 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:40,196 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:40,196 INFO L82 PathProgramCache]: Analyzing trace with hash -1616535564, now seen corresponding path program 15 times [2018-10-10 15:29:40,197 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:40,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:40,990 INFO L134 CoverageAnalysis]: Checked inductivity of 880 backedges. 332 proven. 548 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:40,990 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:40,990 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-10 15:29:40,991 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-10 15:29:40,991 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-10 15:29:40,991 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=186, Invalid=1146, Unknown=0, NotChecked=0, Total=1332 [2018-10-10 15:29:40,992 INFO L87 Difference]: Start difference. First operand 273 states and 274 transitions. Second operand 37 states. [2018-10-10 15:29:42,382 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:42,383 INFO L93 Difference]: Finished difference Result 417 states and 418 transitions. [2018-10-10 15:29:42,383 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-10 15:29:42,383 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 272 [2018-10-10 15:29:42,384 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:42,386 INFO L225 Difference]: With dead ends: 417 [2018-10-10 15:29:42,386 INFO L226 Difference]: Without dead ends: 303 [2018-10-10 15:29:42,388 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1526 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=963, Invalid=5199, Unknown=0, NotChecked=0, Total=6162 [2018-10-10 15:29:42,388 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2018-10-10 15:29:42,392 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 289. [2018-10-10 15:29:42,392 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 289 states. [2018-10-10 15:29:42,393 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 289 states to 289 states and 290 transitions. [2018-10-10 15:29:42,393 INFO L78 Accepts]: Start accepts. Automaton has 289 states and 290 transitions. Word has length 272 [2018-10-10 15:29:42,393 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:42,393 INFO L481 AbstractCegarLoop]: Abstraction has 289 states and 290 transitions. [2018-10-10 15:29:42,394 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-10 15:29:42,394 INFO L276 IsEmpty]: Start isEmpty. Operand 289 states and 290 transitions. [2018-10-10 15:29:42,395 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 289 [2018-10-10 15:29:42,395 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:42,395 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:42,396 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:42,396 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:42,396 INFO L82 PathProgramCache]: Analyzing trace with hash -90972948, now seen corresponding path program 16 times [2018-10-10 15:29:42,397 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:42,416 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:43,308 INFO L134 CoverageAnalysis]: Checked inductivity of 1009 backedges. 392 proven. 617 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:43,308 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:43,308 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-10 15:29:43,309 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-10 15:29:43,309 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-10 15:29:43,309 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=1492, Unknown=0, NotChecked=0, Total=1640 [2018-10-10 15:29:43,310 INFO L87 Difference]: Start difference. First operand 289 states and 290 transitions. Second operand 41 states. [2018-10-10 15:29:47,665 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:47,666 INFO L93 Difference]: Finished difference Result 323 states and 324 transitions. [2018-10-10 15:29:47,666 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-10-10 15:29:47,666 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 288 [2018-10-10 15:29:47,667 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:47,668 INFO L225 Difference]: With dead ends: 323 [2018-10-10 15:29:47,669 INFO L226 Difference]: Without dead ends: 323 [2018-10-10 15:29:47,672 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1906 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=1208, Invalid=6982, Unknown=0, NotChecked=0, Total=8190 [2018-10-10 15:29:47,672 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 323 states. [2018-10-10 15:29:47,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 323 to 303. [2018-10-10 15:29:47,676 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 303 states. [2018-10-10 15:29:47,677 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 303 states to 303 states and 304 transitions. [2018-10-10 15:29:47,677 INFO L78 Accepts]: Start accepts. Automaton has 303 states and 304 transitions. Word has length 288 [2018-10-10 15:29:47,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:47,678 INFO L481 AbstractCegarLoop]: Abstraction has 303 states and 304 transitions. [2018-10-10 15:29:47,678 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-10 15:29:47,678 INFO L276 IsEmpty]: Start isEmpty. Operand 303 states and 304 transitions. [2018-10-10 15:29:47,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 303 [2018-10-10 15:29:47,679 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:47,680 INFO L375 BasicCegarLoop]: trace histogram [10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:47,680 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:47,680 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:47,680 INFO L82 PathProgramCache]: Analyzing trace with hash 1258200992, now seen corresponding path program 17 times [2018-10-10 15:29:47,681 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:47,701 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:48,479 INFO L134 CoverageAnalysis]: Checked inductivity of 1125 backedges. 435 proven. 690 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:48,479 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:48,480 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-10 15:29:48,480 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-10 15:29:48,480 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-10 15:29:48,481 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=226, Invalid=1414, Unknown=0, NotChecked=0, Total=1640 [2018-10-10 15:29:48,481 INFO L87 Difference]: Start difference. First operand 303 states and 304 transitions. Second operand 41 states. [2018-10-10 15:29:49,845 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:49,846 INFO L93 Difference]: Finished difference Result 461 states and 462 transitions. [2018-10-10 15:29:49,846 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2018-10-10 15:29:49,846 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 302 [2018-10-10 15:29:49,847 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:49,849 INFO L225 Difference]: With dead ends: 461 [2018-10-10 15:29:49,849 INFO L226 Difference]: Without dead ends: 333 [2018-10-10 15:29:49,850 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1929 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=1188, Invalid=6468, Unknown=0, NotChecked=0, Total=7656 [2018-10-10 15:29:49,851 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 333 states. [2018-10-10 15:29:49,855 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 333 to 319. [2018-10-10 15:29:49,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 319 states. [2018-10-10 15:29:49,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 319 states to 319 states and 320 transitions. [2018-10-10 15:29:49,856 INFO L78 Accepts]: Start accepts. Automaton has 319 states and 320 transitions. Word has length 302 [2018-10-10 15:29:49,856 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:49,856 INFO L481 AbstractCegarLoop]: Abstraction has 319 states and 320 transitions. [2018-10-10 15:29:49,857 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-10 15:29:49,857 INFO L276 IsEmpty]: Start isEmpty. Operand 319 states and 320 transitions. [2018-10-10 15:29:49,858 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 319 [2018-10-10 15:29:49,858 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:49,859 INFO L375 BasicCegarLoop]: trace histogram [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:49,859 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:49,859 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:49,859 INFO L82 PathProgramCache]: Analyzing trace with hash 568187544, now seen corresponding path program 18 times [2018-10-10 15:29:49,860 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:49,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:51,297 INFO L134 CoverageAnalysis]: Checked inductivity of 1270 backedges. 512 proven. 758 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:51,297 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:51,298 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-10 15:29:51,298 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-10 15:29:51,298 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-10 15:29:51,299 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=219, Invalid=1761, Unknown=0, NotChecked=0, Total=1980 [2018-10-10 15:29:51,299 INFO L87 Difference]: Start difference. First operand 319 states and 320 transitions. Second operand 45 states. [2018-10-10 15:29:56,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:56,097 INFO L93 Difference]: Finished difference Result 353 states and 354 transitions. [2018-10-10 15:29:56,098 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-10-10 15:29:56,098 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 318 [2018-10-10 15:29:56,098 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:56,100 INFO L225 Difference]: With dead ends: 353 [2018-10-10 15:29:56,100 INFO L226 Difference]: Without dead ends: 353 [2018-10-10 15:29:56,101 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2716 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=1920, Invalid=9000, Unknown=0, NotChecked=0, Total=10920 [2018-10-10 15:29:56,102 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2018-10-10 15:29:56,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 333. [2018-10-10 15:29:56,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 333 states. [2018-10-10 15:29:56,107 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 334 transitions. [2018-10-10 15:29:56,107 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 334 transitions. Word has length 318 [2018-10-10 15:29:56,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:56,108 INFO L481 AbstractCegarLoop]: Abstraction has 333 states and 334 transitions. [2018-10-10 15:29:56,108 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-10 15:29:56,108 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 334 transitions. [2018-10-10 15:29:56,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 333 [2018-10-10 15:29:56,110 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:56,110 INFO L375 BasicCegarLoop]: trace histogram [11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:56,110 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:56,110 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:56,110 INFO L82 PathProgramCache]: Analyzing trace with hash -1242218420, now seen corresponding path program 19 times [2018-10-10 15:29:56,111 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:56,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:29:57,268 INFO L134 CoverageAnalysis]: Checked inductivity of 1400 backedges. 552 proven. 848 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:29:57,268 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:29:57,269 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-10 15:29:57,269 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-10 15:29:57,270 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-10 15:29:57,270 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=270, Invalid=1710, Unknown=0, NotChecked=0, Total=1980 [2018-10-10 15:29:57,270 INFO L87 Difference]: Start difference. First operand 333 states and 334 transitions. Second operand 45 states. [2018-10-10 15:29:59,296 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:29:59,296 INFO L93 Difference]: Finished difference Result 505 states and 506 transitions. [2018-10-10 15:29:59,296 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-10-10 15:29:59,296 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 332 [2018-10-10 15:29:59,297 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:29:59,300 INFO L225 Difference]: With dead ends: 505 [2018-10-10 15:29:59,300 INFO L226 Difference]: Without dead ends: 363 [2018-10-10 15:29:59,301 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2379 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=1437, Invalid=7875, Unknown=0, NotChecked=0, Total=9312 [2018-10-10 15:29:59,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 363 states. [2018-10-10 15:29:59,305 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 363 to 349. [2018-10-10 15:29:59,305 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 349 states. [2018-10-10 15:29:59,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 349 states to 349 states and 350 transitions. [2018-10-10 15:29:59,306 INFO L78 Accepts]: Start accepts. Automaton has 349 states and 350 transitions. Word has length 332 [2018-10-10 15:29:59,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:29:59,306 INFO L481 AbstractCegarLoop]: Abstraction has 349 states and 350 transitions. [2018-10-10 15:29:59,307 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-10 15:29:59,307 INFO L276 IsEmpty]: Start isEmpty. Operand 349 states and 350 transitions. [2018-10-10 15:29:59,309 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 349 [2018-10-10 15:29:59,309 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:29:59,309 INFO L375 BasicCegarLoop]: trace histogram [11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:29:59,309 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:29:59,310 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:29:59,310 INFO L82 PathProgramCache]: Analyzing trace with hash 2071263556, now seen corresponding path program 20 times [2018-10-10 15:29:59,311 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:29:59,334 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:30:00,518 INFO L134 CoverageAnalysis]: Checked inductivity of 1561 backedges. 648 proven. 913 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:30:00,518 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:30:00,518 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-10 15:30:00,519 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-10 15:30:00,519 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-10 15:30:00,519 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=244, Invalid=2108, Unknown=0, NotChecked=0, Total=2352 [2018-10-10 15:30:00,519 INFO L87 Difference]: Start difference. First operand 349 states and 350 transitions. Second operand 49 states. [2018-10-10 15:30:06,392 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:30:06,393 INFO L93 Difference]: Finished difference Result 383 states and 384 transitions. [2018-10-10 15:30:06,393 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-10 15:30:06,393 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 348 [2018-10-10 15:30:06,393 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:30:06,395 INFO L225 Difference]: With dead ends: 383 [2018-10-10 15:30:06,395 INFO L226 Difference]: Without dead ends: 383 [2018-10-10 15:30:06,397 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3155 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=2127, Invalid=10529, Unknown=0, NotChecked=0, Total=12656 [2018-10-10 15:30:06,397 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 383 states. [2018-10-10 15:30:06,401 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 383 to 363. [2018-10-10 15:30:06,401 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 363 states. [2018-10-10 15:30:06,402 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 364 transitions. [2018-10-10 15:30:06,402 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 364 transitions. Word has length 348 [2018-10-10 15:30:06,403 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:30:06,403 INFO L481 AbstractCegarLoop]: Abstraction has 363 states and 364 transitions. [2018-10-10 15:30:06,403 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-10 15:30:06,403 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 364 transitions. [2018-10-10 15:30:06,405 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 363 [2018-10-10 15:30:06,405 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:30:06,405 INFO L375 BasicCegarLoop]: trace histogram [12, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:30:06,405 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:30:06,406 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:30:06,406 INFO L82 PathProgramCache]: Analyzing trace with hash 288047608, now seen corresponding path program 21 times [2018-10-10 15:30:06,407 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:30:06,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:30:07,334 INFO L134 CoverageAnalysis]: Checked inductivity of 1705 backedges. 683 proven. 1022 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:30:07,335 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:30:07,335 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-10 15:30:07,335 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-10 15:30:07,336 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-10 15:30:07,336 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=318, Invalid=2034, Unknown=0, NotChecked=0, Total=2352 [2018-10-10 15:30:07,337 INFO L87 Difference]: Start difference. First operand 363 states and 364 transitions. Second operand 49 states. [2018-10-10 15:30:09,556 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:30:09,556 INFO L93 Difference]: Finished difference Result 549 states and 550 transitions. [2018-10-10 15:30:09,556 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 71 states. [2018-10-10 15:30:09,556 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 362 [2018-10-10 15:30:09,557 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:30:09,559 INFO L225 Difference]: With dead ends: 549 [2018-10-10 15:30:09,559 INFO L226 Difference]: Without dead ends: 393 [2018-10-10 15:30:09,560 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2876 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=1710, Invalid=9420, Unknown=0, NotChecked=0, Total=11130 [2018-10-10 15:30:09,561 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 393 states. [2018-10-10 15:30:09,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 393 to 379. [2018-10-10 15:30:09,564 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-10-10 15:30:09,565 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 380 transitions. [2018-10-10 15:30:09,565 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 380 transitions. Word has length 362 [2018-10-10 15:30:09,566 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:30:09,566 INFO L481 AbstractCegarLoop]: Abstraction has 379 states and 380 transitions. [2018-10-10 15:30:09,566 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-10 15:30:09,566 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 380 transitions. [2018-10-10 15:30:09,568 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 379 [2018-10-10 15:30:09,568 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:30:09,568 INFO L375 BasicCegarLoop]: trace histogram [12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:30:09,569 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:30:09,569 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:30:09,569 INFO L82 PathProgramCache]: Analyzing trace with hash -2426640, now seen corresponding path program 22 times [2018-10-10 15:30:09,570 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:30:09,594 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:30:11,298 INFO L134 CoverageAnalysis]: Checked inductivity of 1882 backedges. 800 proven. 1082 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:30:11,298 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:30:11,299 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-10 15:30:11,299 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-10 15:30:11,299 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-10 15:30:11,300 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=271, Invalid=2485, Unknown=0, NotChecked=0, Total=2756 [2018-10-10 15:30:11,300 INFO L87 Difference]: Start difference. First operand 379 states and 380 transitions. Second operand 53 states. [2018-10-10 15:30:17,482 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:30:17,482 INFO L93 Difference]: Finished difference Result 413 states and 414 transitions. [2018-10-10 15:30:17,482 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-10 15:30:17,483 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 378 [2018-10-10 15:30:17,483 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:30:17,484 INFO L225 Difference]: With dead ends: 413 [2018-10-10 15:30:17,484 INFO L226 Difference]: Without dead ends: 413 [2018-10-10 15:30:17,485 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3697 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=2377, Invalid=12385, Unknown=0, NotChecked=0, Total=14762 [2018-10-10 15:30:17,486 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 413 states. [2018-10-10 15:30:17,489 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 413 to 393. [2018-10-10 15:30:17,490 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 393 states. [2018-10-10 15:30:17,490 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 393 states to 393 states and 394 transitions. [2018-10-10 15:30:17,491 INFO L78 Accepts]: Start accepts. Automaton has 393 states and 394 transitions. Word has length 378 [2018-10-10 15:30:17,491 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:30:17,491 INFO L481 AbstractCegarLoop]: Abstraction has 393 states and 394 transitions. [2018-10-10 15:30:17,491 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-10 15:30:17,491 INFO L276 IsEmpty]: Start isEmpty. Operand 393 states and 394 transitions. [2018-10-10 15:30:17,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 393 [2018-10-10 15:30:17,493 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:30:17,494 INFO L375 BasicCegarLoop]: trace histogram [13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:30:17,494 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:30:17,494 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:30:17,494 INFO L82 PathProgramCache]: Analyzing trace with hash 1863476388, now seen corresponding path program 23 times [2018-10-10 15:30:17,495 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:30:17,519 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:30:19,255 INFO L134 CoverageAnalysis]: Checked inductivity of 2040 backedges. 828 proven. 1212 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:30:19,256 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:30:19,256 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-10 15:30:19,256 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-10 15:30:19,257 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-10 15:30:19,257 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=370, Invalid=2386, Unknown=0, NotChecked=0, Total=2756 [2018-10-10 15:30:19,257 INFO L87 Difference]: Start difference. First operand 393 states and 394 transitions. Second operand 53 states. [2018-10-10 15:30:21,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:30:21,894 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-10 15:30:21,894 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-10 15:30:21,894 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 392 [2018-10-10 15:30:21,895 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:30:21,896 INFO L225 Difference]: With dead ends: 593 [2018-10-10 15:30:21,896 INFO L226 Difference]: Without dead ends: 423 [2018-10-10 15:30:21,897 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3420 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=2007, Invalid=11103, Unknown=0, NotChecked=0, Total=13110 [2018-10-10 15:30:21,897 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 423 states. [2018-10-10 15:30:21,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 423 to 409. [2018-10-10 15:30:21,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 409 states. [2018-10-10 15:30:21,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 409 states to 409 states and 410 transitions. [2018-10-10 15:30:21,902 INFO L78 Accepts]: Start accepts. Automaton has 409 states and 410 transitions. Word has length 392 [2018-10-10 15:30:21,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:30:21,903 INFO L481 AbstractCegarLoop]: Abstraction has 409 states and 410 transitions. [2018-10-10 15:30:21,903 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-10 15:30:21,903 INFO L276 IsEmpty]: Start isEmpty. Operand 409 states and 410 transitions. [2018-10-10 15:30:21,905 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 409 [2018-10-10 15:30:21,905 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:30:21,905 INFO L375 BasicCegarLoop]: trace histogram [13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:30:21,906 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:30:21,906 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:30:21,906 INFO L82 PathProgramCache]: Analyzing trace with hash -2124310116, now seen corresponding path program 24 times [2018-10-10 15:30:21,907 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:30:21,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:30:25,005 INFO L134 CoverageAnalysis]: Checked inductivity of 2233 backedges. 860 proven. 1373 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:30:25,006 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:30:25,006 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-10 15:30:25,006 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-10 15:30:25,007 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-10 15:30:25,007 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=234, Invalid=2958, Unknown=0, NotChecked=0, Total=3192 [2018-10-10 15:30:25,007 INFO L87 Difference]: Start difference. First operand 409 states and 410 transitions. Second operand 57 states. [2018-10-10 15:30:32,812 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:30:32,813 INFO L93 Difference]: Finished difference Result 443 states and 444 transitions. [2018-10-10 15:30:32,813 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-10-10 15:30:32,813 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 408 [2018-10-10 15:30:32,814 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:30:32,816 INFO L225 Difference]: With dead ends: 443 [2018-10-10 15:30:32,816 INFO L226 Difference]: Without dead ends: 443 [2018-10-10 15:30:32,817 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3543 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=1645, Invalid=14105, Unknown=0, NotChecked=0, Total=15750 [2018-10-10 15:30:32,818 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 443 states. [2018-10-10 15:30:32,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 443 to 423. [2018-10-10 15:30:32,822 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 423 states. [2018-10-10 15:30:32,822 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 423 states to 423 states and 424 transitions. [2018-10-10 15:30:32,823 INFO L78 Accepts]: Start accepts. Automaton has 423 states and 424 transitions. Word has length 408 [2018-10-10 15:30:32,823 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:30:32,823 INFO L481 AbstractCegarLoop]: Abstraction has 423 states and 424 transitions. [2018-10-10 15:30:32,823 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-10 15:30:32,823 INFO L276 IsEmpty]: Start isEmpty. Operand 423 states and 424 transitions. [2018-10-10 15:30:32,825 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 423 [2018-10-10 15:30:32,826 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:30:32,826 INFO L375 BasicCegarLoop]: trace histogram [14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:30:32,826 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:30:32,826 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:30:32,827 INFO L82 PathProgramCache]: Analyzing trace with hash 1340893264, now seen corresponding path program 25 times [2018-10-10 15:30:32,827 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:30:32,853 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:30:33,975 INFO L134 CoverageAnalysis]: Checked inductivity of 2405 backedges. 987 proven. 1418 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:30:33,975 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:30:33,975 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-10 15:30:33,976 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-10 15:30:33,976 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-10 15:30:33,976 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=426, Invalid=2766, Unknown=0, NotChecked=0, Total=3192 [2018-10-10 15:30:33,976 INFO L87 Difference]: Start difference. First operand 423 states and 424 transitions. Second operand 57 states. [2018-10-10 15:30:36,919 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:30:36,919 INFO L93 Difference]: Finished difference Result 637 states and 638 transitions. [2018-10-10 15:30:36,919 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-10 15:30:36,919 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 422 [2018-10-10 15:30:36,920 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:30:36,922 INFO L225 Difference]: With dead ends: 637 [2018-10-10 15:30:36,922 INFO L226 Difference]: Without dead ends: 453 [2018-10-10 15:30:36,923 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4011 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=2328, Invalid=12924, Unknown=0, NotChecked=0, Total=15252 [2018-10-10 15:30:36,923 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 453 states. [2018-10-10 15:30:36,927 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 453 to 439. [2018-10-10 15:30:36,927 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 439 states. [2018-10-10 15:30:36,928 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 439 states to 439 states and 440 transitions. [2018-10-10 15:30:36,928 INFO L78 Accepts]: Start accepts. Automaton has 439 states and 440 transitions. Word has length 422 [2018-10-10 15:30:36,928 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:30:36,928 INFO L481 AbstractCegarLoop]: Abstraction has 439 states and 440 transitions. [2018-10-10 15:30:36,928 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-10 15:30:36,929 INFO L276 IsEmpty]: Start isEmpty. Operand 439 states and 440 transitions. [2018-10-10 15:30:36,931 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 439 [2018-10-10 15:30:36,931 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:30:36,931 INFO L375 BasicCegarLoop]: trace histogram [14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:30:36,931 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:30:36,932 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:30:36,932 INFO L82 PathProgramCache]: Analyzing trace with hash 942316360, now seen corresponding path program 26 times [2018-10-10 15:30:36,932 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:30:36,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:30:38,597 INFO L134 CoverageAnalysis]: Checked inductivity of 2614 backedges. 1152 proven. 1462 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:30:38,597 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:30:38,597 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-10 15:30:38,597 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-10 15:30:38,598 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-10 15:30:38,598 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=411, Invalid=3249, Unknown=0, NotChecked=0, Total=3660 [2018-10-10 15:30:38,598 INFO L87 Difference]: Start difference. First operand 439 states and 440 transitions. Second operand 61 states. [2018-10-10 15:30:46,729 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:30:46,729 INFO L93 Difference]: Finished difference Result 473 states and 474 transitions. [2018-10-10 15:30:46,729 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-10-10 15:30:46,729 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 438 [2018-10-10 15:30:46,730 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:30:46,731 INFO L225 Difference]: With dead ends: 473 [2018-10-10 15:30:46,731 INFO L226 Difference]: Without dead ends: 473 [2018-10-10 15:30:46,734 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5462 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=3658, Invalid=17222, Unknown=0, NotChecked=0, Total=20880 [2018-10-10 15:30:46,734 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 473 states. [2018-10-10 15:30:46,738 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 473 to 453. [2018-10-10 15:30:46,738 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 453 states. [2018-10-10 15:30:46,739 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 453 states to 453 states and 454 transitions. [2018-10-10 15:30:46,739 INFO L78 Accepts]: Start accepts. Automaton has 453 states and 454 transitions. Word has length 438 [2018-10-10 15:30:46,739 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:30:46,739 INFO L481 AbstractCegarLoop]: Abstraction has 453 states and 454 transitions. [2018-10-10 15:30:46,740 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-10 15:30:46,740 INFO L276 IsEmpty]: Start isEmpty. Operand 453 states and 454 transitions. [2018-10-10 15:30:46,742 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 453 [2018-10-10 15:30:46,742 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:30:46,742 INFO L375 BasicCegarLoop]: trace histogram [15, 15, 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:30:46,743 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:30:46,743 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:30:46,743 INFO L82 PathProgramCache]: Analyzing trace with hash 768281852, now seen corresponding path program 27 times [2018-10-10 15:30:46,744 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:30:46,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:30:48,204 INFO L134 CoverageAnalysis]: Checked inductivity of 2800 backedges. 1160 proven. 1640 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:30:48,204 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:30:48,204 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-10 15:30:48,205 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-10 15:30:48,205 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-10 15:30:48,205 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=486, Invalid=3174, Unknown=0, NotChecked=0, Total=3660 [2018-10-10 15:30:48,205 INFO L87 Difference]: Start difference. First operand 453 states and 454 transitions. Second operand 61 states. [2018-10-10 15:30:51,166 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:30:51,167 INFO L93 Difference]: Finished difference Result 681 states and 682 transitions. [2018-10-10 15:30:51,167 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-10-10 15:30:51,167 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 452 [2018-10-10 15:30:51,168 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:30:51,169 INFO L225 Difference]: With dead ends: 681 [2018-10-10 15:30:51,169 INFO L226 Difference]: Without dead ends: 483 [2018-10-10 15:30:51,171 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 131 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4649 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=2673, Invalid=14883, Unknown=0, NotChecked=0, Total=17556 [2018-10-10 15:30:51,171 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 483 states. [2018-10-10 15:30:51,175 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 483 to 469. [2018-10-10 15:30:51,175 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 469 states. [2018-10-10 15:30:51,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 469 states to 469 states and 470 transitions. [2018-10-10 15:30:51,176 INFO L78 Accepts]: Start accepts. Automaton has 469 states and 470 transitions. Word has length 452 [2018-10-10 15:30:51,177 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:30:51,177 INFO L481 AbstractCegarLoop]: Abstraction has 469 states and 470 transitions. [2018-10-10 15:30:51,177 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-10 15:30:51,177 INFO L276 IsEmpty]: Start isEmpty. Operand 469 states and 470 transitions. [2018-10-10 15:30:51,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 469 [2018-10-10 15:30:51,179 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:30:51,180 INFO L375 BasicCegarLoop]: trace histogram [15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:30:51,180 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:30:51,180 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:30:51,181 INFO L82 PathProgramCache]: Analyzing trace with hash 1311227380, now seen corresponding path program 28 times [2018-10-10 15:30:51,181 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:30:51,210 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:30:53,499 INFO L134 CoverageAnalysis]: Checked inductivity of 3025 backedges. 1352 proven. 1673 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:30:53,500 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:30:53,500 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-10 15:30:53,500 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-10 15:30:53,501 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-10 15:30:53,501 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=444, Invalid=3716, Unknown=0, NotChecked=0, Total=4160 [2018-10-10 15:30:53,501 INFO L87 Difference]: Start difference. First operand 469 states and 470 transitions. Second operand 65 states. [2018-10-10 15:31:02,627 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:31:02,627 INFO L93 Difference]: Finished difference Result 503 states and 504 transitions. [2018-10-10 15:31:02,627 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 105 states. [2018-10-10 15:31:02,627 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 468 [2018-10-10 15:31:02,628 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:31:02,629 INFO L225 Difference]: With dead ends: 503 [2018-10-10 15:31:02,629 INFO L226 Difference]: Without dead ends: 503 [2018-10-10 15:31:02,630 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 151 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6073 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=3945, Invalid=19311, Unknown=0, NotChecked=0, Total=23256 [2018-10-10 15:31:02,631 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 503 states. [2018-10-10 15:31:02,634 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 503 to 483. [2018-10-10 15:31:02,634 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 483 states. [2018-10-10 15:31:02,635 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 483 states to 483 states and 484 transitions. [2018-10-10 15:31:02,635 INFO L78 Accepts]: Start accepts. Automaton has 483 states and 484 transitions. Word has length 468 [2018-10-10 15:31:02,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:31:02,636 INFO L481 AbstractCegarLoop]: Abstraction has 483 states and 484 transitions. [2018-10-10 15:31:02,636 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-10 15:31:02,636 INFO L276 IsEmpty]: Start isEmpty. Operand 483 states and 484 transitions. [2018-10-10 15:31:02,639 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 483 [2018-10-10 15:31:02,639 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:31:02,639 INFO L375 BasicCegarLoop]: trace histogram [16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:31:02,639 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:31:02,640 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:31:02,640 INFO L82 PathProgramCache]: Analyzing trace with hash 143659688, now seen corresponding path program 29 times [2018-10-10 15:31:02,640 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:31:02,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:31:05,187 INFO L134 CoverageAnalysis]: Checked inductivity of 3225 backedges. 1347 proven. 1878 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:31:05,188 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:31:05,188 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-10 15:31:05,188 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-10 15:31:05,189 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-10 15:31:05,189 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=550, Invalid=3610, Unknown=0, NotChecked=0, Total=4160 [2018-10-10 15:31:05,189 INFO L87 Difference]: Start difference. First operand 483 states and 484 transitions. Second operand 65 states. [2018-10-10 15:31:08,871 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:31:08,871 INFO L93 Difference]: Finished difference Result 725 states and 726 transitions. [2018-10-10 15:31:08,871 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 95 states. [2018-10-10 15:31:08,872 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 482 [2018-10-10 15:31:08,872 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:31:08,874 INFO L225 Difference]: With dead ends: 725 [2018-10-10 15:31:08,874 INFO L226 Difference]: Without dead ends: 513 [2018-10-10 15:31:08,875 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5334 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=3042, Invalid=16980, Unknown=0, NotChecked=0, Total=20022 [2018-10-10 15:31:08,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 513 states. [2018-10-10 15:31:08,878 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 513 to 499. [2018-10-10 15:31:08,879 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 499 states. [2018-10-10 15:31:08,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 499 states to 499 states and 500 transitions. [2018-10-10 15:31:08,880 INFO L78 Accepts]: Start accepts. Automaton has 499 states and 500 transitions. Word has length 482 [2018-10-10 15:31:08,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:31:08,880 INFO L481 AbstractCegarLoop]: Abstraction has 499 states and 500 transitions. [2018-10-10 15:31:08,880 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-10 15:31:08,880 INFO L276 IsEmpty]: Start isEmpty. Operand 499 states and 500 transitions. [2018-10-10 15:31:08,883 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 499 [2018-10-10 15:31:08,883 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:31:08,884 INFO L375 BasicCegarLoop]: trace histogram [16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:31:08,884 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:31:08,884 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:31:08,884 INFO L82 PathProgramCache]: Analyzing trace with hash 1796915616, now seen corresponding path program 30 times [2018-10-10 15:31:08,885 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:31:08,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:31:11,105 INFO L134 CoverageAnalysis]: Checked inductivity of 3466 backedges. 1568 proven. 1898 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:31:11,106 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:31:11,106 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-10 15:31:11,107 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-10 15:31:11,107 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-10 15:31:11,107 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=4213, Unknown=0, NotChecked=0, Total=4692 [2018-10-10 15:31:11,107 INFO L87 Difference]: Start difference. First operand 499 states and 500 transitions. Second operand 69 states. [2018-10-10 15:31:21,697 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:31:21,698 INFO L93 Difference]: Finished difference Result 533 states and 534 transitions. [2018-10-10 15:31:21,698 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 111 states. [2018-10-10 15:31:21,698 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 498 [2018-10-10 15:31:21,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:31:21,700 INFO L225 Difference]: With dead ends: 533 [2018-10-10 15:31:21,700 INFO L226 Difference]: Without dead ends: 533 [2018-10-10 15:31:21,702 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 160 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6815 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=4283, Invalid=21799, Unknown=0, NotChecked=0, Total=26082 [2018-10-10 15:31:21,702 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 533 states. [2018-10-10 15:31:21,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 533 to 513. [2018-10-10 15:31:21,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 513 states. [2018-10-10 15:31:21,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 513 states to 513 states and 514 transitions. [2018-10-10 15:31:21,707 INFO L78 Accepts]: Start accepts. Automaton has 513 states and 514 transitions. Word has length 498 [2018-10-10 15:31:21,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:31:21,708 INFO L481 AbstractCegarLoop]: Abstraction has 513 states and 514 transitions. [2018-10-10 15:31:21,708 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-10 15:31:21,708 INFO L276 IsEmpty]: Start isEmpty. Operand 513 states and 514 transitions. [2018-10-10 15:31:21,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 513 [2018-10-10 15:31:21,711 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:31:21,711 INFO L375 BasicCegarLoop]: trace histogram [17, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:31:21,712 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:31:21,712 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:31:21,712 INFO L82 PathProgramCache]: Analyzing trace with hash -236111532, now seen corresponding path program 31 times [2018-10-10 15:31:21,713 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:31:21,742 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:31:23,955 INFO L134 CoverageAnalysis]: Checked inductivity of 3680 backedges. 1548 proven. 2132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:31:23,955 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:31:23,955 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-10 15:31:23,956 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-10 15:31:23,956 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-10 15:31:23,956 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=618, Invalid=4074, Unknown=0, NotChecked=0, Total=4692 [2018-10-10 15:31:23,957 INFO L87 Difference]: Start difference. First operand 513 states and 514 transitions. Second operand 69 states. [2018-10-10 15:31:28,229 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:31:28,230 INFO L93 Difference]: Finished difference Result 769 states and 770 transitions. [2018-10-10 15:31:28,230 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 101 states. [2018-10-10 15:31:28,230 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 512 [2018-10-10 15:31:28,231 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:31:28,233 INFO L225 Difference]: With dead ends: 769 [2018-10-10 15:31:28,233 INFO L226 Difference]: Without dead ends: 543 [2018-10-10 15:31:28,234 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 149 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6066 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=3435, Invalid=19215, Unknown=0, NotChecked=0, Total=22650 [2018-10-10 15:31:28,234 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 543 states. [2018-10-10 15:31:28,238 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 543 to 529. [2018-10-10 15:31:28,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 529 states. [2018-10-10 15:31:28,239 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 529 states to 529 states and 530 transitions. [2018-10-10 15:31:28,239 INFO L78 Accepts]: Start accepts. Automaton has 529 states and 530 transitions. Word has length 512 [2018-10-10 15:31:28,240 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:31:28,240 INFO L481 AbstractCegarLoop]: Abstraction has 529 states and 530 transitions. [2018-10-10 15:31:28,240 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-10 15:31:28,240 INFO L276 IsEmpty]: Start isEmpty. Operand 529 states and 530 transitions. [2018-10-10 15:31:28,243 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 529 [2018-10-10 15:31:28,243 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:31:28,243 INFO L375 BasicCegarLoop]: trace histogram [17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:31:28,243 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:31:28,244 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:31:28,244 INFO L82 PathProgramCache]: Analyzing trace with hash 1083532876, now seen corresponding path program 32 times [2018-10-10 15:31:28,244 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:31:28,277 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:31:30,502 INFO L134 CoverageAnalysis]: Checked inductivity of 3937 backedges. 1800 proven. 2137 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:31:30,502 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:31:30,502 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-10 15:31:30,502 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-10 15:31:30,503 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-10 15:31:30,503 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=516, Invalid=4740, Unknown=0, NotChecked=0, Total=5256 [2018-10-10 15:31:30,503 INFO L87 Difference]: Start difference. First operand 529 states and 530 transitions. Second operand 73 states. [2018-10-10 15:31:42,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:31:42,275 INFO L93 Difference]: Finished difference Result 563 states and 564 transitions. [2018-10-10 15:31:42,275 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-10-10 15:31:42,275 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 528 [2018-10-10 15:31:42,275 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:31:42,277 INFO L225 Difference]: With dead ends: 563 [2018-10-10 15:31:42,277 INFO L226 Difference]: Without dead ends: 563 [2018-10-10 15:31:42,278 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 169 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7598 ImplicationChecksByTransitivity, 8.5s TimeCoverageRelationStatistics Valid=4636, Invalid=24434, Unknown=0, NotChecked=0, Total=29070 [2018-10-10 15:31:42,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 563 states. [2018-10-10 15:31:42,282 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 563 to 543. [2018-10-10 15:31:42,282 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 543 states. [2018-10-10 15:31:42,283 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 543 states to 543 states and 544 transitions. [2018-10-10 15:31:42,283 INFO L78 Accepts]: Start accepts. Automaton has 543 states and 544 transitions. Word has length 528 [2018-10-10 15:31:42,284 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:31:42,284 INFO L481 AbstractCegarLoop]: Abstraction has 543 states and 544 transitions. [2018-10-10 15:31:42,284 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-10 15:31:42,284 INFO L276 IsEmpty]: Start isEmpty. Operand 543 states and 544 transitions. [2018-10-10 15:31:42,287 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 543 [2018-10-10 15:31:42,287 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:31:42,288 INFO L375 BasicCegarLoop]: trace histogram [18, 18, 18, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:31:42,288 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:31:42,288 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:31:42,288 INFO L82 PathProgramCache]: Analyzing trace with hash -1721483008, now seen corresponding path program 33 times [2018-10-10 15:31:42,289 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:31:42,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:31:45,417 INFO L134 CoverageAnalysis]: Checked inductivity of 4165 backedges. 1763 proven. 2402 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:31:45,418 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:31:45,418 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-10 15:31:45,418 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-10 15:31:45,419 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-10 15:31:45,419 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=690, Invalid=4566, Unknown=0, NotChecked=0, Total=5256 [2018-10-10 15:31:45,419 INFO L87 Difference]: Start difference. First operand 543 states and 544 transitions. Second operand 73 states. [2018-10-10 15:31:50,079 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:31:50,080 INFO L93 Difference]: Finished difference Result 813 states and 814 transitions. [2018-10-10 15:31:50,080 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 107 states. [2018-10-10 15:31:50,080 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 542 [2018-10-10 15:31:50,081 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:31:50,083 INFO L225 Difference]: With dead ends: 813 [2018-10-10 15:31:50,083 INFO L226 Difference]: Without dead ends: 573 [2018-10-10 15:31:50,084 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 158 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6845 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=3852, Invalid=21588, Unknown=0, NotChecked=0, Total=25440 [2018-10-10 15:31:50,085 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 573 states. [2018-10-10 15:31:50,089 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 573 to 559. [2018-10-10 15:31:50,089 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 559 states. [2018-10-10 15:31:50,090 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 559 states to 559 states and 560 transitions. [2018-10-10 15:31:50,090 INFO L78 Accepts]: Start accepts. Automaton has 559 states and 560 transitions. Word has length 542 [2018-10-10 15:31:50,091 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:31:50,091 INFO L481 AbstractCegarLoop]: Abstraction has 559 states and 560 transitions. [2018-10-10 15:31:50,091 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-10 15:31:50,091 INFO L276 IsEmpty]: Start isEmpty. Operand 559 states and 560 transitions. [2018-10-10 15:31:50,094 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 559 [2018-10-10 15:31:50,095 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:31:50,095 INFO L375 BasicCegarLoop]: trace histogram [18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:31:50,095 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:31:50,095 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:31:50,096 INFO L82 PathProgramCache]: Analyzing trace with hash 368667640, now seen corresponding path program 34 times [2018-10-10 15:31:50,096 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:31:50,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:31:52,604 INFO L134 CoverageAnalysis]: Checked inductivity of 4438 backedges. 2048 proven. 2390 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:31:52,604 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:31:52,605 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-10 15:31:52,605 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-10 15:31:52,606 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-10 15:31:52,606 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=667, Invalid=5185, Unknown=0, NotChecked=0, Total=5852 [2018-10-10 15:31:52,606 INFO L87 Difference]: Start difference. First operand 559 states and 560 transitions. Second operand 77 states. [2018-10-10 15:32:04,536 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:32:04,536 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-10 15:32:04,543 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-10-10 15:32:04,543 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 558 [2018-10-10 15:32:04,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:32:04,545 INFO L225 Difference]: With dead ends: 593 [2018-10-10 15:32:04,545 INFO L226 Difference]: Without dead ends: 593 [2018-10-10 15:32:04,546 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 183 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9152 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=5956, Invalid=28084, Unknown=0, NotChecked=0, Total=34040 [2018-10-10 15:32:04,546 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 593 states. [2018-10-10 15:32:04,550 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 593 to 573. [2018-10-10 15:32:04,551 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 573 states. [2018-10-10 15:32:04,552 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 573 states to 573 states and 574 transitions. [2018-10-10 15:32:04,552 INFO L78 Accepts]: Start accepts. Automaton has 573 states and 574 transitions. Word has length 558 [2018-10-10 15:32:04,552 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:32:04,552 INFO L481 AbstractCegarLoop]: Abstraction has 573 states and 574 transitions. [2018-10-10 15:32:04,553 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-10 15:32:04,553 INFO L276 IsEmpty]: Start isEmpty. Operand 573 states and 574 transitions. [2018-10-10 15:32:04,556 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 573 [2018-10-10 15:32:04,556 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:32:04,557 INFO L375 BasicCegarLoop]: trace histogram [19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:32:04,557 INFO L424 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:32:04,557 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:32:04,557 INFO L82 PathProgramCache]: Analyzing trace with hash -666441300, now seen corresponding path program 35 times [2018-10-10 15:32:04,558 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:32:04,591 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:32:07,038 INFO L134 CoverageAnalysis]: Checked inductivity of 4680 backedges. 1992 proven. 2688 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:32:07,038 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:32:07,038 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-10 15:32:07,039 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-10 15:32:07,039 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-10 15:32:07,039 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=766, Invalid=5086, Unknown=0, NotChecked=0, Total=5852 [2018-10-10 15:32:07,040 INFO L87 Difference]: Start difference. First operand 573 states and 574 transitions. Second operand 77 states. [2018-10-10 15:32:11,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:32:11,911 INFO L93 Difference]: Finished difference Result 857 states and 858 transitions. [2018-10-10 15:32:11,911 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 113 states. [2018-10-10 15:32:11,912 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 572 [2018-10-10 15:32:11,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:32:11,916 INFO L225 Difference]: With dead ends: 857 [2018-10-10 15:32:11,916 INFO L226 Difference]: Without dead ends: 603 [2018-10-10 15:32:11,917 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 167 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7671 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=4293, Invalid=24099, Unknown=0, NotChecked=0, Total=28392 [2018-10-10 15:32:11,918 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 603 states. [2018-10-10 15:32:11,922 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 603 to 589. [2018-10-10 15:32:11,922 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 589 states. [2018-10-10 15:32:11,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 589 states to 589 states and 590 transitions. [2018-10-10 15:32:11,923 INFO L78 Accepts]: Start accepts. Automaton has 589 states and 590 transitions. Word has length 572 [2018-10-10 15:32:11,924 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:32:11,924 INFO L481 AbstractCegarLoop]: Abstraction has 589 states and 590 transitions. [2018-10-10 15:32:11,924 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-10 15:32:11,924 INFO L276 IsEmpty]: Start isEmpty. Operand 589 states and 590 transitions. [2018-10-10 15:32:11,927 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 589 [2018-10-10 15:32:11,928 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:32:11,928 INFO L375 BasicCegarLoop]: trace histogram [19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:32:11,928 INFO L424 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:32:11,929 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:32:11,929 INFO L82 PathProgramCache]: Analyzing trace with hash 1417188004, now seen corresponding path program 36 times [2018-10-10 15:32:11,929 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:32:11,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:32:14,910 INFO L134 CoverageAnalysis]: Checked inductivity of 4969 backedges. 2312 proven. 2657 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:32:14,910 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:32:14,911 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-10 15:32:14,911 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-10 15:32:14,912 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-10 15:32:14,912 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=708, Invalid=5772, Unknown=0, NotChecked=0, Total=6480 [2018-10-10 15:32:14,912 INFO L87 Difference]: Start difference. First operand 589 states and 590 transitions. Second operand 81 states. [2018-10-10 15:32:28,136 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:32:28,136 INFO L93 Difference]: Finished difference Result 623 states and 624 transitions. [2018-10-10 15:32:28,136 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 133 states. [2018-10-10 15:32:28,136 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 588 [2018-10-10 15:32:28,137 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:32:28,138 INFO L225 Difference]: With dead ends: 623 [2018-10-10 15:32:28,138 INFO L226 Difference]: Without dead ends: 623 [2018-10-10 15:32:28,139 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 191 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9935 ImplicationChecksByTransitivity, 10.3s TimeCoverageRelationStatistics Valid=6323, Invalid=30733, Unknown=0, NotChecked=0, Total=37056 [2018-10-10 15:32:28,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 623 states. [2018-10-10 15:32:28,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 623 to 603. [2018-10-10 15:32:28,143 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 603 states. [2018-10-10 15:32:28,144 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 603 states to 603 states and 604 transitions. [2018-10-10 15:32:28,144 INFO L78 Accepts]: Start accepts. Automaton has 603 states and 604 transitions. Word has length 588 [2018-10-10 15:32:28,144 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:32:28,144 INFO L481 AbstractCegarLoop]: Abstraction has 603 states and 604 transitions. [2018-10-10 15:32:28,144 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-10 15:32:28,145 INFO L276 IsEmpty]: Start isEmpty. Operand 603 states and 604 transitions. [2018-10-10 15:32:28,147 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 603 [2018-10-10 15:32:28,147 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:32:28,148 INFO L375 BasicCegarLoop]: trace histogram [20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:32:28,148 INFO L424 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:32:28,148 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:32:28,148 INFO L82 PathProgramCache]: Analyzing trace with hash 1035400024, now seen corresponding path program 37 times [2018-10-10 15:32:28,149 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:32:28,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:32:30,943 INFO L134 CoverageAnalysis]: Checked inductivity of 5225 backedges. 2235 proven. 2990 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:32:30,943 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:32:30,943 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-10 15:32:30,944 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-10 15:32:30,944 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-10 15:32:30,944 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=846, Invalid=5634, Unknown=0, NotChecked=0, Total=6480 [2018-10-10 15:32:30,945 INFO L87 Difference]: Start difference. First operand 603 states and 604 transitions. Second operand 81 states. [2018-10-10 15:32:36,484 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:32:36,484 INFO L93 Difference]: Finished difference Result 901 states and 902 transitions. [2018-10-10 15:32:36,485 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 119 states. [2018-10-10 15:32:36,485 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 602 [2018-10-10 15:32:36,485 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:32:36,487 INFO L225 Difference]: With dead ends: 901 [2018-10-10 15:32:36,487 INFO L226 Difference]: Without dead ends: 633 [2018-10-10 15:32:36,488 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 176 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8544 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=4758, Invalid=26748, Unknown=0, NotChecked=0, Total=31506 [2018-10-10 15:32:36,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 633 states. [2018-10-10 15:32:36,492 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 633 to 619. [2018-10-10 15:32:36,492 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 619 states. [2018-10-10 15:32:36,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 619 states to 619 states and 620 transitions. [2018-10-10 15:32:36,493 INFO L78 Accepts]: Start accepts. Automaton has 619 states and 620 transitions. Word has length 602 [2018-10-10 15:32:36,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:32:36,493 INFO L481 AbstractCegarLoop]: Abstraction has 619 states and 620 transitions. [2018-10-10 15:32:36,493 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-10 15:32:36,493 INFO L276 IsEmpty]: Start isEmpty. Operand 619 states and 620 transitions. [2018-10-10 15:32:36,497 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 619 [2018-10-10 15:32:36,497 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:32:36,497 INFO L375 BasicCegarLoop]: trace histogram [20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:32:36,498 INFO L424 AbstractCegarLoop]: === Iteration 41 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:32:36,498 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:32:36,498 INFO L82 PathProgramCache]: Analyzing trace with hash 320117328, now seen corresponding path program 38 times [2018-10-10 15:32:36,499 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:32:36,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:32:40,168 INFO L134 CoverageAnalysis]: Checked inductivity of 5530 backedges. 2592 proven. 2938 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:32:40,168 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:32:40,168 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-10 15:32:40,169 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-10 15:32:40,169 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-10 15:32:40,169 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=751, Invalid=6389, Unknown=0, NotChecked=0, Total=7140 [2018-10-10 15:32:40,169 INFO L87 Difference]: Start difference. First operand 619 states and 620 transitions. Second operand 85 states. [2018-10-10 15:32:51,255 WARN L178 SmtUtils]: Spent 102.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 43 [2018-10-10 15:32:55,138 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:32:55,138 INFO L93 Difference]: Finished difference Result 653 states and 654 transitions. [2018-10-10 15:32:55,138 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 139 states. [2018-10-10 15:32:55,138 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 618 [2018-10-10 15:32:55,139 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:32:55,140 INFO L225 Difference]: With dead ends: 653 [2018-10-10 15:32:55,141 INFO L226 Difference]: Without dead ends: 653 [2018-10-10 15:32:55,142 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 206 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 200 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10877 ImplicationChecksByTransitivity, 12.0s TimeCoverageRelationStatistics Valid=6749, Invalid=33853, Unknown=0, NotChecked=0, Total=40602 [2018-10-10 15:32:55,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 653 states. [2018-10-10 15:32:55,146 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 653 to 633. [2018-10-10 15:32:55,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 633 states. [2018-10-10 15:32:55,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 633 states to 633 states and 634 transitions. [2018-10-10 15:32:55,147 INFO L78 Accepts]: Start accepts. Automaton has 633 states and 634 transitions. Word has length 618 [2018-10-10 15:32:55,148 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:32:55,148 INFO L481 AbstractCegarLoop]: Abstraction has 633 states and 634 transitions. [2018-10-10 15:32:55,148 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-10 15:32:55,148 INFO L276 IsEmpty]: Start isEmpty. Operand 633 states and 634 transitions. [2018-10-10 15:32:55,151 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 633 [2018-10-10 15:32:55,151 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:32:55,151 INFO L375 BasicCegarLoop]: trace histogram [21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:32:55,151 INFO L424 AbstractCegarLoop]: === Iteration 42 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:32:55,152 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:32:55,152 INFO L82 PathProgramCache]: Analyzing trace with hash -1700389372, now seen corresponding path program 39 times [2018-10-10 15:32:55,152 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:32:55,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:32:57,803 INFO L134 CoverageAnalysis]: Checked inductivity of 5800 backedges. 2492 proven. 3308 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:32:57,804 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:32:57,804 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-10 15:32:57,804 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-10 15:32:57,805 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-10 15:32:57,805 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=930, Invalid=6210, Unknown=0, NotChecked=0, Total=7140 [2018-10-10 15:32:57,805 INFO L87 Difference]: Start difference. First operand 633 states and 634 transitions. Second operand 85 states. [2018-10-10 15:33:03,885 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:33:03,886 INFO L93 Difference]: Finished difference Result 945 states and 946 transitions. [2018-10-10 15:33:03,886 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 125 states. [2018-10-10 15:33:03,886 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 632 [2018-10-10 15:33:03,887 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:33:03,888 INFO L225 Difference]: With dead ends: 945 [2018-10-10 15:33:03,888 INFO L226 Difference]: Without dead ends: 663 [2018-10-10 15:33:03,889 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9464 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=5247, Invalid=29535, Unknown=0, NotChecked=0, Total=34782 [2018-10-10 15:33:03,890 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 663 states. [2018-10-10 15:33:03,893 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 663 to 649. [2018-10-10 15:33:03,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 649 states. [2018-10-10 15:33:03,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 649 states to 649 states and 650 transitions. [2018-10-10 15:33:03,894 INFO L78 Accepts]: Start accepts. Automaton has 649 states and 650 transitions. Word has length 632 [2018-10-10 15:33:03,895 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:33:03,895 INFO L481 AbstractCegarLoop]: Abstraction has 649 states and 650 transitions. [2018-10-10 15:33:03,895 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-10 15:33:03,895 INFO L276 IsEmpty]: Start isEmpty. Operand 649 states and 650 transitions. [2018-10-10 15:33:03,899 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 649 [2018-10-10 15:33:03,899 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:33:03,899 INFO L375 BasicCegarLoop]: trace histogram [21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:33:03,899 INFO L424 AbstractCegarLoop]: === Iteration 43 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:33:03,900 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:33:03,900 INFO L82 PathProgramCache]: Analyzing trace with hash -1566620932, now seen corresponding path program 40 times [2018-10-10 15:33:03,900 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:33:03,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:33:07,427 INFO L134 CoverageAnalysis]: Checked inductivity of 6121 backedges. 2888 proven. 3233 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:33:07,427 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:33:07,428 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-10 15:33:07,428 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-10 15:33:07,429 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-10 15:33:07,429 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=684, Invalid=7148, Unknown=0, NotChecked=0, Total=7832 [2018-10-10 15:33:07,429 INFO L87 Difference]: Start difference. First operand 649 states and 650 transitions. Second operand 89 states. [2018-10-10 15:33:19,295 WARN L178 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-10 15:33:19,500 WARN L178 SmtUtils]: Spent 108.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-10 15:33:19,963 WARN L178 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-10 15:33:20,171 WARN L178 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-10 15:33:20,653 WARN L178 SmtUtils]: Spent 119.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-10 15:33:20,849 WARN L178 SmtUtils]: Spent 112.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-10 15:33:21,296 WARN L178 SmtUtils]: Spent 115.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-10 15:33:21,492 WARN L178 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 43 [2018-10-10 15:33:21,952 WARN L178 SmtUtils]: Spent 113.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 42 [2018-10-10 15:33:22,144 WARN L178 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 42 [2018-10-10 15:33:25,697 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:33:25,697 INFO L93 Difference]: Finished difference Result 683 states and 684 transitions. [2018-10-10 15:33:25,698 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 141 states. [2018-10-10 15:33:25,698 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 648 [2018-10-10 15:33:25,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:33:25,700 INFO L225 Difference]: With dead ends: 683 [2018-10-10 15:33:25,700 INFO L226 Difference]: Without dead ends: 683 [2018-10-10 15:33:25,702 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 205 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11140 ImplicationChecksByTransitivity, 13.0s TimeCoverageRelationStatistics Valid=6198, Invalid=36444, Unknown=0, NotChecked=0, Total=42642 [2018-10-10 15:33:25,702 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 683 states. [2018-10-10 15:33:25,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 683 to 663. [2018-10-10 15:33:25,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 663 states. [2018-10-10 15:33:25,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 663 states to 663 states and 664 transitions. [2018-10-10 15:33:25,707 INFO L78 Accepts]: Start accepts. Automaton has 663 states and 664 transitions. Word has length 648 [2018-10-10 15:33:25,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:33:25,708 INFO L481 AbstractCegarLoop]: Abstraction has 663 states and 664 transitions. [2018-10-10 15:33:25,708 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-10 15:33:25,708 INFO L276 IsEmpty]: Start isEmpty. Operand 663 states and 664 transitions. [2018-10-10 15:33:25,712 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 663 [2018-10-10 15:33:25,712 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:33:25,712 INFO L375 BasicCegarLoop]: trace histogram [22, 22, 22, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:33:25,713 INFO L424 AbstractCegarLoop]: === Iteration 44 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:33:25,713 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:33:25,713 INFO L82 PathProgramCache]: Analyzing trace with hash -1915344464, now seen corresponding path program 41 times [2018-10-10 15:33:25,713 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:33:25,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:33:28,460 INFO L134 CoverageAnalysis]: Checked inductivity of 6405 backedges. 2763 proven. 3642 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:33:28,460 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:33:28,460 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-10 15:33:28,461 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-10 15:33:28,461 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-10 15:33:28,462 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1018, Invalid=6814, Unknown=0, NotChecked=0, Total=7832 [2018-10-10 15:33:28,462 INFO L87 Difference]: Start difference. First operand 663 states and 664 transitions. Second operand 89 states. [2018-10-10 15:33:34,798 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:33:34,799 INFO L93 Difference]: Finished difference Result 989 states and 990 transitions. [2018-10-10 15:33:34,799 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-10-10 15:33:34,799 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 662 [2018-10-10 15:33:34,800 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:33:34,802 INFO L225 Difference]: With dead ends: 989 [2018-10-10 15:33:34,802 INFO L226 Difference]: Without dead ends: 693 [2018-10-10 15:33:34,804 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 194 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10431 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=5760, Invalid=32460, Unknown=0, NotChecked=0, Total=38220 [2018-10-10 15:33:34,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 693 states. [2018-10-10 15:33:34,808 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 693 to 679. [2018-10-10 15:33:34,808 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 679 states. [2018-10-10 15:33:34,809 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 679 states to 679 states and 680 transitions. [2018-10-10 15:33:34,809 INFO L78 Accepts]: Start accepts. Automaton has 679 states and 680 transitions. Word has length 662 [2018-10-10 15:33:34,809 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:33:34,809 INFO L481 AbstractCegarLoop]: Abstraction has 679 states and 680 transitions. [2018-10-10 15:33:34,809 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-10 15:33:34,809 INFO L276 IsEmpty]: Start isEmpty. Operand 679 states and 680 transitions. [2018-10-10 15:33:34,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 679 [2018-10-10 15:33:34,812 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:33:34,813 INFO L375 BasicCegarLoop]: trace histogram [22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:33:34,813 INFO L424 AbstractCegarLoop]: === Iteration 45 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:33:34,813 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:33:34,813 INFO L82 PathProgramCache]: Analyzing trace with hash 431639720, now seen corresponding path program 42 times [2018-10-10 15:33:34,814 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:33:34,855 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:33:38,551 INFO L134 CoverageAnalysis]: Checked inductivity of 6742 backedges. 3200 proven. 3542 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:33:38,552 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:33:38,552 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-10 15:33:38,552 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-10 15:33:38,553 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-10 15:33:38,553 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=987, Invalid=7569, Unknown=0, NotChecked=0, Total=8556 [2018-10-10 15:33:38,553 INFO L87 Difference]: Start difference. First operand 679 states and 680 transitions. Second operand 93 states. [2018-10-10 15:33:50,805 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:33:50,805 INFO L93 Difference]: Finished difference Result 713 states and 714 transitions. [2018-10-10 15:33:50,805 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 156 states. [2018-10-10 15:33:50,805 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 678 [2018-10-10 15:33:50,806 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:33:50,808 INFO L225 Difference]: With dead ends: 713 [2018-10-10 15:33:50,808 INFO L226 Difference]: Without dead ends: 713 [2018-10-10 15:33:50,809 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 223 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13786 ImplicationChecksByTransitivity, 12.5s TimeCoverageRelationStatistics Valid=8814, Invalid=41586, Unknown=0, NotChecked=0, Total=50400 [2018-10-10 15:33:50,810 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 713 states. [2018-10-10 15:33:50,813 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 713 to 693. [2018-10-10 15:33:50,813 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 693 states. [2018-10-10 15:33:50,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 693 states to 693 states and 694 transitions. [2018-10-10 15:33:50,814 INFO L78 Accepts]: Start accepts. Automaton has 693 states and 694 transitions. Word has length 678 [2018-10-10 15:33:50,815 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:33:50,815 INFO L481 AbstractCegarLoop]: Abstraction has 693 states and 694 transitions. [2018-10-10 15:33:50,815 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-10 15:33:50,815 INFO L276 IsEmpty]: Start isEmpty. Operand 693 states and 694 transitions. [2018-10-10 15:33:50,818 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 693 [2018-10-10 15:33:50,818 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:33:50,819 INFO L375 BasicCegarLoop]: trace histogram [23, 23, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:33:50,819 INFO L424 AbstractCegarLoop]: === Iteration 46 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:33:50,819 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:33:50,819 INFO L82 PathProgramCache]: Analyzing trace with hash 265868892, now seen corresponding path program 43 times [2018-10-10 15:33:50,820 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:33:50,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:33:53,600 INFO L134 CoverageAnalysis]: Checked inductivity of 7040 backedges. 3048 proven. 3992 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:33:53,601 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:33:53,601 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-10 15:33:53,602 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-10 15:33:53,602 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-10 15:33:53,602 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1110, Invalid=7446, Unknown=0, NotChecked=0, Total=8556 [2018-10-10 15:33:53,602 INFO L87 Difference]: Start difference. First operand 693 states and 694 transitions. Second operand 93 states. [2018-10-10 15:34:00,813 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:34:00,814 INFO L93 Difference]: Finished difference Result 1033 states and 1034 transitions. [2018-10-10 15:34:00,814 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 137 states. [2018-10-10 15:34:00,814 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 692 [2018-10-10 15:34:00,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:34:00,817 INFO L225 Difference]: With dead ends: 1033 [2018-10-10 15:34:00,817 INFO L226 Difference]: Without dead ends: 723 [2018-10-10 15:34:00,818 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11445 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=6297, Invalid=35523, Unknown=0, NotChecked=0, Total=41820 [2018-10-10 15:34:00,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 723 states. [2018-10-10 15:34:00,822 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 723 to 709. [2018-10-10 15:34:00,822 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-10-10 15:34:00,823 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 710 transitions. [2018-10-10 15:34:00,823 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 710 transitions. Word has length 692 [2018-10-10 15:34:00,824 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:34:00,824 INFO L481 AbstractCegarLoop]: Abstraction has 709 states and 710 transitions. [2018-10-10 15:34:00,824 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-10 15:34:00,824 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 710 transitions. [2018-10-10 15:34:00,827 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 709 [2018-10-10 15:34:00,827 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:34:00,827 INFO L375 BasicCegarLoop]: trace histogram [23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:34:00,828 INFO L424 AbstractCegarLoop]: === Iteration 47 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:34:00,828 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:34:00,828 INFO L82 PathProgramCache]: Analyzing trace with hash -522750124, now seen corresponding path program 44 times [2018-10-10 15:34:00,828 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:34:00,869 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:34:04,685 INFO L134 CoverageAnalysis]: Checked inductivity of 7393 backedges. 3528 proven. 3865 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:34:04,685 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:34:04,685 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-10 15:34:04,686 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-10 15:34:04,686 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-10 15:34:04,686 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1036, Invalid=8276, Unknown=0, NotChecked=0, Total=9312 [2018-10-10 15:34:04,686 INFO L87 Difference]: Start difference. First operand 709 states and 710 transitions. Second operand 97 states. [2018-10-10 15:34:23,220 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:34:23,220 INFO L93 Difference]: Finished difference Result 743 states and 744 transitions. [2018-10-10 15:34:23,222 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-10 15:34:23,222 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 708 [2018-10-10 15:34:23,223 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:34:23,225 INFO L225 Difference]: With dead ends: 743 [2018-10-10 15:34:23,225 INFO L226 Difference]: Without dead ends: 743 [2018-10-10 15:34:23,227 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 231 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14741 ImplicationChecksByTransitivity, 13.9s TimeCoverageRelationStatistics Valid=9261, Invalid=44795, Unknown=0, NotChecked=0, Total=54056 [2018-10-10 15:34:23,227 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 743 states. [2018-10-10 15:34:23,232 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 743 to 723. [2018-10-10 15:34:23,232 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 723 states. [2018-10-10 15:34:23,234 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 723 states to 723 states and 724 transitions. [2018-10-10 15:34:23,234 INFO L78 Accepts]: Start accepts. Automaton has 723 states and 724 transitions. Word has length 708 [2018-10-10 15:34:23,234 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:34:23,234 INFO L481 AbstractCegarLoop]: Abstraction has 723 states and 724 transitions. [2018-10-10 15:34:23,235 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-10 15:34:23,235 INFO L276 IsEmpty]: Start isEmpty. Operand 723 states and 724 transitions. [2018-10-10 15:34:23,238 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 723 [2018-10-10 15:34:23,238 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:34:23,238 INFO L375 BasicCegarLoop]: trace histogram [24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:34:23,239 INFO L424 AbstractCegarLoop]: === Iteration 48 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:34:23,239 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:34:23,239 INFO L82 PathProgramCache]: Analyzing trace with hash -15735800, now seen corresponding path program 45 times [2018-10-10 15:34:23,239 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:34:23,279 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:34:26,117 INFO L134 CoverageAnalysis]: Checked inductivity of 7705 backedges. 3347 proven. 4358 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:34:26,117 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:34:26,117 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-10 15:34:26,118 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-10 15:34:26,118 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-10 15:34:26,118 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1206, Invalid=8106, Unknown=0, NotChecked=0, Total=9312 [2018-10-10 15:34:26,118 INFO L87 Difference]: Start difference. First operand 723 states and 724 transitions. Second operand 97 states. [2018-10-10 15:34:34,280 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:34:34,281 INFO L93 Difference]: Finished difference Result 1077 states and 1078 transitions. [2018-10-10 15:34:34,281 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 143 states. [2018-10-10 15:34:34,281 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 722 [2018-10-10 15:34:34,282 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:34:34,284 INFO L225 Difference]: With dead ends: 1077 [2018-10-10 15:34:34,285 INFO L226 Difference]: Without dead ends: 753 [2018-10-10 15:34:34,286 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 214 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 212 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12506 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=6858, Invalid=38724, Unknown=0, NotChecked=0, Total=45582 [2018-10-10 15:34:34,287 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 753 states. [2018-10-10 15:34:34,291 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 753 to 739. [2018-10-10 15:34:34,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-10-10 15:34:34,292 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 740 transitions. [2018-10-10 15:34:34,292 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 740 transitions. Word has length 722 [2018-10-10 15:34:34,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:34:34,292 INFO L481 AbstractCegarLoop]: Abstraction has 739 states and 740 transitions. [2018-10-10 15:34:34,292 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-10 15:34:34,292 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 740 transitions. [2018-10-10 15:34:34,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 739 [2018-10-10 15:34:34,296 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:34:34,296 INFO L375 BasicCegarLoop]: trace histogram [24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:34:34,296 INFO L424 AbstractCegarLoop]: === Iteration 49 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:34:34,297 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:34:34,297 INFO L82 PathProgramCache]: Analyzing trace with hash 1043890944, now seen corresponding path program 46 times [2018-10-10 15:34:34,297 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:34:34,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:34:38,973 INFO L134 CoverageAnalysis]: Checked inductivity of 8074 backedges. 3872 proven. 4202 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:34:38,973 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:34:38,973 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-10 15:34:38,974 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-10 15:34:38,974 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-10 15:34:38,974 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1087, Invalid=9013, Unknown=0, NotChecked=0, Total=10100 [2018-10-10 15:34:38,974 INFO L87 Difference]: Start difference. First operand 739 states and 740 transitions. Second operand 101 states. [2018-10-10 15:34:54,247 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:34:54,247 INFO L93 Difference]: Finished difference Result 773 states and 774 transitions. [2018-10-10 15:34:54,248 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-10 15:34:54,248 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 738 [2018-10-10 15:34:54,248 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:34:54,250 INFO L225 Difference]: With dead ends: 773 [2018-10-10 15:34:54,250 INFO L226 Difference]: Without dead ends: 773 [2018-10-10 15:34:54,253 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 240 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15883 ImplicationChecksByTransitivity, 15.5s TimeCoverageRelationStatistics Valid=9775, Invalid=48547, Unknown=0, NotChecked=0, Total=58322 [2018-10-10 15:34:54,253 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 773 states. [2018-10-10 15:34:54,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 773 to 753. [2018-10-10 15:34:54,258 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 753 states. [2018-10-10 15:34:54,259 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 753 states to 753 states and 754 transitions. [2018-10-10 15:34:54,260 INFO L78 Accepts]: Start accepts. Automaton has 753 states and 754 transitions. Word has length 738 [2018-10-10 15:34:54,260 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:34:54,260 INFO L481 AbstractCegarLoop]: Abstraction has 753 states and 754 transitions. [2018-10-10 15:34:54,260 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-10 15:34:54,261 INFO L276 IsEmpty]: Start isEmpty. Operand 753 states and 754 transitions. [2018-10-10 15:34:54,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 753 [2018-10-10 15:34:54,265 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:34:54,265 INFO L375 BasicCegarLoop]: trace histogram [25, 25, 25, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:34:54,265 INFO L424 AbstractCegarLoop]: === Iteration 50 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:34:54,265 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:34:54,266 INFO L82 PathProgramCache]: Analyzing trace with hash -1414720844, now seen corresponding path program 47 times [2018-10-10 15:34:54,266 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:34:54,300 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:34:57,413 INFO L134 CoverageAnalysis]: Checked inductivity of 8400 backedges. 3660 proven. 4740 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:34:57,413 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:34:57,413 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-10 15:34:57,414 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-10 15:34:57,414 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-10 15:34:57,414 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1306, Invalid=8794, Unknown=0, NotChecked=0, Total=10100 [2018-10-10 15:34:57,414 INFO L87 Difference]: Start difference. First operand 753 states and 754 transitions. Second operand 101 states. [2018-10-10 15:35:05,819 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:35:05,819 INFO L93 Difference]: Finished difference Result 1121 states and 1122 transitions. [2018-10-10 15:35:05,820 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 149 states. [2018-10-10 15:35:05,820 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 752 [2018-10-10 15:35:05,821 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:35:05,823 INFO L225 Difference]: With dead ends: 1121 [2018-10-10 15:35:05,823 INFO L226 Difference]: Without dead ends: 783 [2018-10-10 15:35:05,825 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 221 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13614 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=7443, Invalid=42063, Unknown=0, NotChecked=0, Total=49506 [2018-10-10 15:35:05,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 783 states. [2018-10-10 15:35:05,831 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 783 to 769. [2018-10-10 15:35:05,832 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 769 states. [2018-10-10 15:35:05,833 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 769 states to 769 states and 770 transitions. [2018-10-10 15:35:05,833 INFO L78 Accepts]: Start accepts. Automaton has 769 states and 770 transitions. Word has length 752 [2018-10-10 15:35:05,833 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:35:05,834 INFO L481 AbstractCegarLoop]: Abstraction has 769 states and 770 transitions. [2018-10-10 15:35:05,834 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-10 15:35:05,834 INFO L276 IsEmpty]: Start isEmpty. Operand 769 states and 770 transitions. [2018-10-10 15:35:05,838 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 769 [2018-10-10 15:35:05,839 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:35:05,839 INFO L375 BasicCegarLoop]: trace histogram [25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:35:05,839 INFO L424 AbstractCegarLoop]: === Iteration 51 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:35:05,840 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:35:05,840 INFO L82 PathProgramCache]: Analyzing trace with hash -504418388, now seen corresponding path program 48 times [2018-10-10 15:35:05,840 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:35:05,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:35:10,457 INFO L134 CoverageAnalysis]: Checked inductivity of 8785 backedges. 4232 proven. 4553 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:35:10,457 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:35:10,457 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-10 15:35:10,458 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-10 15:35:10,458 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-10 15:35:10,458 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1140, Invalid=9780, Unknown=0, NotChecked=0, Total=10920 [2018-10-10 15:35:10,459 INFO L87 Difference]: Start difference. First operand 769 states and 770 transitions. Second operand 105 states. [2018-10-10 15:35:32,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:35:32,439 INFO L93 Difference]: Finished difference Result 803 states and 804 transitions. [2018-10-10 15:35:32,439 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 173 states. [2018-10-10 15:35:32,439 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 768 [2018-10-10 15:35:32,440 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:35:32,442 INFO L225 Difference]: With dead ends: 803 [2018-10-10 15:35:32,442 INFO L226 Difference]: Without dead ends: 803 [2018-10-10 15:35:32,444 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 255 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 249 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17066 ImplicationChecksByTransitivity, 16.7s TimeCoverageRelationStatistics Valid=10304, Invalid=52446, Unknown=0, NotChecked=0, Total=62750 [2018-10-10 15:35:32,444 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 803 states. [2018-10-10 15:35:32,450 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 803 to 783. [2018-10-10 15:35:32,450 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 783 states. [2018-10-10 15:35:32,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 783 states to 783 states and 784 transitions. [2018-10-10 15:35:32,451 INFO L78 Accepts]: Start accepts. Automaton has 783 states and 784 transitions. Word has length 768 [2018-10-10 15:35:32,452 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:35:32,452 INFO L481 AbstractCegarLoop]: Abstraction has 783 states and 784 transitions. [2018-10-10 15:35:32,452 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-10 15:35:32,452 INFO L276 IsEmpty]: Start isEmpty. Operand 783 states and 784 transitions. [2018-10-10 15:35:32,458 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 783 [2018-10-10 15:35:32,458 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:35:32,458 INFO L375 BasicCegarLoop]: trace histogram [26, 26, 26, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:35:32,459 INFO L424 AbstractCegarLoop]: === Iteration 52 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:35:32,459 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:35:32,459 INFO L82 PathProgramCache]: Analyzing trace with hash 1672618592, now seen corresponding path program 49 times [2018-10-10 15:35:32,460 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:35:32,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:35:36,099 INFO L134 CoverageAnalysis]: Checked inductivity of 9125 backedges. 3987 proven. 5138 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:35:36,100 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:35:36,100 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-10 15:35:36,100 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-10 15:35:36,101 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-10 15:35:36,101 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1410, Invalid=9510, Unknown=0, NotChecked=0, Total=10920 [2018-10-10 15:35:36,101 INFO L87 Difference]: Start difference. First operand 783 states and 784 transitions. Second operand 105 states. [2018-10-10 15:35:45,440 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:35:45,441 INFO L93 Difference]: Finished difference Result 1165 states and 1166 transitions. [2018-10-10 15:35:45,441 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 155 states. [2018-10-10 15:35:45,441 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 782 [2018-10-10 15:35:45,442 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:35:45,445 INFO L225 Difference]: With dead ends: 1165 [2018-10-10 15:35:45,445 INFO L226 Difference]: Without dead ends: 813 [2018-10-10 15:35:45,446 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 232 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 230 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14769 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=8052, Invalid=45540, Unknown=0, NotChecked=0, Total=53592 [2018-10-10 15:35:45,446 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 813 states. [2018-10-10 15:35:45,450 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 813 to 799. [2018-10-10 15:35:45,451 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 799 states. [2018-10-10 15:35:45,451 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 799 states to 799 states and 800 transitions. [2018-10-10 15:35:45,451 INFO L78 Accepts]: Start accepts. Automaton has 799 states and 800 transitions. Word has length 782 [2018-10-10 15:35:45,452 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:35:45,452 INFO L481 AbstractCegarLoop]: Abstraction has 799 states and 800 transitions. [2018-10-10 15:35:45,452 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-10 15:35:45,452 INFO L276 IsEmpty]: Start isEmpty. Operand 799 states and 800 transitions. [2018-10-10 15:35:45,456 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 799 [2018-10-10 15:35:45,456 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:35:45,456 INFO L375 BasicCegarLoop]: trace histogram [26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:35:45,456 INFO L424 AbstractCegarLoop]: === Iteration 53 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:35:45,456 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:35:45,457 INFO L82 PathProgramCache]: Analyzing trace with hash 1910324568, now seen corresponding path program 50 times [2018-10-10 15:35:45,457 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:35:45,505 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:35:50,239 INFO L134 CoverageAnalysis]: Checked inductivity of 9526 backedges. 4608 proven. 4918 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:35:50,239 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:35:50,239 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-10 15:35:50,240 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-10 15:35:50,240 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-10 15:35:50,240 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1371, Invalid=10401, Unknown=0, NotChecked=0, Total=11772 [2018-10-10 15:35:50,241 INFO L87 Difference]: Start difference. First operand 799 states and 800 transitions. Second operand 109 states. [2018-10-10 15:36:08,242 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:36:08,243 INFO L93 Difference]: Finished difference Result 833 states and 834 transitions. [2018-10-10 15:36:08,243 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 184 states. [2018-10-10 15:36:08,243 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 798 [2018-10-10 15:36:08,244 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:36:08,245 INFO L225 Difference]: With dead ends: 833 [2018-10-10 15:36:08,246 INFO L226 Difference]: Without dead ends: 833 [2018-10-10 15:36:08,247 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 269 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 263 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19364 ImplicationChecksByTransitivity, 16.6s TimeCoverageRelationStatistics Valid=12232, Invalid=57728, Unknown=0, NotChecked=0, Total=69960 [2018-10-10 15:36:08,247 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 833 states. [2018-10-10 15:36:08,252 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 833 to 813. [2018-10-10 15:36:08,252 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 813 states. [2018-10-10 15:36:08,253 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 813 states to 813 states and 814 transitions. [2018-10-10 15:36:08,253 INFO L78 Accepts]: Start accepts. Automaton has 813 states and 814 transitions. Word has length 798 [2018-10-10 15:36:08,253 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:36:08,253 INFO L481 AbstractCegarLoop]: Abstraction has 813 states and 814 transitions. [2018-10-10 15:36:08,253 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-10 15:36:08,253 INFO L276 IsEmpty]: Start isEmpty. Operand 813 states and 814 transitions. [2018-10-10 15:36:08,257 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 813 [2018-10-10 15:36:08,258 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:36:08,258 INFO L375 BasicCegarLoop]: trace histogram [27, 27, 27, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:36:08,258 INFO L424 AbstractCegarLoop]: === Iteration 54 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:36:08,258 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:36:08,259 INFO L82 PathProgramCache]: Analyzing trace with hash -17771764, now seen corresponding path program 51 times [2018-10-10 15:36:08,259 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:36:08,298 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:36:12,253 INFO L134 CoverageAnalysis]: Checked inductivity of 9880 backedges. 4328 proven. 5552 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:36:12,254 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:36:12,254 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-10 15:36:12,254 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-10 15:36:12,255 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-10 15:36:12,255 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1518, Invalid=10254, Unknown=0, NotChecked=0, Total=11772 [2018-10-10 15:36:12,255 INFO L87 Difference]: Start difference. First operand 813 states and 814 transitions. Second operand 109 states. [2018-10-10 15:36:22,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:36:22,300 INFO L93 Difference]: Finished difference Result 1209 states and 1210 transitions. [2018-10-10 15:36:22,300 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-10 15:36:22,300 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 812 [2018-10-10 15:36:22,301 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:36:22,303 INFO L225 Difference]: With dead ends: 1209 [2018-10-10 15:36:22,303 INFO L226 Difference]: Without dead ends: 843 [2018-10-10 15:36:22,305 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 239 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15971 ImplicationChecksByTransitivity, 8.4s TimeCoverageRelationStatistics Valid=8685, Invalid=49155, Unknown=0, NotChecked=0, Total=57840 [2018-10-10 15:36:22,306 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 843 states. [2018-10-10 15:36:22,310 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 843 to 829. [2018-10-10 15:36:22,310 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 829 states. [2018-10-10 15:36:22,311 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 829 states to 829 states and 830 transitions. [2018-10-10 15:36:22,311 INFO L78 Accepts]: Start accepts. Automaton has 829 states and 830 transitions. Word has length 812 [2018-10-10 15:36:22,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:36:22,311 INFO L481 AbstractCegarLoop]: Abstraction has 829 states and 830 transitions. [2018-10-10 15:36:22,311 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-10 15:36:22,311 INFO L276 IsEmpty]: Start isEmpty. Operand 829 states and 830 transitions. [2018-10-10 15:36:22,316 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 829 [2018-10-10 15:36:22,316 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:36:22,316 INFO L375 BasicCegarLoop]: trace histogram [27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:36:22,316 INFO L424 AbstractCegarLoop]: === Iteration 55 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:36:22,316 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:36:22,317 INFO L82 PathProgramCache]: Analyzing trace with hash 364145668, now seen corresponding path program 52 times [2018-10-10 15:36:22,317 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:36:22,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:36:27,404 INFO L134 CoverageAnalysis]: Checked inductivity of 10297 backedges. 5000 proven. 5297 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:36:27,404 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:36:27,404 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-10 15:36:27,405 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-10 15:36:27,405 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-10 15:36:27,405 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1428, Invalid=11228, Unknown=0, NotChecked=0, Total=12656 [2018-10-10 15:36:27,405 INFO L87 Difference]: Start difference. First operand 829 states and 830 transitions. Second operand 113 states. [2018-10-10 15:36:51,545 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:36:51,545 INFO L93 Difference]: Finished difference Result 863 states and 864 transitions. [2018-10-10 15:36:51,545 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-10-10 15:36:51,545 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 828 [2018-10-10 15:36:51,546 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:36:51,548 INFO L225 Difference]: With dead ends: 863 [2018-10-10 15:36:51,548 INFO L226 Difference]: Without dead ends: 863 [2018-10-10 15:36:51,549 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 277 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 271 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20491 ImplicationChecksByTransitivity, 18.0s TimeCoverageRelationStatistics Valid=12759, Invalid=61497, Unknown=0, NotChecked=0, Total=74256 [2018-10-10 15:36:51,550 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 863 states. [2018-10-10 15:36:51,554 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 863 to 843. [2018-10-10 15:36:51,554 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 843 states. [2018-10-10 15:36:51,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 843 states to 843 states and 844 transitions. [2018-10-10 15:36:51,555 INFO L78 Accepts]: Start accepts. Automaton has 843 states and 844 transitions. Word has length 828 [2018-10-10 15:36:51,555 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:36:51,556 INFO L481 AbstractCegarLoop]: Abstraction has 843 states and 844 transitions. [2018-10-10 15:36:51,556 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-10 15:36:51,556 INFO L276 IsEmpty]: Start isEmpty. Operand 843 states and 844 transitions. [2018-10-10 15:36:51,560 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 843 [2018-10-10 15:36:51,560 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:36:51,560 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 28, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:36:51,561 INFO L424 AbstractCegarLoop]: === Iteration 56 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:36:51,561 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:36:51,561 INFO L82 PathProgramCache]: Analyzing trace with hash 1795876024, now seen corresponding path program 53 times [2018-10-10 15:36:51,561 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:36:51,603 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:36:55,391 INFO L134 CoverageAnalysis]: Checked inductivity of 10665 backedges. 4683 proven. 5982 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:36:55,392 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:36:55,392 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-10 15:36:55,393 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-10 15:36:55,393 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-10 15:36:55,393 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1630, Invalid=11026, Unknown=0, NotChecked=0, Total=12656 [2018-10-10 15:36:55,394 INFO L87 Difference]: Start difference. First operand 843 states and 844 transitions. Second operand 113 states. [2018-10-10 15:37:06,232 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-10 15:37:06,232 INFO L93 Difference]: Finished difference Result 1253 states and 1254 transitions. [2018-10-10 15:37:06,232 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-10 15:37:06,232 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 842 [2018-10-10 15:37:06,233 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-10 15:37:06,235 INFO L225 Difference]: With dead ends: 1253 [2018-10-10 15:37:06,235 INFO L226 Difference]: Without dead ends: 873 [2018-10-10 15:37:06,236 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 248 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17220 ImplicationChecksByTransitivity, 8.9s TimeCoverageRelationStatistics Valid=9342, Invalid=52908, Unknown=0, NotChecked=0, Total=62250 [2018-10-10 15:37:06,237 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 873 states. [2018-10-10 15:37:06,241 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 873 to 859. [2018-10-10 15:37:06,241 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 859 states. [2018-10-10 15:37:06,242 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 859 states to 859 states and 860 transitions. [2018-10-10 15:37:06,242 INFO L78 Accepts]: Start accepts. Automaton has 859 states and 860 transitions. Word has length 842 [2018-10-10 15:37:06,242 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-10 15:37:06,242 INFO L481 AbstractCegarLoop]: Abstraction has 859 states and 860 transitions. [2018-10-10 15:37:06,243 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-10 15:37:06,243 INFO L276 IsEmpty]: Start isEmpty. Operand 859 states and 860 transitions. [2018-10-10 15:37:06,247 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 859 [2018-10-10 15:37:06,247 INFO L367 BasicCegarLoop]: Found error trace [2018-10-10 15:37:06,248 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-10 15:37:06,248 INFO L424 AbstractCegarLoop]: === Iteration 57 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-10 15:37:06,248 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-10 15:37:06,248 INFO L82 PathProgramCache]: Analyzing trace with hash 49707952, now seen corresponding path program 54 times [2018-10-10 15:37:06,249 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-10 15:37:06,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-10 15:37:12,235 INFO L134 CoverageAnalysis]: Checked inductivity of 11098 backedges. 5408 proven. 5690 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-10 15:37:12,235 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-10 15:37:12,235 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [117] total 117 [2018-10-10 15:37:12,236 INFO L460 AbstractCegarLoop]: Interpolant automaton has 117 states [2018-10-10 15:37:12,236 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 117 interpolants. [2018-10-10 15:37:12,236 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1487, Invalid=12085, Unknown=0, NotChecked=0, Total=13572 [2018-10-10 15:37:12,237 INFO L87 Difference]: Start difference. First operand 859 states and 860 transitions. Second operand 117 states.