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/ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-093a8c0 [2018-10-14 16:24:39,537 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-14 16:24:39,539 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-14 16:24:39,552 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-14 16:24:39,552 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-14 16:24:39,553 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-14 16:24:39,555 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-14 16:24:39,557 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-14 16:24:39,559 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-14 16:24:39,560 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-14 16:24:39,561 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-14 16:24:39,561 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-14 16:24:39,562 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-14 16:24:39,563 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-14 16:24:39,564 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-14 16:24:39,565 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-14 16:24:39,566 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-14 16:24:39,568 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-14 16:24:39,570 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-14 16:24:39,572 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-14 16:24:39,573 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-14 16:24:39,574 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-14 16:24:39,577 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-14 16:24:39,577 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-14 16:24:39,577 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-14 16:24:39,578 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-14 16:24:39,580 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-14 16:24:39,580 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-14 16:24:39,581 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-14 16:24:39,582 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-14 16:24:39,583 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-14 16:24:39,584 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-14 16:24:39,584 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-14 16:24:39,584 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-14 16:24:39,585 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-14 16:24:39,589 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-14 16:24:39,590 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/heapseparator/heapsep-2018-09-18.epf [2018-10-14 16:24:39,600 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-14 16:24:39,600 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-14 16:24:39,601 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-14 16:24:39,601 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-14 16:24:39,601 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-14 16:24:39,602 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-14 16:24:39,602 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-14 16:24:39,603 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-14 16:24:39,603 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-14 16:24:39,603 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-14 16:24:39,603 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-14 16:24:39,603 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-14 16:24:39,604 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-14 16:24:39,605 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-14 16:24:39,605 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-14 16:24:39,657 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-14 16:24:39,671 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-14 16:24:39,674 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-14 16:24:39,677 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-14 16:24:39,677 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-14 16:24:39,678 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl [2018-10-14 16:24:39,678 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl' [2018-10-14 16:24:39,764 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-14 16:24:39,766 INFO L131 ToolchainWalker]: Walking toolchain with 3 elements. [2018-10-14 16:24:39,767 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-14 16:24:39,767 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-14 16:24:39,767 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-14 16:24:39,796 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:24:39" (1/1) ... [2018-10-14 16:24:39,798 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:24:39" (1/1) ... [2018-10-14 16:24:39,817 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:24:39" (1/1) ... [2018-10-14 16:24:39,819 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:24:39" (1/1) ... [2018-10-14 16:24:39,828 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:24:39" (1/1) ... [2018-10-14 16:24:39,836 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:24:39" (1/1) ... [2018-10-14 16:24:39,838 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:24:39" (1/1) ... [2018-10-14 16:24:39,846 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-14 16:24:39,848 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-14 16:24:39,849 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-14 16:24:39,849 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-14 16:24:39,851 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:24:39" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-10-14 16:24:39,930 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2018-10-14 16:24:39,930 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-14 16:24:39,931 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-14 16:24:40,718 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-14 16:24:40,719 INFO L202 PluginConnector]: Adding new model ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 04:24:40 BoogieIcfgContainer [2018-10-14 16:24:40,719 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-14 16:24:40,720 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-14 16:24:40,720 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-14 16:24:40,723 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-14 16:24:40,723 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:24:39" (1/2) ... [2018-10-14 16:24:40,725 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@478f6a1c and model type ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.10 04:24:40, skipping insertion in model container [2018-10-14 16:24:40,725 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 04:24:40" (2/2) ... [2018-10-14 16:24:40,727 INFO L112 eAbstractionObserver]: Analyzing ICFG ArraysOfVariableLength2_true-valid-memsafety.c_18.bpl [2018-10-14 16:24:40,737 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-14 16:24:40,746 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-14 16:24:40,763 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-14 16:24:40,790 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-14 16:24:40,791 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-14 16:24:40,792 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-14 16:24:40,792 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-14 16:24:40,792 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-14 16:24:40,792 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-14 16:24:40,792 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-14 16:24:40,792 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-14 16:24:40,793 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-14 16:24:40,813 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states. [2018-10-14 16:24:40,825 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-10-14 16:24:40,825 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:40,827 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:40,828 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:40,833 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:40,834 INFO L82 PathProgramCache]: Analyzing trace with hash -1777504921, now seen corresponding path program 1 times [2018-10-14 16:24:40,884 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:40,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:41,667 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:24:41,670 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-14 16:24:41,671 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2018-10-14 16:24:41,676 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-14 16:24:41,693 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-14 16:24:41,694 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2018-10-14 16:24:41,697 INFO L87 Difference]: Start difference. First operand 108 states. Second operand 12 states. [2018-10-14 16:24:41,999 WARN L179 SmtUtils]: Spent 124.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-10-14 16:24:42,618 WARN L179 SmtUtils]: Spent 249.00 ms on a formula simplification that was a NOOP. DAG size: 30 [2018-10-14 16:24:42,737 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification that was a NOOP. DAG size: 28 [2018-10-14 16:24:43,478 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:24:43,478 INFO L93 Difference]: Finished difference Result 204 states and 208 transitions. [2018-10-14 16:24:43,479 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-10-14 16:24:43,481 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 64 [2018-10-14 16:24:43,482 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:24:43,500 INFO L225 Difference]: With dead ends: 204 [2018-10-14 16:24:43,500 INFO L226 Difference]: Without dead ends: 204 [2018-10-14 16:24:43,505 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=98, Invalid=322, Unknown=0, NotChecked=0, Total=420 [2018-10-14 16:24:43,529 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 204 states. [2018-10-14 16:24:43,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 204 to 185. [2018-10-14 16:24:43,566 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 185 states. [2018-10-14 16:24:43,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 185 states to 185 states and 189 transitions. [2018-10-14 16:24:43,570 INFO L78 Accepts]: Start accepts. Automaton has 185 states and 189 transitions. Word has length 64 [2018-10-14 16:24:43,571 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:24:43,571 INFO L481 AbstractCegarLoop]: Abstraction has 185 states and 189 transitions. [2018-10-14 16:24:43,571 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-14 16:24:43,572 INFO L276 IsEmpty]: Start isEmpty. Operand 185 states and 189 transitions. [2018-10-14 16:24:43,576 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2018-10-14 16:24:43,577 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:43,577 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:43,578 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:43,578 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:43,578 INFO L82 PathProgramCache]: Analyzing trace with hash 123713428, now seen corresponding path program 1 times [2018-10-14 16:24:43,580 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:43,614 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:43,867 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 26 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:24:43,867 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:24:43,868 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [8] total 8 [2018-10-14 16:24:43,870 INFO L460 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-10-14 16:24:43,870 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-10-14 16:24:43,871 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2018-10-14 16:24:43,871 INFO L87 Difference]: Start difference. First operand 185 states and 189 transitions. Second operand 8 states. [2018-10-14 16:24:44,494 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:24:44,495 INFO L93 Difference]: Finished difference Result 306 states and 312 transitions. [2018-10-14 16:24:44,503 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-14 16:24:44,503 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 118 [2018-10-14 16:24:44,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:24:44,509 INFO L225 Difference]: With dead ends: 306 [2018-10-14 16:24:44,510 INFO L226 Difference]: Without dead ends: 306 [2018-10-14 16:24:44,513 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=46, Invalid=136, Unknown=0, NotChecked=0, Total=182 [2018-10-14 16:24:44,513 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 306 states. [2018-10-14 16:24:44,540 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 306 to 213. [2018-10-14 16:24:44,540 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-10-14 16:24:44,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 217 transitions. [2018-10-14 16:24:44,547 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 217 transitions. Word has length 118 [2018-10-14 16:24:44,548 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:24:44,548 INFO L481 AbstractCegarLoop]: Abstraction has 213 states and 217 transitions. [2018-10-14 16:24:44,548 INFO L482 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-10-14 16:24:44,548 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 217 transitions. [2018-10-14 16:24:44,553 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 140 [2018-10-14 16:24:44,553 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:44,553 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:44,556 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:44,557 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:44,557 INFO L82 PathProgramCache]: Analyzing trace with hash 1233070383, now seen corresponding path program 1 times [2018-10-14 16:24:44,558 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:44,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:44,852 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 17 proven. 30 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-10-14 16:24:44,852 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:24:44,852 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2018-10-14 16:24:44,853 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-10-14 16:24:44,854 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-10-14 16:24:44,854 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=72, Unknown=0, NotChecked=0, Total=90 [2018-10-14 16:24:44,854 INFO L87 Difference]: Start difference. First operand 213 states and 217 transitions. Second operand 10 states. [2018-10-14 16:24:45,520 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:24:45,520 INFO L93 Difference]: Finished difference Result 339 states and 346 transitions. [2018-10-14 16:24:45,521 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-14 16:24:45,521 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 139 [2018-10-14 16:24:45,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:24:45,524 INFO L225 Difference]: With dead ends: 339 [2018-10-14 16:24:45,524 INFO L226 Difference]: Without dead ends: 339 [2018-10-14 16:24:45,525 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=90, Invalid=290, Unknown=0, NotChecked=0, Total=380 [2018-10-14 16:24:45,526 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 339 states. [2018-10-14 16:24:45,538 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 339 to 243. [2018-10-14 16:24:45,539 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 243 states. [2018-10-14 16:24:45,540 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 248 transitions. [2018-10-14 16:24:45,540 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 248 transitions. Word has length 139 [2018-10-14 16:24:45,541 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:24:45,541 INFO L481 AbstractCegarLoop]: Abstraction has 243 states and 248 transitions. [2018-10-14 16:24:45,541 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-10-14 16:24:45,541 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 248 transitions. [2018-10-14 16:24:45,544 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 154 [2018-10-14 16:24:45,544 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:45,545 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:45,545 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:45,545 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:45,546 INFO L82 PathProgramCache]: Analyzing trace with hash 949328200, now seen corresponding path program 1 times [2018-10-14 16:24:45,547 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:45,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:46,601 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 49 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-10-14 16:24:46,602 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:24:46,602 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2018-10-14 16:24:46,603 INFO L460 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-14 16:24:46,603 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-14 16:24:46,603 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=441, Unknown=0, NotChecked=0, Total=506 [2018-10-14 16:24:46,604 INFO L87 Difference]: Start difference. First operand 243 states and 248 transitions. Second operand 23 states. [2018-10-14 16:24:47,973 WARN L179 SmtUtils]: Spent 121.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 28 [2018-10-14 16:24:48,935 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:24:48,936 INFO L93 Difference]: Finished difference Result 296 states and 302 transitions. [2018-10-14 16:24:48,936 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-14 16:24:48,936 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 153 [2018-10-14 16:24:48,938 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:24:48,940 INFO L225 Difference]: With dead ends: 296 [2018-10-14 16:24:48,940 INFO L226 Difference]: Without dead ends: 296 [2018-10-14 16:24:48,942 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 5 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 389 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=243, Invalid=1563, Unknown=0, NotChecked=0, Total=1806 [2018-10-14 16:24:48,942 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 296 states. [2018-10-14 16:24:48,951 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 296 to 274. [2018-10-14 16:24:48,952 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 274 states. [2018-10-14 16:24:48,953 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 274 states to 274 states and 280 transitions. [2018-10-14 16:24:48,953 INFO L78 Accepts]: Start accepts. Automaton has 274 states and 280 transitions. Word has length 153 [2018-10-14 16:24:48,954 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:24:48,954 INFO L481 AbstractCegarLoop]: Abstraction has 274 states and 280 transitions. [2018-10-14 16:24:48,954 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-14 16:24:48,954 INFO L276 IsEmpty]: Start isEmpty. Operand 274 states and 280 transitions. [2018-10-14 16:24:48,958 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 208 [2018-10-14 16:24:48,958 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:48,959 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:48,959 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:48,959 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:48,959 INFO L82 PathProgramCache]: Analyzing trace with hash -245854027, now seen corresponding path program 2 times [2018-10-14 16:24:48,960 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:48,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:49,192 INFO L134 CoverageAnalysis]: Checked inductivity of 152 backedges. 56 proven. 94 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-14 16:24:49,192 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:24:49,192 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2018-10-14 16:24:49,193 INFO L460 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-10-14 16:24:49,193 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-10-14 16:24:49,193 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-10-14 16:24:49,194 INFO L87 Difference]: Start difference. First operand 274 states and 280 transitions. Second operand 10 states. [2018-10-14 16:24:49,440 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:24:49,441 INFO L93 Difference]: Finished difference Result 306 states and 312 transitions. [2018-10-14 16:24:49,442 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-10-14 16:24:49,442 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 207 [2018-10-14 16:24:49,443 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:24:49,446 INFO L225 Difference]: With dead ends: 306 [2018-10-14 16:24:49,446 INFO L226 Difference]: Without dead ends: 306 [2018-10-14 16:24:49,446 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2018-10-14 16:24:49,447 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 306 states. [2018-10-14 16:24:49,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 306 to 275. [2018-10-14 16:24:49,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 275 states. [2018-10-14 16:24:49,455 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 275 states to 275 states and 281 transitions. [2018-10-14 16:24:49,455 INFO L78 Accepts]: Start accepts. Automaton has 275 states and 281 transitions. Word has length 207 [2018-10-14 16:24:49,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:24:49,455 INFO L481 AbstractCegarLoop]: Abstraction has 275 states and 281 transitions. [2018-10-14 16:24:49,456 INFO L482 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-10-14 16:24:49,456 INFO L276 IsEmpty]: Start isEmpty. Operand 275 states and 281 transitions. [2018-10-14 16:24:49,459 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 229 [2018-10-14 16:24:49,460 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:49,460 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:49,460 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:49,461 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:49,461 INFO L82 PathProgramCache]: Analyzing trace with hash 2096430766, now seen corresponding path program 3 times [2018-10-14 16:24:49,462 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:49,485 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:49,750 INFO L134 CoverageAnalysis]: Checked inductivity of 176 backedges. 56 proven. 118 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-10-14 16:24:49,750 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:24:49,750 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-10-14 16:24:49,751 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-14 16:24:49,751 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-14 16:24:49,751 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=107, Unknown=0, NotChecked=0, Total=132 [2018-10-14 16:24:49,753 INFO L87 Difference]: Start difference. First operand 275 states and 281 transitions. Second operand 12 states. [2018-10-14 16:24:50,246 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:24:50,246 INFO L93 Difference]: Finished difference Result 308 states and 314 transitions. [2018-10-14 16:24:50,246 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-14 16:24:50,246 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 228 [2018-10-14 16:24:50,247 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:24:50,249 INFO L225 Difference]: With dead ends: 308 [2018-10-14 16:24:50,249 INFO L226 Difference]: Without dead ends: 308 [2018-10-14 16:24:50,250 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 83 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=123, Invalid=477, Unknown=0, NotChecked=0, Total=600 [2018-10-14 16:24:50,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 308 states. [2018-10-14 16:24:50,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 308 to 296. [2018-10-14 16:24:50,255 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 296 states. [2018-10-14 16:24:50,256 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 296 states to 296 states and 302 transitions. [2018-10-14 16:24:50,257 INFO L78 Accepts]: Start accepts. Automaton has 296 states and 302 transitions. Word has length 228 [2018-10-14 16:24:50,257 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:24:50,257 INFO L481 AbstractCegarLoop]: Abstraction has 296 states and 302 transitions. [2018-10-14 16:24:50,257 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-14 16:24:50,258 INFO L276 IsEmpty]: Start isEmpty. Operand 296 states and 302 transitions. [2018-10-14 16:24:50,261 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 250 [2018-10-14 16:24:50,261 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:50,261 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:50,262 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:50,262 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:50,262 INFO L82 PathProgramCache]: Analyzing trace with hash 1398879829, now seen corresponding path program 4 times [2018-10-14 16:24:50,263 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:50,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:51,235 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 102 proven. 23 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2018-10-14 16:24:51,235 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:24:51,235 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-14 16:24:51,236 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-14 16:24:51,236 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-14 16:24:51,236 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2018-10-14 16:24:51,236 INFO L87 Difference]: Start difference. First operand 296 states and 302 transitions. Second operand 9 states. [2018-10-14 16:24:51,651 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:24:51,651 INFO L93 Difference]: Finished difference Result 751 states and 766 transitions. [2018-10-14 16:24:51,659 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-14 16:24:51,659 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 249 [2018-10-14 16:24:51,660 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:24:51,663 INFO L225 Difference]: With dead ends: 751 [2018-10-14 16:24:51,663 INFO L226 Difference]: Without dead ends: 751 [2018-10-14 16:24:51,664 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=106, Invalid=356, Unknown=0, NotChecked=0, Total=462 [2018-10-14 16:24:51,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 751 states. [2018-10-14 16:24:51,672 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 751 to 328. [2018-10-14 16:24:51,672 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 328 states. [2018-10-14 16:24:51,673 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 328 states to 328 states and 336 transitions. [2018-10-14 16:24:51,674 INFO L78 Accepts]: Start accepts. Automaton has 328 states and 336 transitions. Word has length 249 [2018-10-14 16:24:51,674 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:24:51,674 INFO L481 AbstractCegarLoop]: Abstraction has 328 states and 336 transitions. [2018-10-14 16:24:51,674 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-14 16:24:51,675 INFO L276 IsEmpty]: Start isEmpty. Operand 328 states and 336 transitions. [2018-10-14 16:24:51,678 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 264 [2018-10-14 16:24:51,679 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:51,679 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:51,679 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:51,680 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:51,680 INFO L82 PathProgramCache]: Analyzing trace with hash -907105298, now seen corresponding path program 5 times [2018-10-14 16:24:51,681 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:51,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:52,099 INFO L134 CoverageAnalysis]: Checked inductivity of 238 backedges. 118 proven. 24 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2018-10-14 16:24:52,100 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:24:52,100 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2018-10-14 16:24:52,100 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-14 16:24:52,101 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-14 16:24:52,101 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2018-10-14 16:24:52,101 INFO L87 Difference]: Start difference. First operand 328 states and 336 transitions. Second operand 11 states. [2018-10-14 16:24:52,682 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:24:52,682 INFO L93 Difference]: Finished difference Result 757 states and 772 transitions. [2018-10-14 16:24:52,688 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-14 16:24:52,688 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 263 [2018-10-14 16:24:52,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:24:52,692 INFO L225 Difference]: With dead ends: 757 [2018-10-14 16:24:52,693 INFO L226 Difference]: Without dead ends: 757 [2018-10-14 16:24:52,693 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 156 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=175, Invalid=637, Unknown=0, NotChecked=0, Total=812 [2018-10-14 16:24:52,694 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 757 states. [2018-10-14 16:24:52,700 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 757 to 399. [2018-10-14 16:24:52,701 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 399 states. [2018-10-14 16:24:52,702 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 399 states to 399 states and 408 transitions. [2018-10-14 16:24:52,702 INFO L78 Accepts]: Start accepts. Automaton has 399 states and 408 transitions. Word has length 263 [2018-10-14 16:24:52,703 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:24:52,703 INFO L481 AbstractCegarLoop]: Abstraction has 399 states and 408 transitions. [2018-10-14 16:24:52,703 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-14 16:24:52,703 INFO L276 IsEmpty]: Start isEmpty. Operand 399 states and 408 transitions. [2018-10-14 16:24:52,705 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 278 [2018-10-14 16:24:52,705 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:52,705 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:52,705 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:52,706 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:52,706 INFO L82 PathProgramCache]: Analyzing trace with hash 1097720263, now seen corresponding path program 6 times [2018-10-14 16:24:52,707 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:52,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:54,350 INFO L134 CoverageAnalysis]: Checked inductivity of 269 backedges. 0 proven. 250 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2018-10-14 16:24:54,351 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:24:54,351 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35] total 35 [2018-10-14 16:24:54,352 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-10-14 16:24:54,352 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-10-14 16:24:54,353 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=1081, Unknown=0, NotChecked=0, Total=1190 [2018-10-14 16:24:54,353 INFO L87 Difference]: Start difference. First operand 399 states and 408 transitions. Second operand 35 states. [2018-10-14 16:24:57,578 WARN L179 SmtUtils]: Spent 223.00 ms on a formula simplification that was a NOOP. DAG size: 29 [2018-10-14 16:24:58,522 WARN L179 SmtUtils]: Spent 444.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 32 [2018-10-14 16:24:59,132 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:24:59,132 INFO L93 Difference]: Finished difference Result 544 states and 555 transitions. [2018-10-14 16:24:59,133 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-10-14 16:24:59,133 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 277 [2018-10-14 16:24:59,134 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:24:59,137 INFO L225 Difference]: With dead ends: 544 [2018-10-14 16:24:59,137 INFO L226 Difference]: Without dead ends: 544 [2018-10-14 16:24:59,140 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1099 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=417, Invalid=4005, Unknown=0, NotChecked=0, Total=4422 [2018-10-14 16:24:59,141 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 544 states. [2018-10-14 16:24:59,149 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 544 to 523. [2018-10-14 16:24:59,149 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 523 states. [2018-10-14 16:24:59,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 523 states to 523 states and 534 transitions. [2018-10-14 16:24:59,151 INFO L78 Accepts]: Start accepts. Automaton has 523 states and 534 transitions. Word has length 277 [2018-10-14 16:24:59,151 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:24:59,152 INFO L481 AbstractCegarLoop]: Abstraction has 523 states and 534 transitions. [2018-10-14 16:24:59,152 INFO L482 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-10-14 16:24:59,152 INFO L276 IsEmpty]: Start isEmpty. Operand 523 states and 534 transitions. [2018-10-14 16:24:59,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 402 [2018-10-14 16:24:59,154 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:24:59,155 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:24:59,155 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:24:59,155 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:24:59,155 INFO L82 PathProgramCache]: Analyzing trace with hash -758820410, now seen corresponding path program 7 times [2018-10-14 16:24:59,156 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:24:59,184 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:24:59,578 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 187 proven. 439 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2018-10-14 16:24:59,579 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:24:59,579 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [18] total 18 [2018-10-14 16:24:59,580 INFO L460 AbstractCegarLoop]: Interpolant automaton has 18 states [2018-10-14 16:24:59,580 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2018-10-14 16:24:59,580 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=263, Unknown=0, NotChecked=0, Total=306 [2018-10-14 16:24:59,580 INFO L87 Difference]: Start difference. First operand 523 states and 534 transitions. Second operand 18 states. [2018-10-14 16:25:00,488 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:00,489 INFO L93 Difference]: Finished difference Result 610 states and 622 transitions. [2018-10-14 16:25:00,489 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-10-14 16:25:00,489 INFO L78 Accepts]: Start accepts. Automaton has 18 states. Word has length 401 [2018-10-14 16:25:00,491 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:00,495 INFO L225 Difference]: With dead ends: 610 [2018-10-14 16:25:00,495 INFO L226 Difference]: Without dead ends: 610 [2018-10-14 16:25:00,496 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 261 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=308, Invalid=1252, Unknown=0, NotChecked=0, Total=1560 [2018-10-14 16:25:00,497 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 610 states. [2018-10-14 16:25:00,503 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 610 to 537. [2018-10-14 16:25:00,504 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 537 states. [2018-10-14 16:25:00,505 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 537 states to 537 states and 548 transitions. [2018-10-14 16:25:00,505 INFO L78 Accepts]: Start accepts. Automaton has 537 states and 548 transitions. Word has length 401 [2018-10-14 16:25:00,506 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:00,506 INFO L481 AbstractCegarLoop]: Abstraction has 537 states and 548 transitions. [2018-10-14 16:25:00,506 INFO L482 AbstractCegarLoop]: Interpolant automaton has 18 states. [2018-10-14 16:25:00,506 INFO L276 IsEmpty]: Start isEmpty. Operand 537 states and 548 transitions. [2018-10-14 16:25:00,509 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 416 [2018-10-14 16:25:00,509 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:00,509 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:00,509 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:00,510 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:00,510 INFO L82 PathProgramCache]: Analyzing trace with hash 1482780063, now seen corresponding path program 8 times [2018-10-14 16:25:00,511 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:00,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:01,349 INFO L134 CoverageAnalysis]: Checked inductivity of 764 backedges. 385 proven. 37 refuted. 0 times theorem prover too weak. 342 trivial. 0 not checked. [2018-10-14 16:25:01,350 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:01,350 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-10-14 16:25:01,350 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-14 16:25:01,351 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-14 16:25:01,351 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2018-10-14 16:25:01,351 INFO L87 Difference]: Start difference. First operand 537 states and 548 transitions. Second operand 15 states. [2018-10-14 16:25:03,010 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:03,010 INFO L93 Difference]: Finished difference Result 1594 states and 1623 transitions. [2018-10-14 16:25:03,010 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-10-14 16:25:03,010 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 415 [2018-10-14 16:25:03,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:03,018 INFO L225 Difference]: With dead ends: 1594 [2018-10-14 16:25:03,018 INFO L226 Difference]: Without dead ends: 1554 [2018-10-14 16:25:03,021 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 79 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2242 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=1134, Invalid=5346, Unknown=0, NotChecked=0, Total=6480 [2018-10-14 16:25:03,022 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1554 states. [2018-10-14 16:25:03,036 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1554 to 762. [2018-10-14 16:25:03,036 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 762 states. [2018-10-14 16:25:03,038 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 762 states to 762 states and 779 transitions. [2018-10-14 16:25:03,038 INFO L78 Accepts]: Start accepts. Automaton has 762 states and 779 transitions. Word has length 415 [2018-10-14 16:25:03,039 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:03,039 INFO L481 AbstractCegarLoop]: Abstraction has 762 states and 779 transitions. [2018-10-14 16:25:03,039 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-14 16:25:03,039 INFO L276 IsEmpty]: Start isEmpty. Operand 762 states and 779 transitions. [2018-10-14 16:25:03,042 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 437 [2018-10-14 16:25:03,042 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:03,042 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:03,043 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:03,043 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:03,043 INFO L82 PathProgramCache]: Analyzing trace with hash 1200566010, now seen corresponding path program 9 times [2018-10-14 16:25:03,044 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:03,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:03,655 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-10-14 16:25:06,175 INFO L134 CoverageAnalysis]: Checked inductivity of 873 backedges. 0 proven. 781 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2018-10-14 16:25:06,175 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:06,175 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-14 16:25:06,176 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-14 16:25:06,176 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-14 16:25:06,177 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=191, Invalid=2161, Unknown=0, NotChecked=0, Total=2352 [2018-10-14 16:25:06,177 INFO L87 Difference]: Start difference. First operand 762 states and 779 transitions. Second operand 49 states. [2018-10-14 16:25:09,833 WARN L179 SmtUtils]: Spent 384.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 36 [2018-10-14 16:25:11,149 WARN L179 SmtUtils]: Spent 137.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 36 [2018-10-14 16:25:11,824 WARN L179 SmtUtils]: Spent 154.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 27 [2018-10-14 16:25:13,530 WARN L179 SmtUtils]: Spent 515.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 39 [2018-10-14 16:25:15,886 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:15,886 INFO L93 Difference]: Finished difference Result 1022 states and 1043 transitions. [2018-10-14 16:25:15,886 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 73 states. [2018-10-14 16:25:15,887 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 436 [2018-10-14 16:25:15,888 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:15,892 INFO L225 Difference]: With dead ends: 1022 [2018-10-14 16:25:15,892 INFO L226 Difference]: Without dead ends: 1022 [2018-10-14 16:25:15,896 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 8 SyntacticMatches, 6 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3824 ImplicationChecksByTransitivity, 8.5s TimeCoverageRelationStatistics Valid=1727, Invalid=11383, Unknown=0, NotChecked=0, Total=13110 [2018-10-14 16:25:15,897 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1022 states. [2018-10-14 16:25:15,909 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1022 to 921. [2018-10-14 16:25:15,910 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 921 states. [2018-10-14 16:25:15,911 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 921 states to 921 states and 940 transitions. [2018-10-14 16:25:15,912 INFO L78 Accepts]: Start accepts. Automaton has 921 states and 940 transitions. Word has length 436 [2018-10-14 16:25:15,912 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:15,913 INFO L481 AbstractCegarLoop]: Abstraction has 921 states and 940 transitions. [2018-10-14 16:25:15,913 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-14 16:25:15,913 INFO L276 IsEmpty]: Start isEmpty. Operand 921 states and 940 transitions. [2018-10-14 16:25:15,917 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 596 [2018-10-14 16:25:15,917 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:15,918 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:15,918 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:15,918 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:15,919 INFO L82 PathProgramCache]: Analyzing trace with hash 1907174247, now seen corresponding path program 10 times [2018-10-14 16:25:15,919 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:15,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:16,790 INFO L134 CoverageAnalysis]: Checked inductivity of 1858 backedges. 648 proven. 992 refuted. 0 times theorem prover too weak. 218 trivial. 0 not checked. [2018-10-14 16:25:16,790 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:16,791 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22] total 22 [2018-10-14 16:25:16,791 INFO L460 AbstractCegarLoop]: Interpolant automaton has 22 states [2018-10-14 16:25:16,791 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2018-10-14 16:25:16,792 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=401, Unknown=0, NotChecked=0, Total=462 [2018-10-14 16:25:16,792 INFO L87 Difference]: Start difference. First operand 921 states and 940 transitions. Second operand 22 states. [2018-10-14 16:25:17,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:17,869 INFO L93 Difference]: Finished difference Result 1029 states and 1049 transitions. [2018-10-14 16:25:17,872 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-14 16:25:17,873 INFO L78 Accepts]: Start accepts. Automaton has 22 states. Word has length 595 [2018-10-14 16:25:17,874 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:17,880 INFO L225 Difference]: With dead ends: 1029 [2018-10-14 16:25:17,880 INFO L226 Difference]: Without dead ends: 1029 [2018-10-14 16:25:17,881 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 50 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 453 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=473, Invalid=1977, Unknown=0, NotChecked=0, Total=2450 [2018-10-14 16:25:17,882 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1029 states. [2018-10-14 16:25:17,899 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1029 to 935. [2018-10-14 16:25:17,899 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 935 states. [2018-10-14 16:25:17,901 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 935 states to 935 states and 954 transitions. [2018-10-14 16:25:17,901 INFO L78 Accepts]: Start accepts. Automaton has 935 states and 954 transitions. Word has length 595 [2018-10-14 16:25:17,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:17,902 INFO L481 AbstractCegarLoop]: Abstraction has 935 states and 954 transitions. [2018-10-14 16:25:17,902 INFO L482 AbstractCegarLoop]: Interpolant automaton has 22 states. [2018-10-14 16:25:17,902 INFO L276 IsEmpty]: Start isEmpty. Operand 935 states and 954 transitions. [2018-10-14 16:25:17,907 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 610 [2018-10-14 16:25:17,907 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:17,908 INFO L375 BasicCegarLoop]: trace histogram [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:17,908 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:17,908 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:17,908 INFO L82 PathProgramCache]: Analyzing trace with hash -686335616, now seen corresponding path program 11 times [2018-10-14 16:25:17,909 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:17,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:20,190 INFO L134 CoverageAnalysis]: Checked inductivity of 1989 backedges. 923 proven. 93 refuted. 0 times theorem prover too weak. 973 trivial. 0 not checked. [2018-10-14 16:25:20,190 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:20,190 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-10-14 16:25:20,191 INFO L460 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-14 16:25:20,191 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-14 16:25:20,192 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=292, Unknown=0, NotChecked=0, Total=342 [2018-10-14 16:25:20,192 INFO L87 Difference]: Start difference. First operand 935 states and 954 transitions. Second operand 19 states. [2018-10-14 16:25:21,138 WARN L179 SmtUtils]: Spent 186.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 11 [2018-10-14 16:25:22,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:22,674 INFO L93 Difference]: Finished difference Result 2443 states and 2486 transitions. [2018-10-14 16:25:22,675 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 103 states. [2018-10-14 16:25:22,675 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 609 [2018-10-14 16:25:22,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:22,684 INFO L225 Difference]: With dead ends: 2443 [2018-10-14 16:25:22,684 INFO L226 Difference]: Without dead ends: 2389 [2018-10-14 16:25:22,688 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4879 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=1993, Invalid=11117, Unknown=0, NotChecked=0, Total=13110 [2018-10-14 16:25:22,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2389 states. [2018-10-14 16:25:22,712 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2389 to 1173. [2018-10-14 16:25:22,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1173 states. [2018-10-14 16:25:22,715 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1173 states to 1173 states and 1197 transitions. [2018-10-14 16:25:22,715 INFO L78 Accepts]: Start accepts. Automaton has 1173 states and 1197 transitions. Word has length 609 [2018-10-14 16:25:22,716 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:22,716 INFO L481 AbstractCegarLoop]: Abstraction has 1173 states and 1197 transitions. [2018-10-14 16:25:22,716 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-14 16:25:22,716 INFO L276 IsEmpty]: Start isEmpty. Operand 1173 states and 1197 transitions. [2018-10-14 16:25:22,721 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 631 [2018-10-14 16:25:22,721 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:22,722 INFO L375 BasicCegarLoop]: trace histogram [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:22,722 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:22,722 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:22,722 INFO L82 PathProgramCache]: Analyzing trace with hash 764235019, now seen corresponding path program 12 times [2018-10-14 16:25:22,723 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:22,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:26,792 INFO L134 CoverageAnalysis]: Checked inductivity of 2183 backedges. 0 proven. 1902 refuted. 0 times theorem prover too weak. 281 trivial. 0 not checked. [2018-10-14 16:25:26,792 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:26,792 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [54] total 54 [2018-10-14 16:25:26,793 INFO L460 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-10-14 16:25:26,793 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-10-14 16:25:26,794 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=176, Invalid=2686, Unknown=0, NotChecked=0, Total=2862 [2018-10-14 16:25:26,795 INFO L87 Difference]: Start difference. First operand 1173 states and 1197 transitions. Second operand 54 states. [2018-10-14 16:25:33,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:33,971 INFO L93 Difference]: Finished difference Result 1388 states and 1414 transitions. [2018-10-14 16:25:33,971 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-10-14 16:25:33,972 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 630 [2018-10-14 16:25:33,973 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:33,978 INFO L225 Difference]: With dead ends: 1388 [2018-10-14 16:25:33,978 INFO L226 Difference]: Without dead ends: 1388 [2018-10-14 16:25:33,981 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 11 SyntacticMatches, 6 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3098 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=692, Invalid=10438, Unknown=0, NotChecked=0, Total=11130 [2018-10-14 16:25:33,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1388 states. [2018-10-14 16:25:34,001 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1388 to 1367. [2018-10-14 16:25:34,002 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1367 states. [2018-10-14 16:25:34,004 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1367 states to 1367 states and 1393 transitions. [2018-10-14 16:25:34,004 INFO L78 Accepts]: Start accepts. Automaton has 1367 states and 1393 transitions. Word has length 630 [2018-10-14 16:25:34,005 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:34,005 INFO L481 AbstractCegarLoop]: Abstraction has 1367 states and 1393 transitions. [2018-10-14 16:25:34,005 INFO L482 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-10-14 16:25:34,006 INFO L276 IsEmpty]: Start isEmpty. Operand 1367 states and 1393 transitions. [2018-10-14 16:25:34,012 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 825 [2018-10-14 16:25:34,013 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:34,013 INFO L375 BasicCegarLoop]: trace histogram [14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:34,014 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:34,014 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:34,014 INFO L82 PathProgramCache]: Analyzing trace with hash 1022825180, now seen corresponding path program 13 times [2018-10-14 16:25:34,015 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:34,064 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:35,679 INFO L134 CoverageAnalysis]: Checked inductivity of 4123 backedges. 2341 proven. 1324 refuted. 0 times theorem prover too weak. 458 trivial. 0 not checked. [2018-10-14 16:25:35,679 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:35,679 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24] total 24 [2018-10-14 16:25:35,680 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states [2018-10-14 16:25:35,680 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2018-10-14 16:25:35,681 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=473, Unknown=0, NotChecked=0, Total=552 [2018-10-14 16:25:35,681 INFO L87 Difference]: Start difference. First operand 1367 states and 1393 transitions. Second operand 24 states. [2018-10-14 16:25:37,009 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:37,009 INFO L93 Difference]: Finished difference Result 1400 states and 1426 transitions. [2018-10-14 16:25:37,009 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-10-14 16:25:37,010 INFO L78 Accepts]: Start accepts. Automaton has 24 states. Word has length 824 [2018-10-14 16:25:37,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:37,016 INFO L225 Difference]: With dead ends: 1400 [2018-10-14 16:25:37,016 INFO L226 Difference]: Without dead ends: 1400 [2018-10-14 16:25:37,017 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 55 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 593 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=564, Invalid=2406, Unknown=0, NotChecked=0, Total=2970 [2018-10-14 16:25:37,018 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1400 states. [2018-10-14 16:25:37,034 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1400 to 1388. [2018-10-14 16:25:37,035 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1388 states. [2018-10-14 16:25:37,037 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1388 states to 1388 states and 1414 transitions. [2018-10-14 16:25:37,037 INFO L78 Accepts]: Start accepts. Automaton has 1388 states and 1414 transitions. Word has length 824 [2018-10-14 16:25:37,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:37,038 INFO L481 AbstractCegarLoop]: Abstraction has 1388 states and 1414 transitions. [2018-10-14 16:25:37,038 INFO L482 AbstractCegarLoop]: Interpolant automaton has 24 states. [2018-10-14 16:25:37,038 INFO L276 IsEmpty]: Start isEmpty. Operand 1388 states and 1414 transitions. [2018-10-14 16:25:37,045 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 846 [2018-10-14 16:25:37,046 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:37,046 INFO L375 BasicCegarLoop]: trace histogram [15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:37,046 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:37,047 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:37,047 INFO L82 PathProgramCache]: Analyzing trace with hash 1962558767, now seen corresponding path program 14 times [2018-10-14 16:25:37,048 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:37,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:39,136 INFO L134 CoverageAnalysis]: Checked inductivity of 4423 backedges. 1879 proven. 234 refuted. 0 times theorem prover too weak. 2310 trivial. 0 not checked. [2018-10-14 16:25:39,137 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:39,137 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2018-10-14 16:25:39,137 INFO L460 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-14 16:25:39,138 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-14 16:25:39,138 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=436, Unknown=0, NotChecked=0, Total=506 [2018-10-14 16:25:39,138 INFO L87 Difference]: Start difference. First operand 1388 states and 1414 transitions. Second operand 23 states. [2018-10-14 16:25:41,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:41,260 INFO L93 Difference]: Finished difference Result 3123 states and 3178 transitions. [2018-10-14 16:25:41,260 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2018-10-14 16:25:41,260 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 845 [2018-10-14 16:25:41,261 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:41,271 INFO L225 Difference]: With dead ends: 3123 [2018-10-14 16:25:41,272 INFO L226 Difference]: Without dead ends: 3123 [2018-10-14 16:25:41,273 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1325 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=926, Invalid=4186, Unknown=0, NotChecked=0, Total=5112 [2018-10-14 16:25:41,275 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3123 states. [2018-10-14 16:25:41,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3123 to 1715. [2018-10-14 16:25:41,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1715 states. [2018-10-14 16:25:41,305 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1715 states to 1715 states and 1746 transitions. [2018-10-14 16:25:41,306 INFO L78 Accepts]: Start accepts. Automaton has 1715 states and 1746 transitions. Word has length 845 [2018-10-14 16:25:41,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:41,307 INFO L481 AbstractCegarLoop]: Abstraction has 1715 states and 1746 transitions. [2018-10-14 16:25:41,307 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-14 16:25:41,307 INFO L276 IsEmpty]: Start isEmpty. Operand 1715 states and 1746 transitions. [2018-10-14 16:25:41,315 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 860 [2018-10-14 16:25:41,315 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:41,316 INFO L375 BasicCegarLoop]: trace histogram [15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:41,316 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:41,316 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:41,316 INFO L82 PathProgramCache]: Analyzing trace with hash 812627272, now seen corresponding path program 15 times [2018-10-14 16:25:41,317 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:41,403 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:45,942 INFO L134 CoverageAnalysis]: Checked inductivity of 4625 backedges. 0 proven. 4003 refuted. 0 times theorem prover too weak. 622 trivial. 0 not checked. [2018-10-14 16:25:45,942 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:45,942 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [54] total 54 [2018-10-14 16:25:45,943 INFO L460 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-10-14 16:25:45,943 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-10-14 16:25:45,943 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=2694, Unknown=0, NotChecked=0, Total=2862 [2018-10-14 16:25:45,943 INFO L87 Difference]: Start difference. First operand 1715 states and 1746 transitions. Second operand 54 states. [2018-10-14 16:25:52,556 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:52,556 INFO L93 Difference]: Finished difference Result 1963 states and 1996 transitions. [2018-10-14 16:25:52,557 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-10-14 16:25:52,557 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 859 [2018-10-14 16:25:52,558 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:52,564 INFO L225 Difference]: With dead ends: 1963 [2018-10-14 16:25:52,564 INFO L226 Difference]: Without dead ends: 1963 [2018-10-14 16:25:52,565 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 16 SyntacticMatches, 3 SemanticMatches, 102 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2935 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=627, Invalid=10085, Unknown=0, NotChecked=0, Total=10712 [2018-10-14 16:25:52,567 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1963 states. [2018-10-14 16:25:52,587 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1963 to 1944. [2018-10-14 16:25:52,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1944 states. [2018-10-14 16:25:52,590 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1944 states to 1944 states and 1977 transitions. [2018-10-14 16:25:52,591 INFO L78 Accepts]: Start accepts. Automaton has 1944 states and 1977 transitions. Word has length 859 [2018-10-14 16:25:52,591 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:52,592 INFO L481 AbstractCegarLoop]: Abstraction has 1944 states and 1977 transitions. [2018-10-14 16:25:52,592 INFO L482 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-10-14 16:25:52,592 INFO L276 IsEmpty]: Start isEmpty. Operand 1944 states and 1977 transitions. [2018-10-14 16:25:52,604 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1089 [2018-10-14 16:25:52,604 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:52,605 INFO L375 BasicCegarLoop]: trace histogram [20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:52,605 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:52,605 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:52,606 INFO L82 PathProgramCache]: Analyzing trace with hash 1281087275, now seen corresponding path program 16 times [2018-10-14 16:25:52,607 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:52,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:54,127 INFO L134 CoverageAnalysis]: Checked inductivity of 8016 backedges. 4901 proven. 2240 refuted. 0 times theorem prover too weak. 875 trivial. 0 not checked. [2018-10-14 16:25:54,127 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:54,127 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [28] total 28 [2018-10-14 16:25:54,128 INFO L460 AbstractCegarLoop]: Interpolant automaton has 28 states [2018-10-14 16:25:54,128 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2018-10-14 16:25:54,128 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=651, Unknown=0, NotChecked=0, Total=756 [2018-10-14 16:25:54,129 INFO L87 Difference]: Start difference. First operand 1944 states and 1977 transitions. Second operand 28 states. [2018-10-14 16:25:55,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:25:55,996 INFO L93 Difference]: Finished difference Result 1977 states and 2010 transitions. [2018-10-14 16:25:55,996 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2018-10-14 16:25:55,996 INFO L78 Accepts]: Start accepts. Automaton has 28 states. Word has length 1088 [2018-10-14 16:25:55,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:25:56,003 INFO L225 Difference]: With dead ends: 1977 [2018-10-14 16:25:56,004 INFO L226 Difference]: Without dead ends: 1977 [2018-10-14 16:25:56,004 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 865 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=787, Invalid=3373, Unknown=0, NotChecked=0, Total=4160 [2018-10-14 16:25:56,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1977 states. [2018-10-14 16:25:56,022 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1977 to 1965. [2018-10-14 16:25:56,022 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1965 states. [2018-10-14 16:25:56,025 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1965 states to 1965 states and 1998 transitions. [2018-10-14 16:25:56,026 INFO L78 Accepts]: Start accepts. Automaton has 1965 states and 1998 transitions. Word has length 1088 [2018-10-14 16:25:56,026 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:25:56,027 INFO L481 AbstractCegarLoop]: Abstraction has 1965 states and 1998 transitions. [2018-10-14 16:25:56,027 INFO L482 AbstractCegarLoop]: Interpolant automaton has 28 states. [2018-10-14 16:25:56,027 INFO L276 IsEmpty]: Start isEmpty. Operand 1965 states and 1998 transitions. [2018-10-14 16:25:56,038 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1110 [2018-10-14 16:25:56,038 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:25:56,039 INFO L375 BasicCegarLoop]: trace histogram [21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:25:56,039 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:25:56,039 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:25:56,040 INFO L82 PathProgramCache]: Analyzing trace with hash 4555794, now seen corresponding path program 17 times [2018-10-14 16:25:56,040 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:25:56,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:25:57,235 INFO L134 CoverageAnalysis]: Checked inductivity of 8443 backedges. 3332 proven. 332 refuted. 0 times theorem prover too weak. 4779 trivial. 0 not checked. [2018-10-14 16:25:57,235 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:25:57,235 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2018-10-14 16:25:57,236 INFO L460 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-10-14 16:25:57,236 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-10-14 16:25:57,236 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=608, Unknown=0, NotChecked=0, Total=702 [2018-10-14 16:25:57,237 INFO L87 Difference]: Start difference. First operand 1965 states and 1998 transitions. Second operand 27 states. [2018-10-14 16:26:00,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:26:00,182 INFO L93 Difference]: Finished difference Result 4510 states and 4585 transitions. [2018-10-14 16:26:00,182 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-10-14 16:26:00,183 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 1109 [2018-10-14 16:26:00,183 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:26:00,195 INFO L225 Difference]: With dead ends: 4510 [2018-10-14 16:26:00,195 INFO L226 Difference]: Without dead ends: 4510 [2018-10-14 16:26:00,196 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 84 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1971 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=1316, Invalid=5994, Unknown=0, NotChecked=0, Total=7310 [2018-10-14 16:26:00,198 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4510 states. [2018-10-14 16:26:00,227 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4510 to 2237. [2018-10-14 16:26:00,228 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2237 states. [2018-10-14 16:26:00,231 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2237 states to 2237 states and 2276 transitions. [2018-10-14 16:26:00,231 INFO L78 Accepts]: Start accepts. Automaton has 2237 states and 2276 transitions. Word has length 1109 [2018-10-14 16:26:00,232 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:26:00,232 INFO L481 AbstractCegarLoop]: Abstraction has 2237 states and 2276 transitions. [2018-10-14 16:26:00,232 INFO L482 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-10-14 16:26:00,232 INFO L276 IsEmpty]: Start isEmpty. Operand 2237 states and 2276 transitions. [2018-10-14 16:26:00,245 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1124 [2018-10-14 16:26:00,245 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:26:00,246 INFO L375 BasicCegarLoop]: trace histogram [21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:26:00,246 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:26:00,246 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:26:00,247 INFO L82 PathProgramCache]: Analyzing trace with hash 1841670891, now seen corresponding path program 18 times [2018-10-14 16:26:00,247 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:26:00,411 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:26:01,487 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-10-14 16:26:07,416 INFO L134 CoverageAnalysis]: Checked inductivity of 8730 backedges. 0 proven. 7609 refuted. 0 times theorem prover too weak. 1121 trivial. 0 not checked. [2018-10-14 16:26:07,417 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:26:07,417 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-14 16:26:07,418 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-14 16:26:07,418 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-14 16:26:07,418 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=207, Invalid=3953, Unknown=0, NotChecked=0, Total=4160 [2018-10-14 16:26:07,419 INFO L87 Difference]: Start difference. First operand 2237 states and 2276 transitions. Second operand 65 states. [2018-10-14 16:26:17,443 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:26:17,444 INFO L93 Difference]: Finished difference Result 2524 states and 2565 transitions. [2018-10-14 16:26:17,444 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 81 states. [2018-10-14 16:26:17,444 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 1123 [2018-10-14 16:26:17,446 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:26:17,453 INFO L225 Difference]: With dead ends: 2524 [2018-10-14 16:26:17,453 INFO L226 Difference]: Without dead ends: 2524 [2018-10-14 16:26:17,455 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 146 GetRequests, 17 SyntacticMatches, 4 SemanticMatches, 125 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4501 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=792, Invalid=15210, Unknown=0, NotChecked=0, Total=16002 [2018-10-14 16:26:17,457 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2524 states. [2018-10-14 16:26:17,481 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2524 to 2501. [2018-10-14 16:26:17,481 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2501 states. [2018-10-14 16:26:17,485 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2501 states to 2501 states and 2542 transitions. [2018-10-14 16:26:17,486 INFO L78 Accepts]: Start accepts. Automaton has 2501 states and 2542 transitions. Word has length 1123 [2018-10-14 16:26:17,487 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:26:17,487 INFO L481 AbstractCegarLoop]: Abstraction has 2501 states and 2542 transitions. [2018-10-14 16:26:17,487 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-14 16:26:17,487 INFO L276 IsEmpty]: Start isEmpty. Operand 2501 states and 2542 transitions. [2018-10-14 16:26:17,511 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1388 [2018-10-14 16:26:17,511 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:26:17,512 INFO L375 BasicCegarLoop]: trace histogram [27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:26:17,513 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:26:17,513 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:26:17,513 INFO L82 PathProgramCache]: Analyzing trace with hash -1144066674, now seen corresponding path program 19 times [2018-10-14 16:26:17,514 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:26:17,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:26:19,538 INFO L134 CoverageAnalysis]: Checked inductivity of 14173 backedges. 9172 proven. 3518 refuted. 0 times theorem prover too weak. 1483 trivial. 0 not checked. [2018-10-14 16:26:19,538 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:26:19,538 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [32] total 32 [2018-10-14 16:26:19,539 INFO L460 AbstractCegarLoop]: Interpolant automaton has 32 states [2018-10-14 16:26:19,539 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2018-10-14 16:26:19,539 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=857, Unknown=0, NotChecked=0, Total=992 [2018-10-14 16:26:19,540 INFO L87 Difference]: Start difference. First operand 2501 states and 2542 transitions. Second operand 32 states. [2018-10-14 16:26:21,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:26:21,830 INFO L93 Difference]: Finished difference Result 2534 states and 2575 transitions. [2018-10-14 16:26:21,833 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-14 16:26:21,833 INFO L78 Accepts]: Start accepts. Automaton has 32 states. Word has length 1387 [2018-10-14 16:26:21,835 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:26:21,842 INFO L225 Difference]: With dead ends: 2534 [2018-10-14 16:26:21,842 INFO L226 Difference]: Without dead ends: 2534 [2018-10-14 16:26:21,843 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 75 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1188 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=1048, Invalid=4502, Unknown=0, NotChecked=0, Total=5550 [2018-10-14 16:26:21,845 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2534 states. [2018-10-14 16:26:21,865 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2534 to 2522. [2018-10-14 16:26:21,865 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2522 states. [2018-10-14 16:26:21,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2522 states to 2522 states and 2563 transitions. [2018-10-14 16:26:21,869 INFO L78 Accepts]: Start accepts. Automaton has 2522 states and 2563 transitions. Word has length 1387 [2018-10-14 16:26:21,870 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:26:21,870 INFO L481 AbstractCegarLoop]: Abstraction has 2522 states and 2563 transitions. [2018-10-14 16:26:21,870 INFO L482 AbstractCegarLoop]: Interpolant automaton has 32 states. [2018-10-14 16:26:21,870 INFO L276 IsEmpty]: Start isEmpty. Operand 2522 states and 2563 transitions. [2018-10-14 16:26:21,887 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1409 [2018-10-14 16:26:21,887 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:26:21,888 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:26:21,888 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:26:21,888 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:26:21,889 INFO L82 PathProgramCache]: Analyzing trace with hash -1425920543, now seen corresponding path program 20 times [2018-10-14 16:26:21,889 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:26:21,961 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:26:23,454 INFO L134 CoverageAnalysis]: Checked inductivity of 14748 backedges. 5393 proven. 444 refuted. 0 times theorem prover too weak. 8911 trivial. 0 not checked. [2018-10-14 16:26:23,455 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:26:23,455 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31] total 31 [2018-10-14 16:26:23,456 INFO L460 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-10-14 16:26:23,456 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-10-14 16:26:23,456 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=122, Invalid=808, Unknown=0, NotChecked=0, Total=930 [2018-10-14 16:26:23,456 INFO L87 Difference]: Start difference. First operand 2522 states and 2563 transitions. Second operand 31 states. [2018-10-14 16:26:26,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:26:26,317 INFO L93 Difference]: Finished difference Result 6218 states and 6316 transitions. [2018-10-14 16:26:26,317 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 78 states. [2018-10-14 16:26:26,317 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 1408 [2018-10-14 16:26:26,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:26:26,336 INFO L225 Difference]: With dead ends: 6218 [2018-10-14 16:26:26,336 INFO L226 Difference]: Without dead ends: 6218 [2018-10-14 16:26:26,337 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 98 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2744 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=1777, Invalid=8123, Unknown=0, NotChecked=0, Total=9900 [2018-10-14 16:26:26,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6218 states. [2018-10-14 16:26:26,369 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6218 to 2837. [2018-10-14 16:26:26,369 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2837 states. [2018-10-14 16:26:26,373 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2837 states to 2837 states and 2885 transitions. [2018-10-14 16:26:26,373 INFO L78 Accepts]: Start accepts. Automaton has 2837 states and 2885 transitions. Word has length 1408 [2018-10-14 16:26:26,374 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:26:26,374 INFO L481 AbstractCegarLoop]: Abstraction has 2837 states and 2885 transitions. [2018-10-14 16:26:26,374 INFO L482 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-10-14 16:26:26,375 INFO L276 IsEmpty]: Start isEmpty. Operand 2837 states and 2885 transitions. [2018-10-14 16:26:26,392 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1423 [2018-10-14 16:26:26,393 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:26:26,393 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:26:26,394 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:26:26,394 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:26:26,394 INFO L82 PathProgramCache]: Analyzing trace with hash 554794618, now seen corresponding path program 21 times [2018-10-14 16:26:26,395 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:26:26,510 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:26:37,636 INFO L134 CoverageAnalysis]: Checked inductivity of 15134 backedges. 0 proven. 13310 refuted. 0 times theorem prover too weak. 1824 trivial. 0 not checked. [2018-10-14 16:26:37,636 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:26:37,637 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [76] total 76 [2018-10-14 16:26:37,638 INFO L460 AbstractCegarLoop]: Interpolant automaton has 76 states [2018-10-14 16:26:37,638 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 76 interpolants. [2018-10-14 16:26:37,638 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=246, Invalid=5454, Unknown=0, NotChecked=0, Total=5700 [2018-10-14 16:26:37,639 INFO L87 Difference]: Start difference. First operand 2837 states and 2885 transitions. Second operand 76 states. [2018-10-14 16:26:52,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:26:52,314 INFO L93 Difference]: Finished difference Result 3167 states and 3217 transitions. [2018-10-14 16:26:52,314 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 95 states. [2018-10-14 16:26:52,314 INFO L78 Accepts]: Start accepts. Automaton has 76 states. Word has length 1422 [2018-10-14 16:26:52,316 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:26:52,321 INFO L225 Difference]: With dead ends: 3167 [2018-10-14 16:26:52,321 INFO L226 Difference]: Without dead ends: 3167 [2018-10-14 16:26:52,322 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 20 SyntacticMatches, 9 SemanticMatches, 149 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6696 ImplicationChecksByTransitivity, 8.7s TimeCoverageRelationStatistics Valid=971, Invalid=21679, Unknown=0, NotChecked=0, Total=22650 [2018-10-14 16:26:52,324 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3167 states. [2018-10-14 16:26:52,340 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3167 to 3136. [2018-10-14 16:26:52,340 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3136 states. [2018-10-14 16:26:52,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3136 states to 3136 states and 3186 transitions. [2018-10-14 16:26:52,343 INFO L78 Accepts]: Start accepts. Automaton has 3136 states and 3186 transitions. Word has length 1422 [2018-10-14 16:26:52,344 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:26:52,344 INFO L481 AbstractCegarLoop]: Abstraction has 3136 states and 3186 transitions. [2018-10-14 16:26:52,344 INFO L482 AbstractCegarLoop]: Interpolant automaton has 76 states. [2018-10-14 16:26:52,344 INFO L276 IsEmpty]: Start isEmpty. Operand 3136 states and 3186 transitions. [2018-10-14 16:26:52,368 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1722 [2018-10-14 16:26:52,368 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:26:52,369 INFO L375 BasicCegarLoop]: trace histogram [35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:26:52,369 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:26:52,369 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:26:52,370 INFO L82 PathProgramCache]: Analyzing trace with hash 587892619, now seen corresponding path program 22 times [2018-10-14 16:26:52,370 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:26:52,461 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:26:55,415 INFO L134 CoverageAnalysis]: Checked inductivity of 23335 backedges. 15797 proven. 5221 refuted. 0 times theorem prover too weak. 2317 trivial. 0 not checked. [2018-10-14 16:26:55,415 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:26:55,415 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [36] total 36 [2018-10-14 16:26:55,417 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-10-14 16:26:55,417 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-10-14 16:26:55,417 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=169, Invalid=1091, Unknown=0, NotChecked=0, Total=1260 [2018-10-14 16:26:55,417 INFO L87 Difference]: Start difference. First operand 3136 states and 3186 transitions. Second operand 36 states. [2018-10-14 16:26:58,433 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:26:58,434 INFO L93 Difference]: Finished difference Result 3169 states and 3219 transitions. [2018-10-14 16:26:58,434 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-10-14 16:26:58,434 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 1721 [2018-10-14 16:26:58,436 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:26:58,440 INFO L225 Difference]: With dead ends: 3169 [2018-10-14 16:26:58,441 INFO L226 Difference]: Without dead ends: 3169 [2018-10-14 16:26:58,442 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 83 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1562 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=1347, Invalid=5793, Unknown=0, NotChecked=0, Total=7140 [2018-10-14 16:26:58,443 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3169 states. [2018-10-14 16:26:58,459 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3169 to 3157. [2018-10-14 16:26:58,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3157 states. [2018-10-14 16:26:58,461 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3157 states to 3157 states and 3207 transitions. [2018-10-14 16:26:58,462 INFO L78 Accepts]: Start accepts. Automaton has 3157 states and 3207 transitions. Word has length 1721 [2018-10-14 16:26:58,462 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:26:58,463 INFO L481 AbstractCegarLoop]: Abstraction has 3157 states and 3207 transitions. [2018-10-14 16:26:58,463 INFO L482 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-10-14 16:26:58,463 INFO L276 IsEmpty]: Start isEmpty. Operand 3157 states and 3207 transitions. [2018-10-14 16:26:58,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1743 [2018-10-14 16:26:58,480 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:26:58,481 INFO L375 BasicCegarLoop]: trace histogram [36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:26:58,481 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:26:58,482 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:26:58,482 INFO L82 PathProgramCache]: Analyzing trace with hash 1370325206, now seen corresponding path program 23 times [2018-10-14 16:26:58,483 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:26:58,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:27:00,662 INFO L134 CoverageAnalysis]: Checked inductivity of 24079 backedges. 8167 proven. 570 refuted. 0 times theorem prover too weak. 15342 trivial. 0 not checked. [2018-10-14 16:27:00,663 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:27:00,663 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35] total 35 [2018-10-14 16:27:00,664 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-10-14 16:27:00,664 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-10-14 16:27:00,665 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=154, Invalid=1036, Unknown=0, NotChecked=0, Total=1190 [2018-10-14 16:27:00,665 INFO L87 Difference]: Start difference. First operand 3157 states and 3207 transitions. Second operand 35 states. [2018-10-14 16:27:05,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:27:05,265 INFO L93 Difference]: Finished difference Result 8275 states and 8399 transitions. [2018-10-14 16:27:05,265 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-10-14 16:27:05,265 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 1742 [2018-10-14 16:27:05,266 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:27:05,281 INFO L225 Difference]: With dead ends: 8275 [2018-10-14 16:27:05,281 INFO L226 Difference]: Without dead ends: 8275 [2018-10-14 16:27:05,283 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 112 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3644 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=2309, Invalid=10573, Unknown=0, NotChecked=0, Total=12882 [2018-10-14 16:27:05,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8275 states. [2018-10-14 16:27:05,329 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8275 to 3515. [2018-10-14 16:27:05,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3515 states. [2018-10-14 16:27:05,334 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3515 states to 3515 states and 3573 transitions. [2018-10-14 16:27:05,334 INFO L78 Accepts]: Start accepts. Automaton has 3515 states and 3573 transitions. Word has length 1742 [2018-10-14 16:27:05,335 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:27:05,335 INFO L481 AbstractCegarLoop]: Abstraction has 3515 states and 3573 transitions. [2018-10-14 16:27:05,336 INFO L482 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-10-14 16:27:05,336 INFO L276 IsEmpty]: Start isEmpty. Operand 3515 states and 3573 transitions. [2018-10-14 16:27:05,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1757 [2018-10-14 16:27:05,363 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:27:05,364 INFO L375 BasicCegarLoop]: trace histogram [36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:27:05,365 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:27:05,365 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:27:05,365 INFO L82 PathProgramCache]: Analyzing trace with hash -2021523281, now seen corresponding path program 24 times [2018-10-14 16:27:05,366 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:27:05,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:27:21,362 INFO L134 CoverageAnalysis]: Checked inductivity of 24578 backedges. 0 proven. 22008 refuted. 0 times theorem prover too weak. 2570 trivial. 0 not checked. [2018-10-14 16:27:21,362 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:27:21,363 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-14 16:27:21,363 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-14 16:27:21,364 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-14 16:27:21,364 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=330, Invalid=8982, Unknown=0, NotChecked=0, Total=9312 [2018-10-14 16:27:21,364 INFO L87 Difference]: Start difference. First operand 3515 states and 3573 transitions. Second operand 97 states. [2018-10-14 16:27:45,026 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:27:45,026 INFO L93 Difference]: Finished difference Result 3896 states and 3956 transitions. [2018-10-14 16:27:45,026 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 121 states. [2018-10-14 16:27:45,027 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 1756 [2018-10-14 16:27:45,028 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:27:45,036 INFO L225 Difference]: With dead ends: 3896 [2018-10-14 16:27:45,036 INFO L226 Difference]: Without dead ends: 3896 [2018-10-14 16:27:45,039 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 21 SyntacticMatches, 11 SemanticMatches, 197 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11877 ImplicationChecksByTransitivity, 12.9s TimeCoverageRelationStatistics Valid=1398, Invalid=38004, Unknown=0, NotChecked=0, Total=39402 [2018-10-14 16:27:45,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3896 states. [2018-10-14 16:27:45,065 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3896 to 3849. [2018-10-14 16:27:45,065 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3849 states. [2018-10-14 16:27:45,069 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3849 states to 3849 states and 3909 transitions. [2018-10-14 16:27:45,070 INFO L78 Accepts]: Start accepts. Automaton has 3849 states and 3909 transitions. Word has length 1756 [2018-10-14 16:27:45,071 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:27:45,071 INFO L481 AbstractCegarLoop]: Abstraction has 3849 states and 3909 transitions. [2018-10-14 16:27:45,071 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-14 16:27:45,071 INFO L276 IsEmpty]: Start isEmpty. Operand 3849 states and 3909 transitions. [2018-10-14 16:27:45,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2091 [2018-10-14 16:27:45,107 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:27:45,108 INFO L375 BasicCegarLoop]: trace histogram [44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:27:45,108 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:27:45,108 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:27:45,109 INFO L82 PathProgramCache]: Analyzing trace with hash 1018509860, now seen corresponding path program 25 times [2018-10-14 16:27:45,110 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:27:45,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:27:49,157 INFO L134 CoverageAnalysis]: Checked inductivity of 36348 backedges. 25524 proven. 7412 refuted. 0 times theorem prover too weak. 3412 trivial. 0 not checked. [2018-10-14 16:27:49,157 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:27:49,158 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [40] total 40 [2018-10-14 16:27:49,159 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states [2018-10-14 16:27:49,159 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2018-10-14 16:27:49,159 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=207, Invalid=1353, Unknown=0, NotChecked=0, Total=1560 [2018-10-14 16:27:49,159 INFO L87 Difference]: Start difference. First operand 3849 states and 3909 transitions. Second operand 40 states. [2018-10-14 16:27:52,690 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:27:52,691 INFO L93 Difference]: Finished difference Result 3882 states and 3942 transitions. [2018-10-14 16:27:52,691 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 67 states. [2018-10-14 16:27:52,691 INFO L78 Accepts]: Start accepts. Automaton has 40 states. Word has length 2090 [2018-10-14 16:27:52,693 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:27:52,696 INFO L225 Difference]: With dead ends: 3882 [2018-10-14 16:27:52,697 INFO L226 Difference]: Without dead ends: 3882 [2018-10-14 16:27:52,697 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1987 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=1684, Invalid=7246, Unknown=0, NotChecked=0, Total=8930 [2018-10-14 16:27:52,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3882 states. [2018-10-14 16:27:52,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3882 to 3870. [2018-10-14 16:27:52,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 3870 states. [2018-10-14 16:27:52,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 3870 states to 3870 states and 3930 transitions. [2018-10-14 16:27:52,728 INFO L78 Accepts]: Start accepts. Automaton has 3870 states and 3930 transitions. Word has length 2090 [2018-10-14 16:27:52,729 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:27:52,729 INFO L481 AbstractCegarLoop]: Abstraction has 3870 states and 3930 transitions. [2018-10-14 16:27:52,730 INFO L482 AbstractCegarLoop]: Interpolant automaton has 40 states. [2018-10-14 16:27:52,730 INFO L276 IsEmpty]: Start isEmpty. Operand 3870 states and 3930 transitions. [2018-10-14 16:27:52,764 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2112 [2018-10-14 16:27:52,765 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:27:52,766 INFO L375 BasicCegarLoop]: trace histogram [45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:27:52,766 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:27:52,766 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:27:52,767 INFO L82 PathProgramCache]: Analyzing trace with hash -1403871953, now seen corresponding path program 26 times [2018-10-14 16:27:52,767 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:27:52,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:27:55,963 INFO L134 CoverageAnalysis]: Checked inductivity of 37282 backedges. 11759 proven. 710 refuted. 0 times theorem prover too weak. 24813 trivial. 0 not checked. [2018-10-14 16:27:55,964 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:27:55,964 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39] total 39 [2018-10-14 16:27:55,965 INFO L460 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-10-14 16:27:55,965 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-10-14 16:27:55,965 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=190, Invalid=1292, Unknown=0, NotChecked=0, Total=1482 [2018-10-14 16:27:55,965 INFO L87 Difference]: Start difference. First operand 3870 states and 3930 transitions. Second operand 39 states. [2018-10-14 16:28:01,231 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:28:01,231 INFO L93 Difference]: Finished difference Result 10709 states and 10862 transitions. [2018-10-14 16:28:01,232 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-10-14 16:28:01,232 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 2111 [2018-10-14 16:28:01,234 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:28:01,244 INFO L225 Difference]: With dead ends: 10709 [2018-10-14 16:28:01,244 INFO L226 Difference]: Without dead ends: 10709 [2018-10-14 16:28:01,246 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 126 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4671 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=2912, Invalid=13344, Unknown=0, NotChecked=0, Total=16256 [2018-10-14 16:28:01,252 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10709 states. [2018-10-14 16:28:01,304 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10709 to 4271. [2018-10-14 16:28:01,305 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4271 states. [2018-10-14 16:28:01,309 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4271 states to 4271 states and 4340 transitions. [2018-10-14 16:28:01,309 INFO L78 Accepts]: Start accepts. Automaton has 4271 states and 4340 transitions. Word has length 2111 [2018-10-14 16:28:01,311 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:28:01,311 INFO L481 AbstractCegarLoop]: Abstraction has 4271 states and 4340 transitions. [2018-10-14 16:28:01,311 INFO L482 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-10-14 16:28:01,311 INFO L276 IsEmpty]: Start isEmpty. Operand 4271 states and 4340 transitions. [2018-10-14 16:28:01,353 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2126 [2018-10-14 16:28:01,354 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:28:01,355 INFO L375 BasicCegarLoop]: trace histogram [45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:28:01,355 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:28:01,355 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:28:01,356 INFO L82 PathProgramCache]: Analyzing trace with hash 441322824, now seen corresponding path program 27 times [2018-10-14 16:28:01,357 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:28:01,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:28:03,035 WARN L179 SmtUtils]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-10-14 16:28:03,631 WARN L179 SmtUtils]: Spent 119.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-10-14 16:28:22,039 INFO L134 CoverageAnalysis]: Checked inductivity of 37908 backedges. 0 proven. 33900 refuted. 0 times theorem prover too weak. 4008 trivial. 0 not checked. [2018-10-14 16:28:22,040 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:28:22,040 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [92] total 92 [2018-10-14 16:28:22,041 INFO L460 AbstractCegarLoop]: Interpolant automaton has 92 states [2018-10-14 16:28:22,041 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 92 interpolants. [2018-10-14 16:28:22,042 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=300, Invalid=8072, Unknown=0, NotChecked=0, Total=8372 [2018-10-14 16:28:22,042 INFO L87 Difference]: Start difference. First operand 4271 states and 4340 transitions. Second operand 92 states. [2018-10-14 16:28:27,796 WARN L179 SmtUtils]: Spent 209.00 ms on a formula simplification that was a NOOP. DAG size: 29 [2018-10-14 16:28:42,158 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:28:42,158 INFO L93 Difference]: Finished difference Result 4673 states and 4744 transitions. [2018-10-14 16:28:42,159 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 115 states. [2018-10-14 16:28:42,159 INFO L78 Accepts]: Start accepts. Automaton has 92 states. Word has length 2125 [2018-10-14 16:28:42,160 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:28:42,163 INFO L225 Difference]: With dead ends: 4673 [2018-10-14 16:28:42,163 INFO L226 Difference]: Without dead ends: 4673 [2018-10-14 16:28:42,166 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 25 SyntacticMatches, 10 SemanticMatches, 182 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10113 ImplicationChecksByTransitivity, 12.2s TimeCoverageRelationStatistics Valid=1185, Invalid=32487, Unknown=0, NotChecked=0, Total=33672 [2018-10-14 16:28:42,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4673 states. [2018-10-14 16:28:42,196 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4673 to 4640. [2018-10-14 16:28:42,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4640 states. [2018-10-14 16:28:42,200 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4640 states to 4640 states and 4711 transitions. [2018-10-14 16:28:42,200 INFO L78 Accepts]: Start accepts. Automaton has 4640 states and 4711 transitions. Word has length 2125 [2018-10-14 16:28:42,202 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:28:42,202 INFO L481 AbstractCegarLoop]: Abstraction has 4640 states and 4711 transitions. [2018-10-14 16:28:42,202 INFO L482 AbstractCegarLoop]: Interpolant automaton has 92 states. [2018-10-14 16:28:42,202 INFO L276 IsEmpty]: Start isEmpty. Operand 4640 states and 4711 transitions. [2018-10-14 16:28:42,252 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2495 [2018-10-14 16:28:42,252 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:28:42,253 INFO L375 BasicCegarLoop]: trace histogram [54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:28:42,254 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:28:42,254 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:28:42,255 INFO L82 PathProgramCache]: Analyzing trace with hash -248958513, now seen corresponding path program 28 times [2018-10-14 16:28:42,255 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:28:42,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:28:47,616 INFO L134 CoverageAnalysis]: Checked inductivity of 54163 backedges. 39206 proven. 10154 refuted. 0 times theorem prover too weak. 4803 trivial. 0 not checked. [2018-10-14 16:28:47,616 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:28:47,616 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [44] total 44 [2018-10-14 16:28:47,617 INFO L460 AbstractCegarLoop]: Interpolant automaton has 44 states [2018-10-14 16:28:47,618 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 44 interpolants. [2018-10-14 16:28:47,618 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=249, Invalid=1643, Unknown=0, NotChecked=0, Total=1892 [2018-10-14 16:28:47,618 INFO L87 Difference]: Start difference. First operand 4640 states and 4711 transitions. Second operand 44 states. [2018-10-14 16:28:50,582 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:28:50,582 INFO L93 Difference]: Finished difference Result 4673 states and 4744 transitions. [2018-10-14 16:28:50,583 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 74 states. [2018-10-14 16:28:50,583 INFO L78 Accepts]: Start accepts. Automaton has 44 states. Word has length 2494 [2018-10-14 16:28:50,586 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:28:50,589 INFO L225 Difference]: With dead ends: 4673 [2018-10-14 16:28:50,589 INFO L226 Difference]: Without dead ends: 4673 [2018-10-14 16:28:50,590 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2463 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=2059, Invalid=8861, Unknown=0, NotChecked=0, Total=10920 [2018-10-14 16:28:50,592 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 4673 states. [2018-10-14 16:28:50,613 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 4673 to 4661. [2018-10-14 16:28:50,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 4661 states. [2018-10-14 16:28:50,617 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 4661 states to 4661 states and 4732 transitions. [2018-10-14 16:28:50,618 INFO L78 Accepts]: Start accepts. Automaton has 4661 states and 4732 transitions. Word has length 2494 [2018-10-14 16:28:50,619 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:28:50,619 INFO L481 AbstractCegarLoop]: Abstraction has 4661 states and 4732 transitions. [2018-10-14 16:28:50,619 INFO L482 AbstractCegarLoop]: Interpolant automaton has 44 states. [2018-10-14 16:28:50,619 INFO L276 IsEmpty]: Start isEmpty. Operand 4661 states and 4732 transitions. [2018-10-14 16:28:50,656 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2516 [2018-10-14 16:28:50,656 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:28:50,657 INFO L375 BasicCegarLoop]: trace histogram [55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:28:50,657 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:28:50,657 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:28:50,658 INFO L82 PathProgramCache]: Analyzing trace with hash -1646396362, now seen corresponding path program 29 times [2018-10-14 16:28:50,659 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:28:50,782 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:28:54,199 INFO L134 CoverageAnalysis]: Checked inductivity of 55308 backedges. 16274 proven. 864 refuted. 0 times theorem prover too weak. 38170 trivial. 0 not checked. [2018-10-14 16:28:54,200 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:28:54,200 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43] total 43 [2018-10-14 16:28:54,201 INFO L460 AbstractCegarLoop]: Interpolant automaton has 43 states [2018-10-14 16:28:54,201 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2018-10-14 16:28:54,202 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=230, Invalid=1576, Unknown=0, NotChecked=0, Total=1806 [2018-10-14 16:28:54,202 INFO L87 Difference]: Start difference. First operand 4661 states and 4732 transitions. Second operand 43 states. [2018-10-14 16:28:59,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:28:59,760 INFO L93 Difference]: Finished difference Result 13548 states and 13733 transitions. [2018-10-14 16:28:59,760 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 111 states. [2018-10-14 16:28:59,760 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 2515 [2018-10-14 16:28:59,761 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:28:59,770 INFO L225 Difference]: With dead ends: 13548 [2018-10-14 16:28:59,770 INFO L226 Difference]: Without dead ends: 13548 [2018-10-14 16:28:59,771 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5825 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=3586, Invalid=16436, Unknown=0, NotChecked=0, Total=20022 [2018-10-14 16:28:59,777 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13548 states. [2018-10-14 16:28:59,820 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13548 to 5105. [2018-10-14 16:28:59,820 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5105 states. [2018-10-14 16:28:59,824 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5105 states to 5105 states and 5186 transitions. [2018-10-14 16:28:59,824 INFO L78 Accepts]: Start accepts. Automaton has 5105 states and 5186 transitions. Word has length 2515 [2018-10-14 16:28:59,825 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:28:59,826 INFO L481 AbstractCegarLoop]: Abstraction has 5105 states and 5186 transitions. [2018-10-14 16:28:59,826 INFO L482 AbstractCegarLoop]: Interpolant automaton has 43 states. [2018-10-14 16:28:59,826 INFO L276 IsEmpty]: Start isEmpty. Operand 5105 states and 5186 transitions. [2018-10-14 16:28:59,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2530 [2018-10-14 16:28:59,861 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:28:59,862 INFO L375 BasicCegarLoop]: trace histogram [55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:28:59,862 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:28:59,863 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:28:59,863 INFO L82 PathProgramCache]: Analyzing trace with hash -569961457, now seen corresponding path program 30 times [2018-10-14 16:28:59,864 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:29:00,194 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:29:24,559 INFO L134 CoverageAnalysis]: Checked inductivity of 56075 backedges. 0 proven. 50460 refuted. 0 times theorem prover too weak. 5615 trivial. 0 not checked. [2018-10-14 16:29:24,560 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:29:24,561 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-14 16:29:24,562 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-14 16:29:24,562 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-14 16:29:24,563 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=295, Invalid=8261, Unknown=0, NotChecked=0, Total=8556 [2018-10-14 16:29:24,563 INFO L87 Difference]: Start difference. First operand 5105 states and 5186 transitions. Second operand 93 states. [2018-10-14 16:29:45,118 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:29:45,118 INFO L93 Difference]: Finished difference Result 5540 states and 5623 transitions. [2018-10-14 16:29:45,118 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-10-14 16:29:45,118 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 2529 [2018-10-14 16:29:45,121 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:29:45,123 INFO L225 Difference]: With dead ends: 5540 [2018-10-14 16:29:45,123 INFO L226 Difference]: Without dead ends: 5540 [2018-10-14 16:29:45,124 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 25 SyntacticMatches, 2 SemanticMatches, 181 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9569 ImplicationChecksByTransitivity, 10.3s TimeCoverageRelationStatistics Valid=1126, Invalid=32180, Unknown=0, NotChecked=0, Total=33306 [2018-10-14 16:29:45,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5540 states. [2018-10-14 16:29:45,147 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5540 to 5509. [2018-10-14 16:29:45,147 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5509 states. [2018-10-14 16:29:45,151 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5509 states to 5509 states and 5592 transitions. [2018-10-14 16:29:45,151 INFO L78 Accepts]: Start accepts. Automaton has 5509 states and 5592 transitions. Word has length 2529 [2018-10-14 16:29:45,152 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:29:45,152 INFO L481 AbstractCegarLoop]: Abstraction has 5509 states and 5592 transitions. [2018-10-14 16:29:45,152 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-14 16:29:45,152 INFO L276 IsEmpty]: Start isEmpty. Operand 5509 states and 5592 transitions. [2018-10-14 16:29:45,197 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2934 [2018-10-14 16:29:45,197 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:29:45,198 INFO L375 BasicCegarLoop]: trace histogram [65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:29:45,198 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:29:45,199 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:29:45,199 INFO L82 PathProgramCache]: Analyzing trace with hash 1582670166, now seen corresponding path program 31 times [2018-10-14 16:29:45,200 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:29:45,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:29:51,614 INFO L134 CoverageAnalysis]: Checked inductivity of 77836 backedges. 57801 proven. 13510 refuted. 0 times theorem prover too weak. 6525 trivial. 0 not checked. [2018-10-14 16:29:51,615 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:29:51,615 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [48] total 48 [2018-10-14 16:29:51,616 INFO L460 AbstractCegarLoop]: Interpolant automaton has 48 states [2018-10-14 16:29:51,616 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2018-10-14 16:29:51,616 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=295, Invalid=1961, Unknown=0, NotChecked=0, Total=2256 [2018-10-14 16:29:51,617 INFO L87 Difference]: Start difference. First operand 5509 states and 5592 transitions. Second operand 48 states. [2018-10-14 16:29:55,552 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:29:55,552 INFO L93 Difference]: Finished difference Result 5542 states and 5625 transitions. [2018-10-14 16:29:55,552 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 81 states. [2018-10-14 16:29:55,553 INFO L78 Accepts]: Start accepts. Automaton has 48 states. Word has length 2933 [2018-10-14 16:29:55,555 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:29:55,558 INFO L225 Difference]: With dead ends: 5542 [2018-10-14 16:29:55,558 INFO L226 Difference]: Without dead ends: 5542 [2018-10-14 16:29:55,560 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2990 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=2472, Invalid=10638, Unknown=0, NotChecked=0, Total=13110 [2018-10-14 16:29:55,562 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 5542 states. [2018-10-14 16:29:55,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 5542 to 5530. [2018-10-14 16:29:55,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 5530 states. [2018-10-14 16:29:55,600 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 5530 states to 5530 states and 5613 transitions. [2018-10-14 16:29:55,600 INFO L78 Accepts]: Start accepts. Automaton has 5530 states and 5613 transitions. Word has length 2933 [2018-10-14 16:29:55,602 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:29:55,602 INFO L481 AbstractCegarLoop]: Abstraction has 5530 states and 5613 transitions. [2018-10-14 16:29:55,602 INFO L482 AbstractCegarLoop]: Interpolant automaton has 48 states. [2018-10-14 16:29:55,602 INFO L276 IsEmpty]: Start isEmpty. Operand 5530 states and 5613 transitions. [2018-10-14 16:29:55,652 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2955 [2018-10-14 16:29:55,653 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:29:55,654 INFO L375 BasicCegarLoop]: trace histogram [66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:29:55,654 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:29:55,654 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:29:55,655 INFO L82 PathProgramCache]: Analyzing trace with hash 1343229281, now seen corresponding path program 32 times [2018-10-14 16:29:55,655 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:29:55,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:30:00,302 INFO L134 CoverageAnalysis]: Checked inductivity of 79213 backedges. 21817 proven. 1032 refuted. 0 times theorem prover too weak. 56364 trivial. 0 not checked. [2018-10-14 16:30:00,302 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:30:00,302 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [47] total 47 [2018-10-14 16:30:00,303 INFO L460 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-10-14 16:30:00,304 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-10-14 16:30:00,304 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=274, Invalid=1888, Unknown=0, NotChecked=0, Total=2162 [2018-10-14 16:30:00,304 INFO L87 Difference]: Start difference. First operand 5530 states and 5613 transitions. Second operand 47 states. [2018-10-14 16:30:06,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:30:06,867 INFO L93 Difference]: Finished difference Result 16820 states and 17040 transitions. [2018-10-14 16:30:06,867 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 122 states. [2018-10-14 16:30:06,867 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 2954 [2018-10-14 16:30:06,869 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:30:06,881 INFO L225 Difference]: With dead ends: 16820 [2018-10-14 16:30:06,882 INFO L226 Difference]: Without dead ends: 16820 [2018-10-14 16:30:06,883 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 154 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7106 ImplicationChecksByTransitivity, 3.6s TimeCoverageRelationStatistics Valid=4331, Invalid=19849, Unknown=0, NotChecked=0, Total=24180 [2018-10-14 16:30:06,893 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 16820 states. [2018-10-14 16:30:06,963 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 16820 to 6017. [2018-10-14 16:30:06,963 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6017 states. [2018-10-14 16:30:06,968 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6017 states to 6017 states and 6111 transitions. [2018-10-14 16:30:06,968 INFO L78 Accepts]: Start accepts. Automaton has 6017 states and 6111 transitions. Word has length 2954 [2018-10-14 16:30:06,969 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:30:06,970 INFO L481 AbstractCegarLoop]: Abstraction has 6017 states and 6111 transitions. [2018-10-14 16:30:06,970 INFO L482 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-10-14 16:30:06,970 INFO L276 IsEmpty]: Start isEmpty. Operand 6017 states and 6111 transitions. [2018-10-14 16:30:07,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2969 [2018-10-14 16:30:07,019 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:30:07,020 INFO L375 BasicCegarLoop]: trace histogram [66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:30:07,021 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:30:07,021 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:30:07,021 INFO L82 PathProgramCache]: Analyzing trace with hash 2057453050, now seen corresponding path program 33 times [2018-10-14 16:30:07,022 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:30:07,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:30:15,160 WARN L179 SmtUtils]: Spent 131.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 24 [2018-10-14 16:30:43,976 INFO L134 CoverageAnalysis]: Checked inductivity of 80135 backedges. 0 proven. 73395 refuted. 0 times theorem prover too weak. 6740 trivial. 0 not checked. [2018-10-14 16:30:43,977 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:30:43,977 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [124] total 124 [2018-10-14 16:30:43,978 INFO L460 AbstractCegarLoop]: Interpolant automaton has 124 states [2018-10-14 16:30:43,979 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 124 interpolants. [2018-10-14 16:30:43,979 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=417, Invalid=14835, Unknown=0, NotChecked=0, Total=15252 [2018-10-14 16:30:43,979 INFO L87 Difference]: Start difference. First operand 6017 states and 6111 transitions. Second operand 124 states. [2018-10-14 16:31:21,544 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:31:21,544 INFO L93 Difference]: Finished difference Result 6529 states and 6625 transitions. [2018-10-14 16:31:21,545 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 152 states. [2018-10-14 16:31:21,545 INFO L78 Accepts]: Start accepts. Automaton has 124 states. Word has length 2968 [2018-10-14 16:31:21,547 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:31:21,550 INFO L225 Difference]: With dead ends: 6529 [2018-10-14 16:31:21,551 INFO L226 Difference]: Without dead ends: 6529 [2018-10-14 16:31:21,553 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 276 GetRequests, 23 SyntacticMatches, 4 SemanticMatches, 249 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18410 ImplicationChecksByTransitivity, 19.4s TimeCoverageRelationStatistics Valid=1714, Invalid=61036, Unknown=0, NotChecked=0, Total=62750 [2018-10-14 16:31:21,555 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6529 states. [2018-10-14 16:31:21,578 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6529 to 6456. [2018-10-14 16:31:21,578 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6456 states. [2018-10-14 16:31:21,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6456 states to 6456 states and 6552 transitions. [2018-10-14 16:31:21,583 INFO L78 Accepts]: Start accepts. Automaton has 6456 states and 6552 transitions. Word has length 2968 [2018-10-14 16:31:21,584 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:31:21,584 INFO L481 AbstractCegarLoop]: Abstraction has 6456 states and 6552 transitions. [2018-10-14 16:31:21,584 INFO L482 AbstractCegarLoop]: Interpolant automaton has 124 states. [2018-10-14 16:31:21,584 INFO L276 IsEmpty]: Start isEmpty. Operand 6456 states and 6552 transitions. [2018-10-14 16:31:21,640 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3408 [2018-10-14 16:31:21,641 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:31:21,642 INFO L375 BasicCegarLoop]: trace histogram [77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:31:21,642 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:31:21,642 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:31:21,643 INFO L82 PathProgramCache]: Analyzing trace with hash -1407576145, now seen corresponding path program 34 times [2018-10-14 16:31:21,643 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:31:21,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:31:30,772 INFO L134 CoverageAnalysis]: Checked inductivity of 108528 backedges. 82372 proven. 17543 refuted. 0 times theorem prover too weak. 8613 trivial. 0 not checked. [2018-10-14 16:31:30,773 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:31:30,773 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [52] total 52 [2018-10-14 16:31:30,775 INFO L460 AbstractCegarLoop]: Interpolant automaton has 52 states [2018-10-14 16:31:30,775 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2018-10-14 16:31:30,775 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=345, Invalid=2307, Unknown=0, NotChecked=0, Total=2652 [2018-10-14 16:31:30,775 INFO L87 Difference]: Start difference. First operand 6456 states and 6552 transitions. Second operand 52 states. [2018-10-14 16:31:35,438 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:31:35,439 INFO L93 Difference]: Finished difference Result 6489 states and 6585 transitions. [2018-10-14 16:31:35,439 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 88 states. [2018-10-14 16:31:35,439 INFO L78 Accepts]: Start accepts. Automaton has 52 states. Word has length 3407 [2018-10-14 16:31:35,442 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:31:35,446 INFO L225 Difference]: With dead ends: 6489 [2018-10-14 16:31:35,446 INFO L226 Difference]: Without dead ends: 6489 [2018-10-14 16:31:35,448 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 123 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3568 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=2923, Invalid=12577, Unknown=0, NotChecked=0, Total=15500 [2018-10-14 16:31:35,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 6489 states. [2018-10-14 16:31:35,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 6489 to 6477. [2018-10-14 16:31:35,475 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 6477 states. [2018-10-14 16:31:35,480 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6477 states to 6477 states and 6573 transitions. [2018-10-14 16:31:35,480 INFO L78 Accepts]: Start accepts. Automaton has 6477 states and 6573 transitions. Word has length 3407 [2018-10-14 16:31:35,481 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:31:35,481 INFO L481 AbstractCegarLoop]: Abstraction has 6477 states and 6573 transitions. [2018-10-14 16:31:35,481 INFO L482 AbstractCegarLoop]: Interpolant automaton has 52 states. [2018-10-14 16:31:35,481 INFO L276 IsEmpty]: Start isEmpty. Operand 6477 states and 6573 transitions. [2018-10-14 16:31:35,545 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3429 [2018-10-14 16:31:35,545 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:31:35,547 INFO L375 BasicCegarLoop]: trace histogram [78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:31:35,547 INFO L424 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:31:35,547 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:31:35,548 INFO L82 PathProgramCache]: Analyzing trace with hash 802060154, now seen corresponding path program 35 times [2018-10-14 16:31:35,548 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:31:35,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:31:41,709 INFO L134 CoverageAnalysis]: Checked inductivity of 110158 backedges. 28493 proven. 1214 refuted. 0 times theorem prover too weak. 80451 trivial. 0 not checked. [2018-10-14 16:31:41,709 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:31:41,710 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [51] total 51 [2018-10-14 16:31:41,711 INFO L460 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-10-14 16:31:41,711 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-10-14 16:31:41,711 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=322, Invalid=2228, Unknown=0, NotChecked=0, Total=2550 [2018-10-14 16:31:41,712 INFO L87 Difference]: Start difference. First operand 6477 states and 6573 transitions. Second operand 51 states. [2018-10-14 16:31:49,146 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:31:49,147 INFO L93 Difference]: Finished difference Result 20553 states and 20811 transitions. [2018-10-14 16:31:49,147 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 133 states. [2018-10-14 16:31:49,147 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 3428 [2018-10-14 16:31:49,149 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:31:49,168 INFO L225 Difference]: With dead ends: 20553 [2018-10-14 16:31:49,169 INFO L226 Difference]: Without dead ends: 20553 [2018-10-14 16:31:49,172 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 171 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 168 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8514 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=5147, Invalid=23583, Unknown=0, NotChecked=0, Total=28730 [2018-10-14 16:31:49,181 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20553 states. [2018-10-14 16:31:49,255 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20553 to 7007. [2018-10-14 16:31:49,255 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7007 states. [2018-10-14 16:31:49,260 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7007 states to 7007 states and 7115 transitions. [2018-10-14 16:31:49,261 INFO L78 Accepts]: Start accepts. Automaton has 7007 states and 7115 transitions. Word has length 3428 [2018-10-14 16:31:49,262 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:31:49,262 INFO L481 AbstractCegarLoop]: Abstraction has 7007 states and 7115 transitions. [2018-10-14 16:31:49,262 INFO L482 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-10-14 16:31:49,262 INFO L276 IsEmpty]: Start isEmpty. Operand 7007 states and 7115 transitions. [2018-10-14 16:31:49,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3443 [2018-10-14 16:31:49,330 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:31:49,331 INFO L375 BasicCegarLoop]: trace histogram [78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 78, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:31:49,332 INFO L424 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:31:49,332 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:31:49,333 INFO L82 PathProgramCache]: Analyzing trace with hash -1773369261, now seen corresponding path program 36 times [2018-10-14 16:31:49,334 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:31:49,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:32:33,267 INFO L134 CoverageAnalysis]: Checked inductivity of 111249 backedges. 0 proven. 101534 refuted. 0 times theorem prover too weak. 9715 trivial. 0 not checked. [2018-10-14 16:32:33,267 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:32:33,268 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [119] total 119 [2018-10-14 16:32:33,269 INFO L460 AbstractCegarLoop]: Interpolant automaton has 119 states [2018-10-14 16:32:33,269 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 119 interpolants. [2018-10-14 16:32:33,270 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=390, Invalid=13652, Unknown=0, NotChecked=0, Total=14042 [2018-10-14 16:32:33,270 INFO L87 Difference]: Start difference. First operand 7007 states and 7115 transitions. Second operand 119 states. [2018-10-14 16:33:13,862 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:33:13,862 INFO L93 Difference]: Finished difference Result 7550 states and 7660 transitions. [2018-10-14 16:33:13,863 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 151 states. [2018-10-14 16:33:13,863 INFO L78 Accepts]: Start accepts. Automaton has 119 states. Word has length 3442 [2018-10-14 16:33:13,866 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:33:13,869 INFO L225 Difference]: With dead ends: 7550 [2018-10-14 16:33:13,869 INFO L226 Difference]: Without dead ends: 7550 [2018-10-14 16:33:13,872 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 266 GetRequests, 27 SyntacticMatches, 2 SemanticMatches, 237 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16683 ImplicationChecksByTransitivity, 17.1s TimeCoverageRelationStatistics Valid=1548, Invalid=55334, Unknown=0, NotChecked=0, Total=56882 [2018-10-14 16:33:13,875 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 7550 states. [2018-10-14 16:33:13,906 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 7550 to 7481. [2018-10-14 16:33:13,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 7481 states. [2018-10-14 16:33:13,913 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7481 states to 7481 states and 7591 transitions. [2018-10-14 16:33:13,913 INFO L78 Accepts]: Start accepts. Automaton has 7481 states and 7591 transitions. Word has length 3442 [2018-10-14 16:33:13,915 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:33:13,915 INFO L481 AbstractCegarLoop]: Abstraction has 7481 states and 7591 transitions. [2018-10-14 16:33:13,916 INFO L482 AbstractCegarLoop]: Interpolant automaton has 119 states. [2018-10-14 16:33:13,916 INFO L276 IsEmpty]: Start isEmpty. Operand 7481 states and 7591 transitions. [2018-10-14 16:33:13,994 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 3917 [2018-10-14 16:33:13,994 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:33:13,996 INFO L375 BasicCegarLoop]: trace histogram [90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 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] [2018-10-14 16:33:13,996 INFO L424 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:33:13,996 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:33:13,997 INFO L82 PathProgramCache]: Analyzing trace with hash 1992830316, now seen corresponding path program 37 times [2018-10-14 16:33:13,997 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:33:14,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat