java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data --generate-csv --csv-dir csv -tc ../../../trunk/examples/toolchains/AutomizerBplTransformed.xml -s ../../../trunk/examples/settings/heapseparator/heapsep-2018-09-18.epf -i ../../../trunk/examples/programs/20170304-DifficultPathPrograms/nested1.i_4.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-d769cf3 [2018-10-15 15:32:42,947 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-15 15:32:42,949 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-15 15:32:42,967 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-15 15:32:42,968 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-15 15:32:42,970 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-15 15:32:42,971 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-15 15:32:42,974 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-15 15:32:42,976 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-15 15:32:42,984 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-15 15:32:42,986 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-15 15:32:42,986 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-15 15:32:42,987 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-15 15:32:42,989 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-15 15:32:42,990 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-15 15:32:42,990 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-15 15:32:42,994 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-15 15:32:42,995 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-15 15:32:43,000 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-15 15:32:43,004 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-15 15:32:43,005 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-15 15:32:43,009 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-15 15:32:43,013 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-15 15:32:43,014 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-15 15:32:43,015 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-15 15:32:43,016 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-15 15:32:43,017 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-15 15:32:43,018 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-15 15:32:43,018 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-15 15:32:43,019 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-15 15:32:43,020 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-15 15:32:43,020 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-15 15:32:43,020 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-15 15:32:43,021 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-15 15:32:43,022 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-15 15:32:43,022 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-15 15:32:43,023 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-15 15:32:43,032 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-15 15:32:43,032 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-15 15:32:43,033 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-15 15:32:43,033 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-15 15:32:43,033 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-15 15:32:43,033 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-15 15:32:43,034 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-15 15:32:43,034 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-15 15:32:43,034 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-15 15:32:43,035 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-15 15:32:43,035 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-15 15:32:43,035 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-15 15:32:43,035 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-15 15:32:43,036 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-15 15:32:43,036 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-15 15:32:43,094 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-15 15:32:43,109 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-15 15:32:43,116 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-15 15:32:43,118 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-15 15:32:43,118 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-15 15:32:43,119 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/nested1.i_4.bpl [2018-10-15 15:32:43,119 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/nested1.i_4.bpl' [2018-10-15 15:32:43,164 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-15 15:32:43,165 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-10-15 15:32:43,166 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-15 15:32:43,166 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-15 15:32:43,166 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-15 15:32:43,188 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.10 03:32:43" (1/1) ... [2018-10-15 15:32:43,190 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.10 03:32:43" (1/1) ... [2018-10-15 15:32:43,200 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.10 03:32:43" (1/1) ... [2018-10-15 15:32:43,201 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.10 03:32:43" (1/1) ... [2018-10-15 15:32:43,204 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.10 03:32:43" (1/1) ... [2018-10-15 15:32:43,205 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.10 03:32:43" (1/1) ... [2018-10-15 15:32:43,206 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.10 03:32:43" (1/1) ... [2018-10-15 15:32:43,208 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-15 15:32:43,212 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-15 15:32:43,212 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-15 15:32:43,212 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-15 15:32:43,213 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.10 03:32:43" (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-15 15:32:43,286 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-15 15:32:43,286 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-15 15:32:43,622 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-15 15:32:43,623 INFO L202 PluginConnector]: Adding new model nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.10 03:32:43 BoogieIcfgContainer [2018-10-15 15:32:43,624 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-15 15:32:43,624 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2018-10-15 15:32:43,624 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2018-10-15 15:32:43,626 INFO L276 PluginConnector]: IcfgTransformer initialized [2018-10-15 15:32:43,632 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.10 03:32:43" (1/1) ... [2018-10-15 15:32:43,638 WARN L219 ansformationObserver]: HeapSeparator: input icfg has no '#valid' array -- returning unchanged Icfg! [2018-10-15 15:32:43,658 INFO L202 PluginConnector]: Adding new model nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 15.10 03:32:43 BasicIcfg [2018-10-15 15:32:43,658 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2018-10-15 15:32:43,659 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-15 15:32:43,659 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-15 15:32:43,663 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-15 15:32:43,664 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 15.10 03:32:43" (1/3) ... [2018-10-15 15:32:43,665 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@39c85953 and model type nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.10 03:32:43, skipping insertion in model container [2018-10-15 15:32:43,665 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.10 03:32:43" (2/3) ... [2018-10-15 15:32:43,666 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@39c85953 and model type nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 15.10 03:32:43, skipping insertion in model container [2018-10-15 15:32:43,666 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 15.10 03:32:43" (3/3) ... [2018-10-15 15:32:43,668 INFO L112 eAbstractionObserver]: Analyzing ICFG nested1.i_4.bplleft_unchanged_by_heapseparator [2018-10-15 15:32:43,680 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-15 15:32:43,699 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-15 15:32:43,723 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-15 15:32:43,755 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-15 15:32:43,756 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-15 15:32:43,757 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-15 15:32:43,757 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-15 15:32:43,757 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-15 15:32:43,757 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-15 15:32:43,757 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-15 15:32:43,757 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-15 15:32:43,758 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-15 15:32:43,772 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states. [2018-10-15 15:32:43,781 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-10-15 15:32:43,781 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:43,782 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:43,784 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:43,790 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:43,790 INFO L82 PathProgramCache]: Analyzing trace with hash 630062764, now seen corresponding path program 1 times [2018-10-15 15:32:43,847 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:43,890 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:43,994 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-15 15:32:43,996 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-15 15:32:43,997 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-15 15:32:44,000 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-15 15:32:44,013 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-15 15:32:44,014 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-15 15:32:44,017 INFO L87 Difference]: Start difference. First operand 22 states. Second operand 3 states. [2018-10-15 15:32:44,100 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:44,100 INFO L93 Difference]: Finished difference Result 32 states and 34 transitions. [2018-10-15 15:32:44,101 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-15 15:32:44,102 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 12 [2018-10-15 15:32:44,103 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:44,114 INFO L225 Difference]: With dead ends: 32 [2018-10-15 15:32:44,114 INFO L226 Difference]: Without dead ends: 32 [2018-10-15 15:32:44,116 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-15 15:32:44,132 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2018-10-15 15:32:44,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 24. [2018-10-15 15:32:44,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 24 states. [2018-10-15 15:32:44,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 25 transitions. [2018-10-15 15:32:44,148 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 25 transitions. Word has length 12 [2018-10-15 15:32:44,149 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:44,149 INFO L481 AbstractCegarLoop]: Abstraction has 24 states and 25 transitions. [2018-10-15 15:32:44,149 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-15 15:32:44,149 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 25 transitions. [2018-10-15 15:32:44,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-15 15:32:44,150 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:44,150 INFO L375 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:44,150 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:44,151 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:44,151 INFO L82 PathProgramCache]: Analyzing trace with hash 1322871095, now seen corresponding path program 1 times [2018-10-15 15:32:44,152 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:44,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:44,198 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:44,198 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-15 15:32:44,198 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-15 15:32:44,200 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-15 15:32:44,200 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-15 15:32:44,201 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-15 15:32:44,201 INFO L87 Difference]: Start difference. First operand 24 states and 25 transitions. Second operand 3 states. [2018-10-15 15:32:44,313 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:44,313 INFO L93 Difference]: Finished difference Result 29 states and 30 transitions. [2018-10-15 15:32:44,314 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-15 15:32:44,314 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 20 [2018-10-15 15:32:44,314 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:44,315 INFO L225 Difference]: With dead ends: 29 [2018-10-15 15:32:44,315 INFO L226 Difference]: Without dead ends: 29 [2018-10-15 15:32:44,316 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-15 15:32:44,317 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2018-10-15 15:32:44,320 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 26. [2018-10-15 15:32:44,320 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-10-15 15:32:44,321 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 27 transitions. [2018-10-15 15:32:44,321 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 27 transitions. Word has length 20 [2018-10-15 15:32:44,321 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:44,322 INFO L481 AbstractCegarLoop]: Abstraction has 26 states and 27 transitions. [2018-10-15 15:32:44,322 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-15 15:32:44,322 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 27 transitions. [2018-10-15 15:32:44,323 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-15 15:32:44,323 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:44,323 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:44,323 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:44,324 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:44,324 INFO L82 PathProgramCache]: Analyzing trace with hash -706610159, now seen corresponding path program 1 times [2018-10-15 15:32:44,325 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:44,347 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:44,606 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:44,607 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:44,607 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5] total 5 [2018-10-15 15:32:44,607 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-15 15:32:44,608 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-15 15:32:44,608 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-10-15 15:32:44,608 INFO L87 Difference]: Start difference. First operand 26 states and 27 transitions. Second operand 5 states. [2018-10-15 15:32:44,891 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:44,891 INFO L93 Difference]: Finished difference Result 34 states and 35 transitions. [2018-10-15 15:32:44,891 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-15 15:32:44,892 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 25 [2018-10-15 15:32:44,892 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:44,893 INFO L225 Difference]: With dead ends: 34 [2018-10-15 15:32:44,893 INFO L226 Difference]: Without dead ends: 34 [2018-10-15 15:32:44,894 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2018-10-15 15:32:44,894 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-10-15 15:32:44,897 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 31. [2018-10-15 15:32:44,897 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-10-15 15:32:44,898 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-10-15 15:32:44,899 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 25 [2018-10-15 15:32:44,899 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:44,899 INFO L481 AbstractCegarLoop]: Abstraction has 31 states and 32 transitions. [2018-10-15 15:32:44,899 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-15 15:32:44,899 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 32 transitions. [2018-10-15 15:32:44,900 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-10-15 15:32:44,900 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:44,901 INFO L375 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:44,901 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:44,901 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:44,901 INFO L82 PathProgramCache]: Analyzing trace with hash 191177079, now seen corresponding path program 2 times [2018-10-15 15:32:44,902 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:44,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:45,180 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 2 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:45,181 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:45,181 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2018-10-15 15:32:45,181 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-15 15:32:45,182 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-15 15:32:45,182 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-10-15 15:32:45,183 INFO L87 Difference]: Start difference. First operand 31 states and 32 transitions. Second operand 7 states. [2018-10-15 15:32:45,489 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:45,490 INFO L93 Difference]: Finished difference Result 39 states and 40 transitions. [2018-10-15 15:32:45,495 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-15 15:32:45,495 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 30 [2018-10-15 15:32:45,495 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:45,496 INFO L225 Difference]: With dead ends: 39 [2018-10-15 15:32:45,496 INFO L226 Difference]: Without dead ends: 39 [2018-10-15 15:32:45,497 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2018-10-15 15:32:45,497 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-10-15 15:32:45,502 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 36. [2018-10-15 15:32:45,502 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2018-10-15 15:32:45,503 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 37 transitions. [2018-10-15 15:32:45,503 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 37 transitions. Word has length 30 [2018-10-15 15:32:45,505 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:45,505 INFO L481 AbstractCegarLoop]: Abstraction has 36 states and 37 transitions. [2018-10-15 15:32:45,505 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-15 15:32:45,506 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 37 transitions. [2018-10-15 15:32:45,508 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-10-15 15:32:45,508 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:45,509 INFO L375 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:45,510 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:45,510 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:45,510 INFO L82 PathProgramCache]: Analyzing trace with hash -1591776303, now seen corresponding path program 3 times [2018-10-15 15:32:45,511 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:45,531 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:45,774 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:45,775 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:45,775 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-15 15:32:45,776 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-15 15:32:45,776 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-15 15:32:45,776 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-10-15 15:32:45,777 INFO L87 Difference]: Start difference. First operand 36 states and 37 transitions. Second operand 9 states. [2018-10-15 15:32:46,180 WARN L179 SmtUtils]: Spent 109.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-10-15 15:32:46,435 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:46,435 INFO L93 Difference]: Finished difference Result 44 states and 45 transitions. [2018-10-15 15:32:46,436 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-10-15 15:32:46,437 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 35 [2018-10-15 15:32:46,437 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:46,438 INFO L225 Difference]: With dead ends: 44 [2018-10-15 15:32:46,438 INFO L226 Difference]: Without dead ends: 44 [2018-10-15 15:32:46,439 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2018-10-15 15:32:46,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2018-10-15 15:32:46,443 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 41. [2018-10-15 15:32:46,443 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-10-15 15:32:46,444 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 42 transitions. [2018-10-15 15:32:46,444 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 42 transitions. Word has length 35 [2018-10-15 15:32:46,445 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:46,445 INFO L481 AbstractCegarLoop]: Abstraction has 41 states and 42 transitions. [2018-10-15 15:32:46,445 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-15 15:32:46,445 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 42 transitions. [2018-10-15 15:32:46,446 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-10-15 15:32:46,447 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:46,447 INFO L375 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:46,447 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:46,447 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:46,448 INFO L82 PathProgramCache]: Analyzing trace with hash 1876396471, now seen corresponding path program 4 times [2018-10-15 15:32:46,449 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:46,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:46,770 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 2 proven. 38 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:46,771 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:46,771 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2018-10-15 15:32:46,772 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-15 15:32:46,772 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-15 15:32:46,772 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=91, Unknown=0, NotChecked=0, Total=110 [2018-10-15 15:32:46,773 INFO L87 Difference]: Start difference. First operand 41 states and 42 transitions. Second operand 11 states. [2018-10-15 15:32:47,231 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:47,232 INFO L93 Difference]: Finished difference Result 49 states and 50 transitions. [2018-10-15 15:32:47,242 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-15 15:32:47,242 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 40 [2018-10-15 15:32:47,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:47,243 INFO L225 Difference]: With dead ends: 49 [2018-10-15 15:32:47,243 INFO L226 Difference]: Without dead ends: 49 [2018-10-15 15:32:47,244 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2018-10-15 15:32:47,244 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-10-15 15:32:47,249 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 46. [2018-10-15 15:32:47,249 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-10-15 15:32:47,250 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 47 transitions. [2018-10-15 15:32:47,251 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 47 transitions. Word has length 40 [2018-10-15 15:32:47,251 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:47,251 INFO L481 AbstractCegarLoop]: Abstraction has 46 states and 47 transitions. [2018-10-15 15:32:47,251 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-15 15:32:47,252 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 47 transitions. [2018-10-15 15:32:47,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2018-10-15 15:32:47,253 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:47,253 INFO L375 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:47,253 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:47,254 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:47,254 INFO L82 PathProgramCache]: Analyzing trace with hash 421800849, now seen corresponding path program 5 times [2018-10-15 15:32:47,255 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:47,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:47,512 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 2 proven. 60 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:47,512 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:47,512 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-15 15:32:47,513 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-15 15:32:47,513 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-15 15:32:47,513 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-10-15 15:32:47,514 INFO L87 Difference]: Start difference. First operand 46 states and 47 transitions. Second operand 13 states. [2018-10-15 15:32:48,238 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:48,239 INFO L93 Difference]: Finished difference Result 54 states and 55 transitions. [2018-10-15 15:32:48,242 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-15 15:32:48,242 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 45 [2018-10-15 15:32:48,244 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:48,244 INFO L225 Difference]: With dead ends: 54 [2018-10-15 15:32:48,244 INFO L226 Difference]: Without dead ends: 54 [2018-10-15 15:32:48,245 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=63, Invalid=443, Unknown=0, NotChecked=0, Total=506 [2018-10-15 15:32:48,246 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-10-15 15:32:48,250 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 51. [2018-10-15 15:32:48,250 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-10-15 15:32:48,251 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 52 transitions. [2018-10-15 15:32:48,251 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 52 transitions. Word has length 45 [2018-10-15 15:32:48,252 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:48,252 INFO L481 AbstractCegarLoop]: Abstraction has 51 states and 52 transitions. [2018-10-15 15:32:48,252 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-15 15:32:48,252 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 52 transitions. [2018-10-15 15:32:48,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-10-15 15:32:48,253 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:48,254 INFO L375 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:48,254 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:48,254 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:48,254 INFO L82 PathProgramCache]: Analyzing trace with hash -1886084617, now seen corresponding path program 6 times [2018-10-15 15:32:48,255 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:48,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:48,691 INFO L134 CoverageAnalysis]: Checked inductivity of 89 backedges. 2 proven. 87 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:48,691 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:48,691 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-10-15 15:32:48,692 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-15 15:32:48,692 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-15 15:32:48,692 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-10-15 15:32:48,693 INFO L87 Difference]: Start difference. First operand 51 states and 52 transitions. Second operand 15 states. [2018-10-15 15:32:49,172 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:49,172 INFO L93 Difference]: Finished difference Result 59 states and 60 transitions. [2018-10-15 15:32:49,179 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-10-15 15:32:49,179 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 50 [2018-10-15 15:32:49,180 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:49,180 INFO L225 Difference]: With dead ends: 59 [2018-10-15 15:32:49,180 INFO L226 Difference]: Without dead ends: 59 [2018-10-15 15:32:49,181 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=75, Invalid=627, Unknown=0, NotChecked=0, Total=702 [2018-10-15 15:32:49,181 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2018-10-15 15:32:49,186 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 56. [2018-10-15 15:32:49,187 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-10-15 15:32:49,188 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 57 transitions. [2018-10-15 15:32:49,192 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 57 transitions. Word has length 50 [2018-10-15 15:32:49,193 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:49,193 INFO L481 AbstractCegarLoop]: Abstraction has 56 states and 57 transitions. [2018-10-15 15:32:49,193 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-15 15:32:49,193 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 57 transitions. [2018-10-15 15:32:49,196 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2018-10-15 15:32:49,196 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:49,197 INFO L375 BasicCegarLoop]: trace histogram [8, 7, 7, 7, 7, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:49,197 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:49,197 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:49,197 INFO L82 PathProgramCache]: Analyzing trace with hash -1458816175, now seen corresponding path program 7 times [2018-10-15 15:32:49,198 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:49,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:49,549 INFO L134 CoverageAnalysis]: Checked inductivity of 121 backedges. 2 proven. 119 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:49,549 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:49,549 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-15 15:32:49,550 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-15 15:32:49,550 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-15 15:32:49,551 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=241, Unknown=0, NotChecked=0, Total=272 [2018-10-15 15:32:49,551 INFO L87 Difference]: Start difference. First operand 56 states and 57 transitions. Second operand 17 states. [2018-10-15 15:32:50,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:50,383 INFO L93 Difference]: Finished difference Result 64 states and 65 transitions. [2018-10-15 15:32:50,384 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-15 15:32:50,384 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 55 [2018-10-15 15:32:50,385 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:50,386 INFO L225 Difference]: With dead ends: 64 [2018-10-15 15:32:50,386 INFO L226 Difference]: Without dead ends: 64 [2018-10-15 15:32:50,387 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=87, Invalid=843, Unknown=0, NotChecked=0, Total=930 [2018-10-15 15:32:50,387 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2018-10-15 15:32:50,391 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 61. [2018-10-15 15:32:50,391 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 61 states. [2018-10-15 15:32:50,392 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 62 transitions. [2018-10-15 15:32:50,392 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 62 transitions. Word has length 55 [2018-10-15 15:32:50,392 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:50,393 INFO L481 AbstractCegarLoop]: Abstraction has 61 states and 62 transitions. [2018-10-15 15:32:50,393 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-15 15:32:50,393 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 62 transitions. [2018-10-15 15:32:50,394 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-10-15 15:32:50,394 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:50,394 INFO L375 BasicCegarLoop]: trace histogram [9, 8, 8, 8, 8, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:50,394 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:50,395 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:50,395 INFO L82 PathProgramCache]: Analyzing trace with hash -1862243785, now seen corresponding path program 8 times [2018-10-15 15:32:50,396 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:50,406 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:50,913 INFO L134 CoverageAnalysis]: Checked inductivity of 158 backedges. 2 proven. 156 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:50,913 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:50,913 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-10-15 15:32:50,913 INFO L460 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-15 15:32:50,914 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-15 15:32:50,914 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=307, Unknown=0, NotChecked=0, Total=342 [2018-10-15 15:32:50,914 INFO L87 Difference]: Start difference. First operand 61 states and 62 transitions. Second operand 19 states. [2018-10-15 15:32:51,852 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:51,852 INFO L93 Difference]: Finished difference Result 69 states and 70 transitions. [2018-10-15 15:32:51,853 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-10-15 15:32:51,853 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 60 [2018-10-15 15:32:51,854 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:51,854 INFO L225 Difference]: With dead ends: 69 [2018-10-15 15:32:51,854 INFO L226 Difference]: Without dead ends: 69 [2018-10-15 15:32:51,855 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=99, Invalid=1091, Unknown=0, NotChecked=0, Total=1190 [2018-10-15 15:32:51,856 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2018-10-15 15:32:51,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 66. [2018-10-15 15:32:51,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 66 states. [2018-10-15 15:32:51,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 67 transitions. [2018-10-15 15:32:51,860 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 67 transitions. Word has length 60 [2018-10-15 15:32:51,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:51,860 INFO L481 AbstractCegarLoop]: Abstraction has 66 states and 67 transitions. [2018-10-15 15:32:51,861 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-15 15:32:51,861 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 67 transitions. [2018-10-15 15:32:51,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-10-15 15:32:51,862 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:51,862 INFO L375 BasicCegarLoop]: trace histogram [10, 9, 9, 9, 9, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:51,862 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:51,862 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:51,862 INFO L82 PathProgramCache]: Analyzing trace with hash -1997300975, now seen corresponding path program 9 times [2018-10-15 15:32:51,863 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:51,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:52,468 INFO L134 CoverageAnalysis]: Checked inductivity of 200 backedges. 2 proven. 198 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-15 15:32:52,468 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:52,468 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-15 15:32:52,469 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-15 15:32:52,469 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-15 15:32:52,469 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=381, Unknown=0, NotChecked=0, Total=420 [2018-10-15 15:32:52,469 INFO L87 Difference]: Start difference. First operand 66 states and 67 transitions. Second operand 21 states. [2018-10-15 15:32:53,690 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:53,690 INFO L93 Difference]: Finished difference Result 74 states and 75 transitions. [2018-10-15 15:32:53,700 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-15 15:32:53,700 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 65 [2018-10-15 15:32:53,700 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:53,701 INFO L225 Difference]: With dead ends: 74 [2018-10-15 15:32:53,701 INFO L226 Difference]: Without dead ends: 74 [2018-10-15 15:32:53,702 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 153 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=111, Invalid=1371, Unknown=0, NotChecked=0, Total=1482 [2018-10-15 15:32:53,702 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2018-10-15 15:32:53,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2018-10-15 15:32:53,706 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71 states. [2018-10-15 15:32:53,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 72 transitions. [2018-10-15 15:32:53,707 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 72 transitions. Word has length 65 [2018-10-15 15:32:53,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:53,709 INFO L481 AbstractCegarLoop]: Abstraction has 71 states and 72 transitions. [2018-10-15 15:32:53,709 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-15 15:32:53,709 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 72 transitions. [2018-10-15 15:32:53,710 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2018-10-15 15:32:53,713 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:53,713 INFO L375 BasicCegarLoop]: trace histogram [11, 10, 10, 10, 10, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:53,713 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:53,714 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:53,714 INFO L82 PathProgramCache]: Analyzing trace with hash -310451593, now seen corresponding path program 10 times [2018-10-15 15:32:53,717 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:53,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:53,988 INFO L134 CoverageAnalysis]: Checked inductivity of 247 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 245 trivial. 0 not checked. [2018-10-15 15:32:53,989 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:53,989 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5] total 5 [2018-10-15 15:32:53,989 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-15 15:32:53,989 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-15 15:32:53,989 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-10-15 15:32:53,990 INFO L87 Difference]: Start difference. First operand 71 states and 72 transitions. Second operand 5 states. [2018-10-15 15:32:54,039 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:54,039 INFO L93 Difference]: Finished difference Result 184 states and 187 transitions. [2018-10-15 15:32:54,039 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-15 15:32:54,040 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 70 [2018-10-15 15:32:54,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:54,042 INFO L225 Difference]: With dead ends: 184 [2018-10-15 15:32:54,042 INFO L226 Difference]: Without dead ends: 184 [2018-10-15 15:32:54,042 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2018-10-15 15:32:54,044 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2018-10-15 15:32:54,057 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 129. [2018-10-15 15:32:54,057 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 129 states. [2018-10-15 15:32:54,059 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 131 transitions. [2018-10-15 15:32:54,059 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 131 transitions. Word has length 70 [2018-10-15 15:32:54,059 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:54,059 INFO L481 AbstractCegarLoop]: Abstraction has 129 states and 131 transitions. [2018-10-15 15:32:54,059 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-15 15:32:54,060 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 131 transitions. [2018-10-15 15:32:54,064 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 129 [2018-10-15 15:32:54,064 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:54,064 INFO L375 BasicCegarLoop]: trace histogram [22, 20, 20, 20, 20, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:54,065 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:54,065 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:54,065 INFO L82 PathProgramCache]: Analyzing trace with hash 1579639426, now seen corresponding path program 11 times [2018-10-15 15:32:54,066 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:54,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:54,416 INFO L134 CoverageAnalysis]: Checked inductivity of 1042 backedges. 0 proven. 552 refuted. 0 times theorem prover too weak. 490 trivial. 0 not checked. [2018-10-15 15:32:54,416 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:54,416 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2018-10-15 15:32:54,417 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-15 15:32:54,417 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-15 15:32:54,417 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-10-15 15:32:54,417 INFO L87 Difference]: Start difference. First operand 129 states and 131 transitions. Second operand 7 states. [2018-10-15 15:32:54,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:54,514 INFO L93 Difference]: Finished difference Result 242 states and 246 transitions. [2018-10-15 15:32:54,514 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-15 15:32:54,515 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 128 [2018-10-15 15:32:54,515 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:54,517 INFO L225 Difference]: With dead ends: 242 [2018-10-15 15:32:54,517 INFO L226 Difference]: Without dead ends: 242 [2018-10-15 15:32:54,518 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2018-10-15 15:32:54,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 242 states. [2018-10-15 15:32:54,531 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 242 to 187. [2018-10-15 15:32:54,531 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 187 states. [2018-10-15 15:32:54,532 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 190 transitions. [2018-10-15 15:32:54,532 INFO L78 Accepts]: Start accepts. Automaton has 187 states and 190 transitions. Word has length 128 [2018-10-15 15:32:54,533 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:54,533 INFO L481 AbstractCegarLoop]: Abstraction has 187 states and 190 transitions. [2018-10-15 15:32:54,533 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-15 15:32:54,533 INFO L276 IsEmpty]: Start isEmpty. Operand 187 states and 190 transitions. [2018-10-15 15:32:54,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 187 [2018-10-15 15:32:54,535 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:54,535 INFO L375 BasicCegarLoop]: trace histogram [33, 30, 30, 30, 30, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:54,536 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:54,536 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:54,536 INFO L82 PathProgramCache]: Analyzing trace with hash -889213235, now seen corresponding path program 12 times [2018-10-15 15:32:54,542 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:54,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:54,876 INFO L134 CoverageAnalysis]: Checked inductivity of 2385 backedges. 0 proven. 1650 refuted. 0 times theorem prover too weak. 735 trivial. 0 not checked. [2018-10-15 15:32:54,876 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:54,877 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-15 15:32:54,877 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-15 15:32:54,877 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-15 15:32:54,877 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-10-15 15:32:54,878 INFO L87 Difference]: Start difference. First operand 187 states and 190 transitions. Second operand 9 states. [2018-10-15 15:32:55,031 WARN L179 SmtUtils]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-10-15 15:32:55,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:55,269 INFO L93 Difference]: Finished difference Result 300 states and 305 transitions. [2018-10-15 15:32:55,270 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-10-15 15:32:55,270 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 186 [2018-10-15 15:32:55,270 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:55,272 INFO L225 Difference]: With dead ends: 300 [2018-10-15 15:32:55,272 INFO L226 Difference]: Without dead ends: 300 [2018-10-15 15:32:55,273 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2018-10-15 15:32:55,274 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 300 states. [2018-10-15 15:32:55,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 300 to 245. [2018-10-15 15:32:55,281 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 245 states. [2018-10-15 15:32:55,282 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 245 states to 245 states and 249 transitions. [2018-10-15 15:32:55,282 INFO L78 Accepts]: Start accepts. Automaton has 245 states and 249 transitions. Word has length 186 [2018-10-15 15:32:55,283 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:55,283 INFO L481 AbstractCegarLoop]: Abstraction has 245 states and 249 transitions. [2018-10-15 15:32:55,283 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-15 15:32:55,283 INFO L276 IsEmpty]: Start isEmpty. Operand 245 states and 249 transitions. [2018-10-15 15:32:55,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 245 [2018-10-15 15:32:55,284 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:55,285 INFO L375 BasicCegarLoop]: trace histogram [44, 40, 40, 40, 40, 5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:55,285 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:55,285 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:55,285 INFO L82 PathProgramCache]: Analyzing trace with hash -672925864, now seen corresponding path program 13 times [2018-10-15 15:32:55,286 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:55,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:55,771 INFO L134 CoverageAnalysis]: Checked inductivity of 4276 backedges. 0 proven. 3296 refuted. 0 times theorem prover too weak. 980 trivial. 0 not checked. [2018-10-15 15:32:55,771 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:55,771 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2018-10-15 15:32:55,772 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-15 15:32:55,772 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-15 15:32:55,772 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=91, Unknown=0, NotChecked=0, Total=110 [2018-10-15 15:32:55,772 INFO L87 Difference]: Start difference. First operand 245 states and 249 transitions. Second operand 11 states. [2018-10-15 15:32:56,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:56,109 INFO L93 Difference]: Finished difference Result 358 states and 364 transitions. [2018-10-15 15:32:56,115 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-15 15:32:56,115 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 244 [2018-10-15 15:32:56,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:56,117 INFO L225 Difference]: With dead ends: 358 [2018-10-15 15:32:56,117 INFO L226 Difference]: Without dead ends: 358 [2018-10-15 15:32:56,118 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=51, Invalid=291, Unknown=0, NotChecked=0, Total=342 [2018-10-15 15:32:56,118 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 358 states. [2018-10-15 15:32:56,122 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 358 to 303. [2018-10-15 15:32:56,123 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 303 states. [2018-10-15 15:32:56,124 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 303 states to 303 states and 308 transitions. [2018-10-15 15:32:56,124 INFO L78 Accepts]: Start accepts. Automaton has 303 states and 308 transitions. Word has length 244 [2018-10-15 15:32:56,124 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:56,124 INFO L481 AbstractCegarLoop]: Abstraction has 303 states and 308 transitions. [2018-10-15 15:32:56,125 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-15 15:32:56,125 INFO L276 IsEmpty]: Start isEmpty. Operand 303 states and 308 transitions. [2018-10-15 15:32:56,126 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 303 [2018-10-15 15:32:56,126 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:56,127 INFO L375 BasicCegarLoop]: trace histogram [55, 50, 50, 50, 50, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:56,127 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:56,127 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:56,127 INFO L82 PathProgramCache]: Analyzing trace with hash 1947495459, now seen corresponding path program 14 times [2018-10-15 15:32:56,128 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:56,150 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:56,624 INFO L134 CoverageAnalysis]: Checked inductivity of 6715 backedges. 0 proven. 5490 refuted. 0 times theorem prover too weak. 1225 trivial. 0 not checked. [2018-10-15 15:32:56,624 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:56,624 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-15 15:32:56,625 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-15 15:32:56,625 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-15 15:32:56,625 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-10-15 15:32:56,626 INFO L87 Difference]: Start difference. First operand 303 states and 308 transitions. Second operand 13 states. [2018-10-15 15:32:56,986 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:56,987 INFO L93 Difference]: Finished difference Result 416 states and 423 transitions. [2018-10-15 15:32:56,987 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-15 15:32:56,987 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 302 [2018-10-15 15:32:56,988 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:56,990 INFO L225 Difference]: With dead ends: 416 [2018-10-15 15:32:56,991 INFO L226 Difference]: Without dead ends: 416 [2018-10-15 15:32:56,992 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=63, Invalid=443, Unknown=0, NotChecked=0, Total=506 [2018-10-15 15:32:56,993 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 416 states. [2018-10-15 15:32:56,997 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 416 to 361. [2018-10-15 15:32:56,999 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 361 states. [2018-10-15 15:32:57,000 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 361 states to 361 states and 367 transitions. [2018-10-15 15:32:57,000 INFO L78 Accepts]: Start accepts. Automaton has 361 states and 367 transitions. Word has length 302 [2018-10-15 15:32:57,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:57,001 INFO L481 AbstractCegarLoop]: Abstraction has 361 states and 367 transitions. [2018-10-15 15:32:57,001 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-15 15:32:57,001 INFO L276 IsEmpty]: Start isEmpty. Operand 361 states and 367 transitions. [2018-10-15 15:32:57,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 361 [2018-10-15 15:32:57,003 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:57,004 INFO L375 BasicCegarLoop]: trace histogram [66, 60, 60, 60, 60, 7, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:57,004 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:57,004 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:57,004 INFO L82 PathProgramCache]: Analyzing trace with hash 355810606, now seen corresponding path program 15 times [2018-10-15 15:32:57,005 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:57,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:32:58,240 INFO L134 CoverageAnalysis]: Checked inductivity of 9702 backedges. 0 proven. 8232 refuted. 0 times theorem prover too weak. 1470 trivial. 0 not checked. [2018-10-15 15:32:58,241 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:32:58,241 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-10-15 15:32:58,242 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-15 15:32:58,242 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-15 15:32:58,242 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-10-15 15:32:58,242 INFO L87 Difference]: Start difference. First operand 361 states and 367 transitions. Second operand 15 states. [2018-10-15 15:32:58,718 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:32:58,719 INFO L93 Difference]: Finished difference Result 474 states and 482 transitions. [2018-10-15 15:32:58,721 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-10-15 15:32:58,721 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 360 [2018-10-15 15:32:58,723 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:32:58,725 INFO L225 Difference]: With dead ends: 474 [2018-10-15 15:32:58,725 INFO L226 Difference]: Without dead ends: 474 [2018-10-15 15:32:58,726 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=75, Invalid=627, Unknown=0, NotChecked=0, Total=702 [2018-10-15 15:32:58,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 474 states. [2018-10-15 15:32:58,732 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 474 to 419. [2018-10-15 15:32:58,732 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 419 states. [2018-10-15 15:32:58,734 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 419 states to 419 states and 426 transitions. [2018-10-15 15:32:58,734 INFO L78 Accepts]: Start accepts. Automaton has 419 states and 426 transitions. Word has length 360 [2018-10-15 15:32:58,735 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:32:58,735 INFO L481 AbstractCegarLoop]: Abstraction has 419 states and 426 transitions. [2018-10-15 15:32:58,735 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-15 15:32:58,735 INFO L276 IsEmpty]: Start isEmpty. Operand 419 states and 426 transitions. [2018-10-15 15:32:58,738 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 419 [2018-10-15 15:32:58,739 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:32:58,739 INFO L375 BasicCegarLoop]: trace histogram [77, 70, 70, 70, 70, 8, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:32:58,739 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:32:58,740 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:32:58,740 INFO L82 PathProgramCache]: Analyzing trace with hash 844012153, now seen corresponding path program 16 times [2018-10-15 15:32:58,741 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:32:58,771 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:00,131 INFO L134 CoverageAnalysis]: Checked inductivity of 13237 backedges. 0 proven. 11522 refuted. 0 times theorem prover too weak. 1715 trivial. 0 not checked. [2018-10-15 15:33:00,132 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:00,132 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-15 15:33:00,132 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-15 15:33:00,133 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-15 15:33:00,133 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=241, Unknown=0, NotChecked=0, Total=272 [2018-10-15 15:33:00,133 INFO L87 Difference]: Start difference. First operand 419 states and 426 transitions. Second operand 17 states. [2018-10-15 15:33:00,774 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:00,775 INFO L93 Difference]: Finished difference Result 532 states and 541 transitions. [2018-10-15 15:33:00,777 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-15 15:33:00,777 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 418 [2018-10-15 15:33:00,778 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:00,780 INFO L225 Difference]: With dead ends: 532 [2018-10-15 15:33:00,780 INFO L226 Difference]: Without dead ends: 532 [2018-10-15 15:33:00,780 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=87, Invalid=843, Unknown=0, NotChecked=0, Total=930 [2018-10-15 15:33:00,781 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 532 states. [2018-10-15 15:33:00,787 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 532 to 477. [2018-10-15 15:33:00,787 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 477 states. [2018-10-15 15:33:00,788 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 477 states to 477 states and 485 transitions. [2018-10-15 15:33:00,788 INFO L78 Accepts]: Start accepts. Automaton has 477 states and 485 transitions. Word has length 418 [2018-10-15 15:33:00,789 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:00,789 INFO L481 AbstractCegarLoop]: Abstraction has 477 states and 485 transitions. [2018-10-15 15:33:00,789 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-15 15:33:00,790 INFO L276 IsEmpty]: Start isEmpty. Operand 477 states and 485 transitions. [2018-10-15 15:33:00,792 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 477 [2018-10-15 15:33:00,792 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:00,792 INFO L375 BasicCegarLoop]: trace histogram [88, 80, 80, 80, 80, 9, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:00,793 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:00,793 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:00,793 INFO L82 PathProgramCache]: Analyzing trace with hash -20139004, now seen corresponding path program 17 times [2018-10-15 15:33:00,794 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:00,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:01,636 INFO L134 CoverageAnalysis]: Checked inductivity of 17320 backedges. 0 proven. 15360 refuted. 0 times theorem prover too weak. 1960 trivial. 0 not checked. [2018-10-15 15:33:01,636 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:01,637 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-10-15 15:33:01,637 INFO L460 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-15 15:33:01,637 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-15 15:33:01,638 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=307, Unknown=0, NotChecked=0, Total=342 [2018-10-15 15:33:01,638 INFO L87 Difference]: Start difference. First operand 477 states and 485 transitions. Second operand 19 states. [2018-10-15 15:33:02,611 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:02,612 INFO L93 Difference]: Finished difference Result 590 states and 600 transitions. [2018-10-15 15:33:02,612 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-10-15 15:33:02,612 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 476 [2018-10-15 15:33:02,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:02,617 INFO L225 Difference]: With dead ends: 590 [2018-10-15 15:33:02,617 INFO L226 Difference]: Without dead ends: 590 [2018-10-15 15:33:02,618 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=99, Invalid=1091, Unknown=0, NotChecked=0, Total=1190 [2018-10-15 15:33:02,618 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 590 states. [2018-10-15 15:33:02,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 590 to 535. [2018-10-15 15:33:02,625 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 535 states. [2018-10-15 15:33:02,627 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 535 states to 535 states and 544 transitions. [2018-10-15 15:33:02,627 INFO L78 Accepts]: Start accepts. Automaton has 535 states and 544 transitions. Word has length 476 [2018-10-15 15:33:02,628 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:02,628 INFO L481 AbstractCegarLoop]: Abstraction has 535 states and 544 transitions. [2018-10-15 15:33:02,628 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-15 15:33:02,628 INFO L276 IsEmpty]: Start isEmpty. Operand 535 states and 544 transitions. [2018-10-15 15:33:02,631 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 535 [2018-10-15 15:33:02,631 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:02,632 INFO L375 BasicCegarLoop]: trace histogram [99, 90, 90, 90, 90, 10, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:02,632 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:02,632 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:02,633 INFO L82 PathProgramCache]: Analyzing trace with hash 1702869455, now seen corresponding path program 18 times [2018-10-15 15:33:02,633 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:02,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:05,753 INFO L134 CoverageAnalysis]: Checked inductivity of 21951 backedges. 0 proven. 19746 refuted. 0 times theorem prover too weak. 2205 trivial. 0 not checked. [2018-10-15 15:33:05,753 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:05,753 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-15 15:33:05,754 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-15 15:33:05,754 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-15 15:33:05,754 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=381, Unknown=0, NotChecked=0, Total=420 [2018-10-15 15:33:05,755 INFO L87 Difference]: Start difference. First operand 535 states and 544 transitions. Second operand 21 states. [2018-10-15 15:33:06,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:06,789 INFO L93 Difference]: Finished difference Result 648 states and 659 transitions. [2018-10-15 15:33:06,797 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-15 15:33:06,797 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 534 [2018-10-15 15:33:06,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:06,800 INFO L225 Difference]: With dead ends: 648 [2018-10-15 15:33:06,801 INFO L226 Difference]: Without dead ends: 648 [2018-10-15 15:33:06,801 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 153 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=111, Invalid=1371, Unknown=0, NotChecked=0, Total=1482 [2018-10-15 15:33:06,802 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 648 states. [2018-10-15 15:33:06,810 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 648 to 593. [2018-10-15 15:33:06,810 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 593 states. [2018-10-15 15:33:06,812 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 593 states to 593 states and 603 transitions. [2018-10-15 15:33:06,812 INFO L78 Accepts]: Start accepts. Automaton has 593 states and 603 transitions. Word has length 534 [2018-10-15 15:33:06,813 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:06,813 INFO L481 AbstractCegarLoop]: Abstraction has 593 states and 603 transitions. [2018-10-15 15:33:06,813 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-15 15:33:06,813 INFO L276 IsEmpty]: Start isEmpty. Operand 593 states and 603 transitions. [2018-10-15 15:33:06,817 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 593 [2018-10-15 15:33:06,817 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:06,817 INFO L375 BasicCegarLoop]: trace histogram [110, 100, 100, 100, 100, 11, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:06,818 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:06,818 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:06,818 INFO L82 PathProgramCache]: Analyzing trace with hash 1134287834, now seen corresponding path program 19 times [2018-10-15 15:33:06,819 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:06,854 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:08,484 INFO L134 CoverageAnalysis]: Checked inductivity of 27130 backedges. 0 proven. 24680 refuted. 0 times theorem prover too weak. 2450 trivial. 0 not checked. [2018-10-15 15:33:08,485 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:08,485 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2018-10-15 15:33:08,486 INFO L460 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-15 15:33:08,486 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-15 15:33:08,486 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=463, Unknown=0, NotChecked=0, Total=506 [2018-10-15 15:33:08,486 INFO L87 Difference]: Start difference. First operand 593 states and 603 transitions. Second operand 23 states. [2018-10-15 15:33:09,841 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:09,842 INFO L93 Difference]: Finished difference Result 706 states and 718 transitions. [2018-10-15 15:33:09,842 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-10-15 15:33:09,843 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 592 [2018-10-15 15:33:09,844 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:09,848 INFO L225 Difference]: With dead ends: 706 [2018-10-15 15:33:09,848 INFO L226 Difference]: Without dead ends: 706 [2018-10-15 15:33:09,849 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 44 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 190 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=123, Invalid=1683, Unknown=0, NotChecked=0, Total=1806 [2018-10-15 15:33:09,850 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 706 states. [2018-10-15 15:33:09,859 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 706 to 651. [2018-10-15 15:33:09,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 651 states. [2018-10-15 15:33:09,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 651 states to 651 states and 662 transitions. [2018-10-15 15:33:09,861 INFO L78 Accepts]: Start accepts. Automaton has 651 states and 662 transitions. Word has length 592 [2018-10-15 15:33:09,862 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:09,862 INFO L481 AbstractCegarLoop]: Abstraction has 651 states and 662 transitions. [2018-10-15 15:33:09,862 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-15 15:33:09,862 INFO L276 IsEmpty]: Start isEmpty. Operand 651 states and 662 transitions. [2018-10-15 15:33:09,868 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 651 [2018-10-15 15:33:09,869 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:09,869 INFO L375 BasicCegarLoop]: trace histogram [121, 110, 110, 110, 110, 12, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:09,869 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:09,869 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:09,870 INFO L82 PathProgramCache]: Analyzing trace with hash -474396123, now seen corresponding path program 20 times [2018-10-15 15:33:09,871 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:09,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:11,686 INFO L134 CoverageAnalysis]: Checked inductivity of 32857 backedges. 0 proven. 30162 refuted. 0 times theorem prover too weak. 2695 trivial. 0 not checked. [2018-10-15 15:33:11,686 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:11,687 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-15 15:33:11,687 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-15 15:33:11,687 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-15 15:33:11,688 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=553, Unknown=0, NotChecked=0, Total=600 [2018-10-15 15:33:11,688 INFO L87 Difference]: Start difference. First operand 651 states and 662 transitions. Second operand 25 states. [2018-10-15 15:33:12,934 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:12,934 INFO L93 Difference]: Finished difference Result 764 states and 777 transitions. [2018-10-15 15:33:12,935 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-10-15 15:33:12,935 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 650 [2018-10-15 15:33:12,937 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:12,939 INFO L225 Difference]: With dead ends: 764 [2018-10-15 15:33:12,939 INFO L226 Difference]: Without dead ends: 764 [2018-10-15 15:33:12,940 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 231 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=135, Invalid=2027, Unknown=0, NotChecked=0, Total=2162 [2018-10-15 15:33:12,941 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 764 states. [2018-10-15 15:33:12,948 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 764 to 709. [2018-10-15 15:33:12,949 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-10-15 15:33:12,950 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 721 transitions. [2018-10-15 15:33:12,950 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 721 transitions. Word has length 650 [2018-10-15 15:33:12,951 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:12,951 INFO L481 AbstractCegarLoop]: Abstraction has 709 states and 721 transitions. [2018-10-15 15:33:12,951 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-15 15:33:12,951 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 721 transitions. [2018-10-15 15:33:12,956 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 709 [2018-10-15 15:33:12,956 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:12,956 INFO L375 BasicCegarLoop]: trace histogram [132, 120, 120, 120, 120, 13, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:12,957 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:12,957 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:12,957 INFO L82 PathProgramCache]: Analyzing trace with hash -1194052432, now seen corresponding path program 21 times [2018-10-15 15:33:12,958 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:12,993 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:15,080 INFO L134 CoverageAnalysis]: Checked inductivity of 39132 backedges. 0 proven. 36192 refuted. 0 times theorem prover too weak. 2940 trivial. 0 not checked. [2018-10-15 15:33:15,080 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:15,081 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2018-10-15 15:33:15,081 INFO L460 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-10-15 15:33:15,082 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-10-15 15:33:15,082 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=651, Unknown=0, NotChecked=0, Total=702 [2018-10-15 15:33:15,082 INFO L87 Difference]: Start difference. First operand 709 states and 721 transitions. Second operand 27 states. [2018-10-15 15:33:16,640 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:16,640 INFO L93 Difference]: Finished difference Result 822 states and 836 transitions. [2018-10-15 15:33:16,641 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-10-15 15:33:16,642 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 708 [2018-10-15 15:33:16,642 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:16,646 INFO L225 Difference]: With dead ends: 822 [2018-10-15 15:33:16,646 INFO L226 Difference]: Without dead ends: 822 [2018-10-15 15:33:16,647 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 276 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=147, Invalid=2403, Unknown=0, NotChecked=0, Total=2550 [2018-10-15 15:33:16,648 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 822 states. [2018-10-15 15:33:16,656 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 822 to 767. [2018-10-15 15:33:16,657 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 767 states. [2018-10-15 15:33:16,658 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 767 states to 767 states and 780 transitions. [2018-10-15 15:33:16,658 INFO L78 Accepts]: Start accepts. Automaton has 767 states and 780 transitions. Word has length 708 [2018-10-15 15:33:16,659 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:16,659 INFO L481 AbstractCegarLoop]: Abstraction has 767 states and 780 transitions. [2018-10-15 15:33:16,659 INFO L482 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-10-15 15:33:16,659 INFO L276 IsEmpty]: Start isEmpty. Operand 767 states and 780 transitions. [2018-10-15 15:33:16,665 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 767 [2018-10-15 15:33:16,665 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:16,666 INFO L375 BasicCegarLoop]: trace histogram [143, 130, 130, 130, 130, 14, 13, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:16,666 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:16,666 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:16,667 INFO L82 PathProgramCache]: Analyzing trace with hash 1498205051, now seen corresponding path program 22 times [2018-10-15 15:33:16,667 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:16,705 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:19,980 INFO L134 CoverageAnalysis]: Checked inductivity of 45955 backedges. 0 proven. 42770 refuted. 0 times theorem prover too weak. 3185 trivial. 0 not checked. [2018-10-15 15:33:19,980 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:19,981 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-15 15:33:19,981 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-15 15:33:19,982 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-15 15:33:19,982 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=757, Unknown=0, NotChecked=0, Total=812 [2018-10-15 15:33:19,982 INFO L87 Difference]: Start difference. First operand 767 states and 780 transitions. Second operand 29 states. [2018-10-15 15:33:21,654 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:21,655 INFO L93 Difference]: Finished difference Result 880 states and 895 transitions. [2018-10-15 15:33:21,655 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2018-10-15 15:33:21,655 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 766 [2018-10-15 15:33:21,656 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:21,660 INFO L225 Difference]: With dead ends: 880 [2018-10-15 15:33:21,661 INFO L226 Difference]: Without dead ends: 880 [2018-10-15 15:33:21,662 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 325 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=159, Invalid=2811, Unknown=0, NotChecked=0, Total=2970 [2018-10-15 15:33:21,663 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 880 states. [2018-10-15 15:33:21,671 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 880 to 825. [2018-10-15 15:33:21,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 825 states. [2018-10-15 15:33:21,673 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 825 states to 825 states and 839 transitions. [2018-10-15 15:33:21,673 INFO L78 Accepts]: Start accepts. Automaton has 825 states and 839 transitions. Word has length 766 [2018-10-15 15:33:21,674 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:21,674 INFO L481 AbstractCegarLoop]: Abstraction has 825 states and 839 transitions. [2018-10-15 15:33:21,674 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-15 15:33:21,674 INFO L276 IsEmpty]: Start isEmpty. Operand 825 states and 839 transitions. [2018-10-15 15:33:21,680 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 825 [2018-10-15 15:33:21,680 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:21,681 INFO L375 BasicCegarLoop]: trace histogram [154, 140, 140, 140, 140, 15, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:21,681 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:21,682 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:21,682 INFO L82 PathProgramCache]: Analyzing trace with hash -1176027514, now seen corresponding path program 23 times [2018-10-15 15:33:21,683 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:21,724 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:24,734 INFO L134 CoverageAnalysis]: Checked inductivity of 53326 backedges. 0 proven. 49896 refuted. 0 times theorem prover too weak. 3430 trivial. 0 not checked. [2018-10-15 15:33:24,734 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:24,734 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31] total 31 [2018-10-15 15:33:24,735 INFO L460 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-10-15 15:33:24,735 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-10-15 15:33:24,735 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=871, Unknown=0, NotChecked=0, Total=930 [2018-10-15 15:33:24,736 INFO L87 Difference]: Start difference. First operand 825 states and 839 transitions. Second operand 31 states. [2018-10-15 15:33:26,746 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:26,747 INFO L93 Difference]: Finished difference Result 938 states and 954 transitions. [2018-10-15 15:33:26,747 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-10-15 15:33:26,747 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 824 [2018-10-15 15:33:26,748 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:26,751 INFO L225 Difference]: With dead ends: 938 [2018-10-15 15:33:26,751 INFO L226 Difference]: Without dead ends: 938 [2018-10-15 15:33:26,752 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 378 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=171, Invalid=3251, Unknown=0, NotChecked=0, Total=3422 [2018-10-15 15:33:26,753 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 938 states. [2018-10-15 15:33:26,761 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 938 to 883. [2018-10-15 15:33:26,761 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-10-15 15:33:26,763 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 898 transitions. [2018-10-15 15:33:26,763 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 898 transitions. Word has length 824 [2018-10-15 15:33:26,764 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:26,764 INFO L481 AbstractCegarLoop]: Abstraction has 883 states and 898 transitions. [2018-10-15 15:33:26,764 INFO L482 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-10-15 15:33:26,764 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 898 transitions. [2018-10-15 15:33:26,771 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 883 [2018-10-15 15:33:26,771 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:26,772 INFO L375 BasicCegarLoop]: trace histogram [165, 150, 150, 150, 150, 16, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:26,772 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:26,772 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:26,772 INFO L82 PathProgramCache]: Analyzing trace with hash -1463042607, now seen corresponding path program 24 times [2018-10-15 15:33:26,773 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:26,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:29,535 INFO L134 CoverageAnalysis]: Checked inductivity of 61245 backedges. 0 proven. 57570 refuted. 0 times theorem prover too weak. 3675 trivial. 0 not checked. [2018-10-15 15:33:29,535 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:29,535 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-15 15:33:29,536 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-15 15:33:29,536 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-15 15:33:29,536 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=993, Unknown=0, NotChecked=0, Total=1056 [2018-10-15 15:33:29,537 INFO L87 Difference]: Start difference. First operand 883 states and 898 transitions. Second operand 33 states. [2018-10-15 15:33:30,354 WARN L179 SmtUtils]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-10-15 15:33:32,002 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:32,003 INFO L93 Difference]: Finished difference Result 996 states and 1013 transitions. [2018-10-15 15:33:32,003 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2018-10-15 15:33:32,003 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 882 [2018-10-15 15:33:32,004 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:32,007 INFO L225 Difference]: With dead ends: 996 [2018-10-15 15:33:32,007 INFO L226 Difference]: Without dead ends: 996 [2018-10-15 15:33:32,009 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 435 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=183, Invalid=3723, Unknown=0, NotChecked=0, Total=3906 [2018-10-15 15:33:32,009 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 996 states. [2018-10-15 15:33:32,018 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 996 to 941. [2018-10-15 15:33:32,018 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 941 states. [2018-10-15 15:33:32,020 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 941 states to 941 states and 957 transitions. [2018-10-15 15:33:32,020 INFO L78 Accepts]: Start accepts. Automaton has 941 states and 957 transitions. Word has length 882 [2018-10-15 15:33:32,021 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:32,021 INFO L481 AbstractCegarLoop]: Abstraction has 941 states and 957 transitions. [2018-10-15 15:33:32,021 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-15 15:33:32,021 INFO L276 IsEmpty]: Start isEmpty. Operand 941 states and 957 transitions. [2018-10-15 15:33:32,029 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 941 [2018-10-15 15:33:32,030 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:32,030 INFO L375 BasicCegarLoop]: trace histogram [176, 160, 160, 160, 160, 17, 16, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:32,031 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:32,031 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:32,031 INFO L82 PathProgramCache]: Analyzing trace with hash -2004453028, now seen corresponding path program 25 times [2018-10-15 15:33:32,032 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:32,079 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:34,382 INFO L134 CoverageAnalysis]: Checked inductivity of 69712 backedges. 0 proven. 65792 refuted. 0 times theorem prover too weak. 3920 trivial. 0 not checked. [2018-10-15 15:33:34,382 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:34,383 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35] total 35 [2018-10-15 15:33:34,383 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-10-15 15:33:34,383 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-10-15 15:33:34,384 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=1123, Unknown=0, NotChecked=0, Total=1190 [2018-10-15 15:33:34,384 INFO L87 Difference]: Start difference. First operand 941 states and 957 transitions. Second operand 35 states. [2018-10-15 15:33:35,014 WARN L179 SmtUtils]: Spent 137.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-10-15 15:33:37,107 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:37,108 INFO L93 Difference]: Finished difference Result 1054 states and 1072 transitions. [2018-10-15 15:33:37,108 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-10-15 15:33:37,108 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 940 [2018-10-15 15:33:37,109 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:37,113 INFO L225 Difference]: With dead ends: 1054 [2018-10-15 15:33:37,113 INFO L226 Difference]: Without dead ends: 1054 [2018-10-15 15:33:37,115 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 496 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=195, Invalid=4227, Unknown=0, NotChecked=0, Total=4422 [2018-10-15 15:33:37,115 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1054 states. [2018-10-15 15:33:37,124 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1054 to 999. [2018-10-15 15:33:37,124 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 999 states. [2018-10-15 15:33:37,126 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 999 states to 999 states and 1016 transitions. [2018-10-15 15:33:37,126 INFO L78 Accepts]: Start accepts. Automaton has 999 states and 1016 transitions. Word has length 940 [2018-10-15 15:33:37,127 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:37,127 INFO L481 AbstractCegarLoop]: Abstraction has 999 states and 1016 transitions. [2018-10-15 15:33:37,127 INFO L482 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-10-15 15:33:37,127 INFO L276 IsEmpty]: Start isEmpty. Operand 999 states and 1016 transitions. [2018-10-15 15:33:37,135 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 999 [2018-10-15 15:33:37,136 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:37,136 INFO L375 BasicCegarLoop]: trace histogram [187, 170, 170, 170, 170, 18, 17, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:37,137 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:37,137 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:37,137 INFO L82 PathProgramCache]: Analyzing trace with hash 1258791207, now seen corresponding path program 26 times [2018-10-15 15:33:37,138 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:37,182 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:40,826 INFO L134 CoverageAnalysis]: Checked inductivity of 78727 backedges. 0 proven. 74562 refuted. 0 times theorem prover too weak. 4165 trivial. 0 not checked. [2018-10-15 15:33:40,827 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:40,827 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-15 15:33:40,828 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-15 15:33:40,828 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-15 15:33:40,828 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=1261, Unknown=0, NotChecked=0, Total=1332 [2018-10-15 15:33:40,828 INFO L87 Difference]: Start difference. First operand 999 states and 1016 transitions. Second operand 37 states. [2018-10-15 15:33:43,472 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:43,473 INFO L93 Difference]: Finished difference Result 1112 states and 1131 transitions. [2018-10-15 15:33:43,473 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-10-15 15:33:43,473 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 998 [2018-10-15 15:33:43,474 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:43,479 INFO L225 Difference]: With dead ends: 1112 [2018-10-15 15:33:43,479 INFO L226 Difference]: Without dead ends: 1112 [2018-10-15 15:33:43,481 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 561 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=207, Invalid=4763, Unknown=0, NotChecked=0, Total=4970 [2018-10-15 15:33:43,481 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1112 states. [2018-10-15 15:33:43,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1112 to 1057. [2018-10-15 15:33:43,490 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1057 states. [2018-10-15 15:33:43,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1057 states to 1057 states and 1075 transitions. [2018-10-15 15:33:43,492 INFO L78 Accepts]: Start accepts. Automaton has 1057 states and 1075 transitions. Word has length 998 [2018-10-15 15:33:43,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:43,493 INFO L481 AbstractCegarLoop]: Abstraction has 1057 states and 1075 transitions. [2018-10-15 15:33:43,493 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-15 15:33:43,493 INFO L276 IsEmpty]: Start isEmpty. Operand 1057 states and 1075 transitions. [2018-10-15 15:33:43,503 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1057 [2018-10-15 15:33:43,503 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:43,503 INFO L375 BasicCegarLoop]: trace histogram [198, 180, 180, 180, 180, 19, 18, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:43,504 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:43,504 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:43,504 INFO L82 PathProgramCache]: Analyzing trace with hash -1398577870, now seen corresponding path program 27 times [2018-10-15 15:33:43,505 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:43,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:46,637 INFO L134 CoverageAnalysis]: Checked inductivity of 88290 backedges. 0 proven. 83880 refuted. 0 times theorem prover too weak. 4410 trivial. 0 not checked. [2018-10-15 15:33:46,637 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:46,637 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39] total 39 [2018-10-15 15:33:46,638 INFO L460 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-10-15 15:33:46,638 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-10-15 15:33:46,639 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=1407, Unknown=0, NotChecked=0, Total=1482 [2018-10-15 15:33:46,639 INFO L87 Difference]: Start difference. First operand 1057 states and 1075 transitions. Second operand 39 states. [2018-10-15 15:33:49,843 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:49,843 INFO L93 Difference]: Finished difference Result 1170 states and 1190 transitions. [2018-10-15 15:33:49,844 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-10-15 15:33:49,844 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 1056 [2018-10-15 15:33:49,845 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:49,849 INFO L225 Difference]: With dead ends: 1170 [2018-10-15 15:33:49,849 INFO L226 Difference]: Without dead ends: 1170 [2018-10-15 15:33:49,851 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 630 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=219, Invalid=5331, Unknown=0, NotChecked=0, Total=5550 [2018-10-15 15:33:49,852 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1170 states. [2018-10-15 15:33:49,862 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1170 to 1115. [2018-10-15 15:33:49,862 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1115 states. [2018-10-15 15:33:49,864 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1115 states to 1115 states and 1134 transitions. [2018-10-15 15:33:49,865 INFO L78 Accepts]: Start accepts. Automaton has 1115 states and 1134 transitions. Word has length 1056 [2018-10-15 15:33:49,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:49,866 INFO L481 AbstractCegarLoop]: Abstraction has 1115 states and 1134 transitions. [2018-10-15 15:33:49,866 INFO L482 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-10-15 15:33:49,866 INFO L276 IsEmpty]: Start isEmpty. Operand 1115 states and 1134 transitions. [2018-10-15 15:33:49,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1115 [2018-10-15 15:33:49,877 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:49,877 INFO L375 BasicCegarLoop]: trace histogram [209, 190, 190, 190, 190, 20, 19, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:49,877 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:49,878 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:49,878 INFO L82 PathProgramCache]: Analyzing trace with hash -1357777539, now seen corresponding path program 28 times [2018-10-15 15:33:49,879 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:49,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:53,020 INFO L134 CoverageAnalysis]: Checked inductivity of 98401 backedges. 0 proven. 93746 refuted. 0 times theorem prover too weak. 4655 trivial. 0 not checked. [2018-10-15 15:33:53,020 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:53,020 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-15 15:33:53,021 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-15 15:33:53,021 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-15 15:33:53,022 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=1561, Unknown=0, NotChecked=0, Total=1640 [2018-10-15 15:33:53,022 INFO L87 Difference]: Start difference. First operand 1115 states and 1134 transitions. Second operand 41 states. [2018-10-15 15:33:55,904 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:33:55,905 INFO L93 Difference]: Finished difference Result 1228 states and 1249 transitions. [2018-10-15 15:33:55,905 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-10-15 15:33:55,905 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 1114 [2018-10-15 15:33:55,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:33:55,911 INFO L225 Difference]: With dead ends: 1228 [2018-10-15 15:33:55,911 INFO L226 Difference]: Without dead ends: 1228 [2018-10-15 15:33:55,913 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 703 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=231, Invalid=5931, Unknown=0, NotChecked=0, Total=6162 [2018-10-15 15:33:55,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1228 states. [2018-10-15 15:33:55,922 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1228 to 1173. [2018-10-15 15:33:55,923 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1173 states. [2018-10-15 15:33:55,925 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1173 states to 1173 states and 1193 transitions. [2018-10-15 15:33:55,925 INFO L78 Accepts]: Start accepts. Automaton has 1173 states and 1193 transitions. Word has length 1114 [2018-10-15 15:33:55,926 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:33:55,926 INFO L481 AbstractCegarLoop]: Abstraction has 1173 states and 1193 transitions. [2018-10-15 15:33:55,926 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-15 15:33:55,926 INFO L276 IsEmpty]: Start isEmpty. Operand 1173 states and 1193 transitions. [2018-10-15 15:33:55,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1173 [2018-10-15 15:33:55,938 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:33:55,939 INFO L375 BasicCegarLoop]: trace histogram [220, 200, 200, 200, 200, 21, 20, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:33:55,939 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:33:55,939 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:33:55,940 INFO L82 PathProgramCache]: Analyzing trace with hash 1416593928, now seen corresponding path program 29 times [2018-10-15 15:33:55,940 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:33:55,985 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:33:59,480 INFO L134 CoverageAnalysis]: Checked inductivity of 109060 backedges. 0 proven. 104160 refuted. 0 times theorem prover too weak. 4900 trivial. 0 not checked. [2018-10-15 15:33:59,481 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:33:59,481 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43] total 43 [2018-10-15 15:33:59,481 INFO L460 AbstractCegarLoop]: Interpolant automaton has 43 states [2018-10-15 15:33:59,482 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2018-10-15 15:33:59,482 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=1723, Unknown=0, NotChecked=0, Total=1806 [2018-10-15 15:33:59,482 INFO L87 Difference]: Start difference. First operand 1173 states and 1193 transitions. Second operand 43 states. [2018-10-15 15:34:02,903 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:34:02,903 INFO L93 Difference]: Finished difference Result 1286 states and 1308 transitions. [2018-10-15 15:34:02,903 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2018-10-15 15:34:02,904 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 1172 [2018-10-15 15:34:02,905 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:34:02,909 INFO L225 Difference]: With dead ends: 1286 [2018-10-15 15:34:02,909 INFO L226 Difference]: Without dead ends: 1286 [2018-10-15 15:34:02,910 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 780 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=243, Invalid=6563, Unknown=0, NotChecked=0, Total=6806 [2018-10-15 15:34:02,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1286 states. [2018-10-15 15:34:02,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1286 to 1231. [2018-10-15 15:34:02,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1231 states. [2018-10-15 15:34:02,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1231 states to 1231 states and 1252 transitions. [2018-10-15 15:34:02,921 INFO L78 Accepts]: Start accepts. Automaton has 1231 states and 1252 transitions. Word has length 1172 [2018-10-15 15:34:02,922 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:34:02,922 INFO L481 AbstractCegarLoop]: Abstraction has 1231 states and 1252 transitions. [2018-10-15 15:34:02,922 INFO L482 AbstractCegarLoop]: Interpolant automaton has 43 states. [2018-10-15 15:34:02,923 INFO L276 IsEmpty]: Start isEmpty. Operand 1231 states and 1252 transitions. [2018-10-15 15:34:02,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1231 [2018-10-15 15:34:02,936 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:34:02,936 INFO L375 BasicCegarLoop]: trace histogram [231, 210, 210, 210, 210, 22, 21, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:34:02,936 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:34:02,937 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:34:02,937 INFO L82 PathProgramCache]: Analyzing trace with hash -1707328813, now seen corresponding path program 30 times [2018-10-15 15:34:02,938 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:34:02,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:34:08,478 INFO L134 CoverageAnalysis]: Checked inductivity of 120267 backedges. 0 proven. 115122 refuted. 0 times theorem prover too weak. 5145 trivial. 0 not checked. [2018-10-15 15:34:08,478 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:34:08,478 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-15 15:34:08,479 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-15 15:34:08,479 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-15 15:34:08,480 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=1893, Unknown=0, NotChecked=0, Total=1980 [2018-10-15 15:34:08,480 INFO L87 Difference]: Start difference. First operand 1231 states and 1252 transitions. Second operand 45 states. [2018-10-15 15:34:11,946 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:34:11,946 INFO L93 Difference]: Finished difference Result 1344 states and 1367 transitions. [2018-10-15 15:34:11,946 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 66 states. [2018-10-15 15:34:11,947 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 1230 [2018-10-15 15:34:11,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:34:11,952 INFO L225 Difference]: With dead ends: 1344 [2018-10-15 15:34:11,952 INFO L226 Difference]: Without dead ends: 1344 [2018-10-15 15:34:11,954 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 861 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=255, Invalid=7227, Unknown=0, NotChecked=0, Total=7482 [2018-10-15 15:34:11,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1344 states. [2018-10-15 15:34:11,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1344 to 1289. [2018-10-15 15:34:11,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1289 states. [2018-10-15 15:34:11,965 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1289 states to 1289 states and 1311 transitions. [2018-10-15 15:34:11,965 INFO L78 Accepts]: Start accepts. Automaton has 1289 states and 1311 transitions. Word has length 1230 [2018-10-15 15:34:11,966 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:34:11,966 INFO L481 AbstractCegarLoop]: Abstraction has 1289 states and 1311 transitions. [2018-10-15 15:34:11,966 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-15 15:34:11,966 INFO L276 IsEmpty]: Start isEmpty. Operand 1289 states and 1311 transitions. [2018-10-15 15:34:11,979 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1289 [2018-10-15 15:34:11,979 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:34:11,980 INFO L375 BasicCegarLoop]: trace histogram [242, 220, 220, 220, 220, 23, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:34:11,980 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:34:11,980 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:34:11,981 INFO L82 PathProgramCache]: Analyzing trace with hash -1269018658, now seen corresponding path program 31 times [2018-10-15 15:34:11,981 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:34:12,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:34:15,533 INFO L134 CoverageAnalysis]: Checked inductivity of 132022 backedges. 0 proven. 126632 refuted. 0 times theorem prover too weak. 5390 trivial. 0 not checked. [2018-10-15 15:34:15,533 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:34:15,533 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [47] total 47 [2018-10-15 15:34:15,534 INFO L460 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-10-15 15:34:15,534 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-10-15 15:34:15,535 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=2071, Unknown=0, NotChecked=0, Total=2162 [2018-10-15 15:34:15,535 INFO L87 Difference]: Start difference. First operand 1289 states and 1311 transitions. Second operand 47 states. [2018-10-15 15:34:19,690 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:34:19,691 INFO L93 Difference]: Finished difference Result 1402 states and 1426 transitions. [2018-10-15 15:34:19,691 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 69 states. [2018-10-15 15:34:19,691 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 1288 [2018-10-15 15:34:19,693 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:34:19,697 INFO L225 Difference]: With dead ends: 1402 [2018-10-15 15:34:19,697 INFO L226 Difference]: Without dead ends: 1402 [2018-10-15 15:34:19,699 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 946 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=267, Invalid=7923, Unknown=0, NotChecked=0, Total=8190 [2018-10-15 15:34:19,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1402 states. [2018-10-15 15:34:19,707 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1402 to 1347. [2018-10-15 15:34:19,707 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1347 states. [2018-10-15 15:34:19,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1347 states to 1347 states and 1370 transitions. [2018-10-15 15:34:19,709 INFO L78 Accepts]: Start accepts. Automaton has 1347 states and 1370 transitions. Word has length 1288 [2018-10-15 15:34:19,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:34:19,711 INFO L481 AbstractCegarLoop]: Abstraction has 1347 states and 1370 transitions. [2018-10-15 15:34:19,711 INFO L482 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-10-15 15:34:19,711 INFO L276 IsEmpty]: Start isEmpty. Operand 1347 states and 1370 transitions. [2018-10-15 15:34:19,725 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1347 [2018-10-15 15:34:19,725 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:34:19,726 INFO L375 BasicCegarLoop]: trace histogram [253, 230, 230, 230, 230, 24, 23, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:34:19,726 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:34:19,726 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:34:19,727 INFO L82 PathProgramCache]: Analyzing trace with hash -2011696855, now seen corresponding path program 32 times [2018-10-15 15:34:19,727 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:34:19,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:34:23,381 INFO L134 CoverageAnalysis]: Checked inductivity of 144325 backedges. 0 proven. 138690 refuted. 0 times theorem prover too weak. 5635 trivial. 0 not checked. [2018-10-15 15:34:23,382 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:34:23,382 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-15 15:34:23,383 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-15 15:34:23,383 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-15 15:34:23,383 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=2257, Unknown=0, NotChecked=0, Total=2352 [2018-10-15 15:34:23,383 INFO L87 Difference]: Start difference. First operand 1347 states and 1370 transitions. Second operand 49 states. [2018-10-15 15:34:27,583 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:34:27,583 INFO L93 Difference]: Finished difference Result 1460 states and 1485 transitions. [2018-10-15 15:34:27,584 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-10-15 15:34:27,584 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 1346 [2018-10-15 15:34:27,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:34:27,589 INFO L225 Difference]: With dead ends: 1460 [2018-10-15 15:34:27,589 INFO L226 Difference]: Without dead ends: 1460 [2018-10-15 15:34:27,590 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1035 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=279, Invalid=8651, Unknown=0, NotChecked=0, Total=8930 [2018-10-15 15:34:27,591 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1460 states. [2018-10-15 15:34:27,602 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1460 to 1405. [2018-10-15 15:34:27,602 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1405 states. [2018-10-15 15:34:27,604 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1405 states to 1405 states and 1429 transitions. [2018-10-15 15:34:27,605 INFO L78 Accepts]: Start accepts. Automaton has 1405 states and 1429 transitions. Word has length 1346 [2018-10-15 15:34:27,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:34:27,606 INFO L481 AbstractCegarLoop]: Abstraction has 1405 states and 1429 transitions. [2018-10-15 15:34:27,606 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-15 15:34:27,606 INFO L276 IsEmpty]: Start isEmpty. Operand 1405 states and 1429 transitions. [2018-10-15 15:34:27,628 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1405 [2018-10-15 15:34:27,628 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:34:27,629 INFO L375 BasicCegarLoop]: trace histogram [264, 240, 240, 240, 240, 25, 24, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:34:27,630 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:34:27,630 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:34:27,631 INFO L82 PathProgramCache]: Analyzing trace with hash 1729842868, now seen corresponding path program 33 times [2018-10-15 15:34:27,632 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:34:27,682 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:34:31,606 INFO L134 CoverageAnalysis]: Checked inductivity of 157176 backedges. 0 proven. 151296 refuted. 0 times theorem prover too weak. 5880 trivial. 0 not checked. [2018-10-15 15:34:31,606 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:34:31,606 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [51] total 51 [2018-10-15 15:34:31,607 INFO L460 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-10-15 15:34:31,607 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-10-15 15:34:31,607 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=2451, Unknown=0, NotChecked=0, Total=2550 [2018-10-15 15:34:31,607 INFO L87 Difference]: Start difference. First operand 1405 states and 1429 transitions. Second operand 51 states. [2018-10-15 15:34:36,337 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:34:36,338 INFO L93 Difference]: Finished difference Result 1518 states and 1544 transitions. [2018-10-15 15:34:36,338 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-10-15 15:34:36,338 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 1404 [2018-10-15 15:34:36,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:34:36,345 INFO L225 Difference]: With dead ends: 1518 [2018-10-15 15:34:36,345 INFO L226 Difference]: Without dead ends: 1518 [2018-10-15 15:34:36,346 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 97 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1128 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=291, Invalid=9411, Unknown=0, NotChecked=0, Total=9702 [2018-10-15 15:34:36,347 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1518 states. [2018-10-15 15:34:36,357 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1518 to 1463. [2018-10-15 15:34:36,357 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1463 states. [2018-10-15 15:34:36,360 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1463 states to 1463 states and 1488 transitions. [2018-10-15 15:34:36,360 INFO L78 Accepts]: Start accepts. Automaton has 1463 states and 1488 transitions. Word has length 1404 [2018-10-15 15:34:36,361 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:34:36,361 INFO L481 AbstractCegarLoop]: Abstraction has 1463 states and 1488 transitions. [2018-10-15 15:34:36,361 INFO L482 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-10-15 15:34:36,361 INFO L276 IsEmpty]: Start isEmpty. Operand 1463 states and 1488 transitions. [2018-10-15 15:34:36,378 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1463 [2018-10-15 15:34:36,378 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:34:36,379 INFO L375 BasicCegarLoop]: trace histogram [275, 250, 250, 250, 250, 26, 25, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:34:36,379 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:34:36,379 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:34:36,380 INFO L82 PathProgramCache]: Analyzing trace with hash 175544447, now seen corresponding path program 34 times [2018-10-15 15:34:36,380 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:34:36,434 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:34:41,721 INFO L134 CoverageAnalysis]: Checked inductivity of 170575 backedges. 0 proven. 164450 refuted. 0 times theorem prover too weak. 6125 trivial. 0 not checked. [2018-10-15 15:34:41,722 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:34:41,722 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-15 15:34:41,722 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-15 15:34:41,723 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-15 15:34:41,723 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=2653, Unknown=0, NotChecked=0, Total=2756 [2018-10-15 15:34:41,723 INFO L87 Difference]: Start difference. First operand 1463 states and 1488 transitions. Second operand 53 states. [2018-10-15 15:34:46,869 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:34:46,870 INFO L93 Difference]: Finished difference Result 1576 states and 1603 transitions. [2018-10-15 15:34:46,870 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 78 states. [2018-10-15 15:34:46,870 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 1462 [2018-10-15 15:34:46,872 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:34:46,875 INFO L225 Difference]: With dead ends: 1576 [2018-10-15 15:34:46,875 INFO L226 Difference]: Without dead ends: 1576 [2018-10-15 15:34:46,876 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1225 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=303, Invalid=10203, Unknown=0, NotChecked=0, Total=10506 [2018-10-15 15:34:46,877 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1576 states. [2018-10-15 15:34:46,885 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1576 to 1521. [2018-10-15 15:34:46,885 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1521 states. [2018-10-15 15:34:46,886 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1521 states to 1521 states and 1547 transitions. [2018-10-15 15:34:46,887 INFO L78 Accepts]: Start accepts. Automaton has 1521 states and 1547 transitions. Word has length 1462 [2018-10-15 15:34:46,887 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:34:46,887 INFO L481 AbstractCegarLoop]: Abstraction has 1521 states and 1547 transitions. [2018-10-15 15:34:46,888 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-15 15:34:46,888 INFO L276 IsEmpty]: Start isEmpty. Operand 1521 states and 1547 transitions. [2018-10-15 15:34:46,900 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1521 [2018-10-15 15:34:46,900 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:34:46,901 INFO L375 BasicCegarLoop]: trace histogram [286, 260, 260, 260, 260, 27, 26, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:34:46,901 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:34:46,901 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:34:46,902 INFO L82 PathProgramCache]: Analyzing trace with hash -845283702, now seen corresponding path program 35 times [2018-10-15 15:34:46,902 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:34:46,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:34:51,929 INFO L134 CoverageAnalysis]: Checked inductivity of 184522 backedges. 0 proven. 178152 refuted. 0 times theorem prover too weak. 6370 trivial. 0 not checked. [2018-10-15 15:34:51,929 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:34:51,930 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55] total 55 [2018-10-15 15:34:51,930 INFO L460 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-10-15 15:34:51,931 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-10-15 15:34:51,931 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=2863, Unknown=0, NotChecked=0, Total=2970 [2018-10-15 15:34:51,931 INFO L87 Difference]: Start difference. First operand 1521 states and 1547 transitions. Second operand 55 states. [2018-10-15 15:34:57,652 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:34:57,652 INFO L93 Difference]: Finished difference Result 1634 states and 1662 transitions. [2018-10-15 15:34:57,652 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 81 states. [2018-10-15 15:34:57,653 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 1520 [2018-10-15 15:34:57,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:34:57,659 INFO L225 Difference]: With dead ends: 1634 [2018-10-15 15:34:57,660 INFO L226 Difference]: Without dead ends: 1634 [2018-10-15 15:34:57,661 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 105 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1326 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=315, Invalid=11027, Unknown=0, NotChecked=0, Total=11342 [2018-10-15 15:34:57,662 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1634 states. [2018-10-15 15:34:57,671 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1634 to 1579. [2018-10-15 15:34:57,672 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1579 states. [2018-10-15 15:34:57,673 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1579 states to 1579 states and 1606 transitions. [2018-10-15 15:34:57,674 INFO L78 Accepts]: Start accepts. Automaton has 1579 states and 1606 transitions. Word has length 1520 [2018-10-15 15:34:57,674 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:34:57,675 INFO L481 AbstractCegarLoop]: Abstraction has 1579 states and 1606 transitions. [2018-10-15 15:34:57,675 INFO L482 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-10-15 15:34:57,675 INFO L276 IsEmpty]: Start isEmpty. Operand 1579 states and 1606 transitions. [2018-10-15 15:34:57,690 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1579 [2018-10-15 15:34:57,690 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:34:57,691 INFO L375 BasicCegarLoop]: trace histogram [297, 270, 270, 270, 270, 28, 27, 27, 27, 27, 27, 27, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:34:57,691 INFO L424 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:34:57,691 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:34:57,691 INFO L82 PathProgramCache]: Analyzing trace with hash 694792405, now seen corresponding path program 36 times [2018-10-15 15:34:57,692 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:34:57,740 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:35:03,201 INFO L134 CoverageAnalysis]: Checked inductivity of 199017 backedges. 0 proven. 192402 refuted. 0 times theorem prover too weak. 6615 trivial. 0 not checked. [2018-10-15 15:35:03,202 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:35:03,202 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-15 15:35:03,203 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-15 15:35:03,203 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-15 15:35:03,204 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=3081, Unknown=0, NotChecked=0, Total=3192 [2018-10-15 15:35:03,204 INFO L87 Difference]: Start difference. First operand 1579 states and 1606 transitions. Second operand 57 states. [2018-10-15 15:35:09,143 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:35:09,144 INFO L93 Difference]: Finished difference Result 1692 states and 1721 transitions. [2018-10-15 15:35:09,144 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-10-15 15:35:09,144 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 1578 [2018-10-15 15:35:09,145 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:35:09,149 INFO L225 Difference]: With dead ends: 1692 [2018-10-15 15:35:09,150 INFO L226 Difference]: Without dead ends: 1692 [2018-10-15 15:35:09,151 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 109 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1431 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=327, Invalid=11883, Unknown=0, NotChecked=0, Total=12210 [2018-10-15 15:35:09,151 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1692 states. [2018-10-15 15:35:09,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1692 to 1637. [2018-10-15 15:35:09,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1637 states. [2018-10-15 15:35:09,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1637 states to 1637 states and 1665 transitions. [2018-10-15 15:35:09,162 INFO L78 Accepts]: Start accepts. Automaton has 1637 states and 1665 transitions. Word has length 1578 [2018-10-15 15:35:09,163 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:35:09,163 INFO L481 AbstractCegarLoop]: Abstraction has 1637 states and 1665 transitions. [2018-10-15 15:35:09,163 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-15 15:35:09,163 INFO L276 IsEmpty]: Start isEmpty. Operand 1637 states and 1665 transitions. [2018-10-15 15:35:09,178 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1637 [2018-10-15 15:35:09,178 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:35:09,179 INFO L375 BasicCegarLoop]: trace histogram [308, 280, 280, 280, 280, 29, 28, 28, 28, 28, 28, 28, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:35:09,179 INFO L424 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:35:09,179 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:35:09,179 INFO L82 PathProgramCache]: Analyzing trace with hash 1863704416, now seen corresponding path program 37 times [2018-10-15 15:35:09,180 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:35:09,234 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:35:14,466 INFO L134 CoverageAnalysis]: Checked inductivity of 214060 backedges. 0 proven. 207200 refuted. 0 times theorem prover too weak. 6860 trivial. 0 not checked. [2018-10-15 15:35:14,466 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:35:14,466 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [59] total 59 [2018-10-15 15:35:14,467 INFO L460 AbstractCegarLoop]: Interpolant automaton has 59 states [2018-10-15 15:35:14,467 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 59 interpolants. [2018-10-15 15:35:14,467 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=3307, Unknown=0, NotChecked=0, Total=3422 [2018-10-15 15:35:14,468 INFO L87 Difference]: Start difference. First operand 1637 states and 1665 transitions. Second operand 59 states. [2018-10-15 15:35:20,528 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:35:20,528 INFO L93 Difference]: Finished difference Result 1750 states and 1780 transitions. [2018-10-15 15:35:20,529 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 87 states. [2018-10-15 15:35:20,529 INFO L78 Accepts]: Start accepts. Automaton has 59 states. Word has length 1636 [2018-10-15 15:35:20,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:35:20,536 INFO L225 Difference]: With dead ends: 1750 [2018-10-15 15:35:20,536 INFO L226 Difference]: Without dead ends: 1750 [2018-10-15 15:35:20,537 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1540 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=339, Invalid=12771, Unknown=0, NotChecked=0, Total=13110 [2018-10-15 15:35:20,537 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1750 states. [2018-10-15 15:35:20,546 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1750 to 1695. [2018-10-15 15:35:20,547 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1695 states. [2018-10-15 15:35:20,549 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1695 states to 1695 states and 1724 transitions. [2018-10-15 15:35:20,549 INFO L78 Accepts]: Start accepts. Automaton has 1695 states and 1724 transitions. Word has length 1636 [2018-10-15 15:35:20,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:35:20,550 INFO L481 AbstractCegarLoop]: Abstraction has 1695 states and 1724 transitions. [2018-10-15 15:35:20,550 INFO L482 AbstractCegarLoop]: Interpolant automaton has 59 states. [2018-10-15 15:35:20,550 INFO L276 IsEmpty]: Start isEmpty. Operand 1695 states and 1724 transitions. [2018-10-15 15:35:20,566 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1695 [2018-10-15 15:35:20,566 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:35:20,566 INFO L375 BasicCegarLoop]: trace histogram [319, 290, 290, 290, 290, 30, 29, 29, 29, 29, 29, 29, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:35:20,567 INFO L424 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:35:20,567 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:35:20,567 INFO L82 PathProgramCache]: Analyzing trace with hash -1019037141, now seen corresponding path program 38 times [2018-10-15 15:35:20,568 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:35:20,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:35:25,920 INFO L134 CoverageAnalysis]: Checked inductivity of 229651 backedges. 0 proven. 222546 refuted. 0 times theorem prover too weak. 7105 trivial. 0 not checked. [2018-10-15 15:35:25,921 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:35:25,921 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-15 15:35:25,922 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-15 15:35:25,922 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-15 15:35:25,922 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=3541, Unknown=0, NotChecked=0, Total=3660 [2018-10-15 15:35:25,922 INFO L87 Difference]: Start difference. First operand 1695 states and 1724 transitions. Second operand 61 states. [2018-10-15 15:35:32,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:35:32,297 INFO L93 Difference]: Finished difference Result 1808 states and 1839 transitions. [2018-10-15 15:35:32,298 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 90 states. [2018-10-15 15:35:32,298 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 1694 [2018-10-15 15:35:32,299 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:35:32,304 INFO L225 Difference]: With dead ends: 1808 [2018-10-15 15:35:32,304 INFO L226 Difference]: Without dead ends: 1808 [2018-10-15 15:35:32,304 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 117 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1653 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=351, Invalid=13691, Unknown=0, NotChecked=0, Total=14042 [2018-10-15 15:35:32,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1808 states. [2018-10-15 15:35:32,314 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1808 to 1753. [2018-10-15 15:35:32,314 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1753 states. [2018-10-15 15:35:32,316 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1753 states to 1753 states and 1783 transitions. [2018-10-15 15:35:32,317 INFO L78 Accepts]: Start accepts. Automaton has 1753 states and 1783 transitions. Word has length 1694 [2018-10-15 15:35:32,317 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:35:32,318 INFO L481 AbstractCegarLoop]: Abstraction has 1753 states and 1783 transitions. [2018-10-15 15:35:32,318 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-15 15:35:32,318 INFO L276 IsEmpty]: Start isEmpty. Operand 1753 states and 1783 transitions. [2018-10-15 15:35:32,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1753 [2018-10-15 15:35:32,338 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:35:32,338 INFO L375 BasicCegarLoop]: trace histogram [330, 300, 300, 300, 300, 31, 30, 30, 30, 30, 30, 30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:35:32,339 INFO L424 AbstractCegarLoop]: === Iteration 41 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:35:32,339 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:35:32,339 INFO L82 PathProgramCache]: Analyzing trace with hash 1492414774, now seen corresponding path program 39 times [2018-10-15 15:35:32,340 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:35:32,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:35:38,428 INFO L134 CoverageAnalysis]: Checked inductivity of 245790 backedges. 0 proven. 238440 refuted. 0 times theorem prover too weak. 7350 trivial. 0 not checked. [2018-10-15 15:35:38,428 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:35:38,428 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [63] total 63 [2018-10-15 15:35:38,429 INFO L460 AbstractCegarLoop]: Interpolant automaton has 63 states [2018-10-15 15:35:38,429 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 63 interpolants. [2018-10-15 15:35:38,429 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=3783, Unknown=0, NotChecked=0, Total=3906 [2018-10-15 15:35:38,430 INFO L87 Difference]: Start difference. First operand 1753 states and 1783 transitions. Second operand 63 states. [2018-10-15 15:35:45,648 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:35:45,648 INFO L93 Difference]: Finished difference Result 1866 states and 1898 transitions. [2018-10-15 15:35:45,648 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-10-15 15:35:45,648 INFO L78 Accepts]: Start accepts. Automaton has 63 states. Word has length 1752 [2018-10-15 15:35:45,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:35:45,656 INFO L225 Difference]: With dead ends: 1866 [2018-10-15 15:35:45,656 INFO L226 Difference]: Without dead ends: 1866 [2018-10-15 15:35:45,658 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1770 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=363, Invalid=14643, Unknown=0, NotChecked=0, Total=15006 [2018-10-15 15:35:45,659 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1866 states. [2018-10-15 15:35:45,673 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1866 to 1811. [2018-10-15 15:35:45,673 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1811 states. [2018-10-15 15:35:45,675 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1811 states to 1811 states and 1842 transitions. [2018-10-15 15:35:45,676 INFO L78 Accepts]: Start accepts. Automaton has 1811 states and 1842 transitions. Word has length 1752 [2018-10-15 15:35:45,677 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:35:45,677 INFO L481 AbstractCegarLoop]: Abstraction has 1811 states and 1842 transitions. [2018-10-15 15:35:45,677 INFO L482 AbstractCegarLoop]: Interpolant automaton has 63 states. [2018-10-15 15:35:45,677 INFO L276 IsEmpty]: Start isEmpty. Operand 1811 states and 1842 transitions. [2018-10-15 15:35:45,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1811 [2018-10-15 15:35:45,698 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:35:45,699 INFO L375 BasicCegarLoop]: trace histogram [341, 310, 310, 310, 310, 32, 31, 31, 31, 31, 31, 31, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:35:45,699 INFO L424 AbstractCegarLoop]: === Iteration 42 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:35:45,700 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:35:45,700 INFO L82 PathProgramCache]: Analyzing trace with hash -325897087, now seen corresponding path program 40 times [2018-10-15 15:35:45,701 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:35:45,751 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:35:51,990 INFO L134 CoverageAnalysis]: Checked inductivity of 262477 backedges. 0 proven. 254882 refuted. 0 times theorem prover too weak. 7595 trivial. 0 not checked. [2018-10-15 15:35:51,990 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:35:51,991 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-15 15:35:51,991 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-15 15:35:51,992 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-15 15:35:51,992 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=4033, Unknown=0, NotChecked=0, Total=4160 [2018-10-15 15:35:51,992 INFO L87 Difference]: Start difference. First operand 1811 states and 1842 transitions. Second operand 65 states. [2018-10-15 15:35:59,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:35:59,269 INFO L93 Difference]: Finished difference Result 1924 states and 1957 transitions. [2018-10-15 15:35:59,270 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-10-15 15:35:59,270 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 1810 [2018-10-15 15:35:59,272 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:35:59,278 INFO L225 Difference]: With dead ends: 1924 [2018-10-15 15:35:59,279 INFO L226 Difference]: Without dead ends: 1924 [2018-10-15 15:35:59,280 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 125 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1891 ImplicationChecksByTransitivity, 4.3s TimeCoverageRelationStatistics Valid=375, Invalid=15627, Unknown=0, NotChecked=0, Total=16002 [2018-10-15 15:35:59,281 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1924 states. [2018-10-15 15:35:59,293 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1924 to 1869. [2018-10-15 15:35:59,293 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1869 states. [2018-10-15 15:35:59,295 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1869 states to 1869 states and 1901 transitions. [2018-10-15 15:35:59,296 INFO L78 Accepts]: Start accepts. Automaton has 1869 states and 1901 transitions. Word has length 1810 [2018-10-15 15:35:59,297 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:35:59,297 INFO L481 AbstractCegarLoop]: Abstraction has 1869 states and 1901 transitions. [2018-10-15 15:35:59,297 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-15 15:35:59,297 INFO L276 IsEmpty]: Start isEmpty. Operand 1869 states and 1901 transitions. [2018-10-15 15:35:59,324 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1869 [2018-10-15 15:35:59,324 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:35:59,325 INFO L375 BasicCegarLoop]: trace histogram [352, 320, 320, 320, 320, 33, 32, 32, 32, 32, 32, 32, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:35:59,325 INFO L424 AbstractCegarLoop]: === Iteration 43 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:35:59,325 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:35:59,326 INFO L82 PathProgramCache]: Analyzing trace with hash 2129343500, now seen corresponding path program 41 times [2018-10-15 15:35:59,327 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:35:59,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:36:06,073 INFO L134 CoverageAnalysis]: Checked inductivity of 279712 backedges. 0 proven. 271872 refuted. 0 times theorem prover too weak. 7840 trivial. 0 not checked. [2018-10-15 15:36:06,073 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:36:06,074 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67] total 67 [2018-10-15 15:36:06,075 INFO L460 AbstractCegarLoop]: Interpolant automaton has 67 states [2018-10-15 15:36:06,075 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 67 interpolants. [2018-10-15 15:36:06,075 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=4291, Unknown=0, NotChecked=0, Total=4422 [2018-10-15 15:36:06,075 INFO L87 Difference]: Start difference. First operand 1869 states and 1901 transitions. Second operand 67 states. [2018-10-15 15:36:13,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:36:13,484 INFO L93 Difference]: Finished difference Result 1982 states and 2016 transitions. [2018-10-15 15:36:13,484 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 99 states. [2018-10-15 15:36:13,484 INFO L78 Accepts]: Start accepts. Automaton has 67 states. Word has length 1868 [2018-10-15 15:36:13,486 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:36:13,490 INFO L225 Difference]: With dead ends: 1982 [2018-10-15 15:36:13,490 INFO L226 Difference]: Without dead ends: 1982 [2018-10-15 15:36:13,490 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 129 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2016 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=387, Invalid=16643, Unknown=0, NotChecked=0, Total=17030 [2018-10-15 15:36:13,491 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1982 states. [2018-10-15 15:36:13,504 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1982 to 1927. [2018-10-15 15:36:13,504 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1927 states. [2018-10-15 15:36:13,506 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1927 states to 1927 states and 1960 transitions. [2018-10-15 15:36:13,506 INFO L78 Accepts]: Start accepts. Automaton has 1927 states and 1960 transitions. Word has length 1868 [2018-10-15 15:36:13,507 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:36:13,507 INFO L481 AbstractCegarLoop]: Abstraction has 1927 states and 1960 transitions. [2018-10-15 15:36:13,507 INFO L482 AbstractCegarLoop]: Interpolant automaton has 67 states. [2018-10-15 15:36:13,507 INFO L276 IsEmpty]: Start isEmpty. Operand 1927 states and 1960 transitions. [2018-10-15 15:36:13,526 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1927 [2018-10-15 15:36:13,527 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:36:13,527 INFO L375 BasicCegarLoop]: trace histogram [363, 330, 330, 330, 330, 34, 33, 33, 33, 33, 33, 33, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:36:13,528 INFO L424 AbstractCegarLoop]: === Iteration 44 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:36:13,528 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:36:13,528 INFO L82 PathProgramCache]: Analyzing trace with hash 1345101783, now seen corresponding path program 42 times [2018-10-15 15:36:13,529 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:36:13,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:36:20,769 INFO L134 CoverageAnalysis]: Checked inductivity of 297495 backedges. 0 proven. 289410 refuted. 0 times theorem prover too weak. 8085 trivial. 0 not checked. [2018-10-15 15:36:20,769 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:36:20,769 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-15 15:36:20,770 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-15 15:36:20,770 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-15 15:36:20,771 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=4557, Unknown=0, NotChecked=0, Total=4692 [2018-10-15 15:36:20,771 INFO L87 Difference]: Start difference. First operand 1927 states and 1960 transitions. Second operand 69 states. [2018-10-15 15:36:28,597 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:36:28,597 INFO L93 Difference]: Finished difference Result 2040 states and 2075 transitions. [2018-10-15 15:36:28,597 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 102 states. [2018-10-15 15:36:28,598 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 1926 [2018-10-15 15:36:28,599 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:36:28,602 INFO L225 Difference]: With dead ends: 2040 [2018-10-15 15:36:28,602 INFO L226 Difference]: Without dead ends: 2040 [2018-10-15 15:36:28,603 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 133 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2145 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=399, Invalid=17691, Unknown=0, NotChecked=0, Total=18090 [2018-10-15 15:36:28,604 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2040 states. [2018-10-15 15:36:28,612 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2040 to 1985. [2018-10-15 15:36:28,612 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1985 states. [2018-10-15 15:36:28,614 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1985 states to 1985 states and 2019 transitions. [2018-10-15 15:36:28,614 INFO L78 Accepts]: Start accepts. Automaton has 1985 states and 2019 transitions. Word has length 1926 [2018-10-15 15:36:28,614 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:36:28,615 INFO L481 AbstractCegarLoop]: Abstraction has 1985 states and 2019 transitions. [2018-10-15 15:36:28,615 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-15 15:36:28,615 INFO L276 IsEmpty]: Start isEmpty. Operand 1985 states and 2019 transitions. [2018-10-15 15:36:28,635 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1985 [2018-10-15 15:36:28,635 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:36:28,636 INFO L375 BasicCegarLoop]: trace histogram [374, 340, 340, 340, 340, 35, 34, 34, 34, 34, 34, 34, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:36:28,636 INFO L424 AbstractCegarLoop]: === Iteration 45 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:36:28,637 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:36:28,637 INFO L82 PathProgramCache]: Analyzing trace with hash 451651554, now seen corresponding path program 43 times [2018-10-15 15:36:28,638 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:36:28,685 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:36:36,337 INFO L134 CoverageAnalysis]: Checked inductivity of 315826 backedges. 0 proven. 307496 refuted. 0 times theorem prover too weak. 8330 trivial. 0 not checked. [2018-10-15 15:36:36,338 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:36:36,338 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [71] total 71 [2018-10-15 15:36:36,339 INFO L460 AbstractCegarLoop]: Interpolant automaton has 71 states [2018-10-15 15:36:36,339 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 71 interpolants. [2018-10-15 15:36:36,339 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=4831, Unknown=0, NotChecked=0, Total=4970 [2018-10-15 15:36:36,339 INFO L87 Difference]: Start difference. First operand 1985 states and 2019 transitions. Second operand 71 states. [2018-10-15 15:36:44,587 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:36:44,587 INFO L93 Difference]: Finished difference Result 2098 states and 2134 transitions. [2018-10-15 15:36:44,588 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 105 states. [2018-10-15 15:36:44,588 INFO L78 Accepts]: Start accepts. Automaton has 71 states. Word has length 1984 [2018-10-15 15:36:44,589 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:36:44,592 INFO L225 Difference]: With dead ends: 2098 [2018-10-15 15:36:44,592 INFO L226 Difference]: Without dead ends: 2098 [2018-10-15 15:36:44,593 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 137 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2278 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=411, Invalid=18771, Unknown=0, NotChecked=0, Total=19182 [2018-10-15 15:36:44,594 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2098 states. [2018-10-15 15:36:44,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2098 to 2043. [2018-10-15 15:36:44,603 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2043 states. [2018-10-15 15:36:44,605 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2043 states to 2043 states and 2078 transitions. [2018-10-15 15:36:44,605 INFO L78 Accepts]: Start accepts. Automaton has 2043 states and 2078 transitions. Word has length 1984 [2018-10-15 15:36:44,606 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:36:44,606 INFO L481 AbstractCegarLoop]: Abstraction has 2043 states and 2078 transitions. [2018-10-15 15:36:44,606 INFO L482 AbstractCegarLoop]: Interpolant automaton has 71 states. [2018-10-15 15:36:44,606 INFO L276 IsEmpty]: Start isEmpty. Operand 2043 states and 2078 transitions. [2018-10-15 15:36:44,652 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2043 [2018-10-15 15:36:44,652 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:36:44,653 INFO L375 BasicCegarLoop]: trace histogram [385, 350, 350, 350, 350, 36, 35, 35, 35, 35, 35, 35, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:36:44,653 INFO L424 AbstractCegarLoop]: === Iteration 46 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:36:44,653 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:36:44,654 INFO L82 PathProgramCache]: Analyzing trace with hash -1893696467, now seen corresponding path program 44 times [2018-10-15 15:36:44,654 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:36:44,712 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:36:52,530 INFO L134 CoverageAnalysis]: Checked inductivity of 334705 backedges. 0 proven. 326130 refuted. 0 times theorem prover too weak. 8575 trivial. 0 not checked. [2018-10-15 15:36:52,530 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:36:52,530 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-15 15:36:52,531 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-15 15:36:52,531 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-15 15:36:52,531 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=5113, Unknown=0, NotChecked=0, Total=5256 [2018-10-15 15:36:52,532 INFO L87 Difference]: Start difference. First operand 2043 states and 2078 transitions. Second operand 73 states. [2018-10-15 15:37:01,295 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:37:01,295 INFO L93 Difference]: Finished difference Result 2156 states and 2193 transitions. [2018-10-15 15:37:01,295 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 108 states. [2018-10-15 15:37:01,296 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 2042 [2018-10-15 15:37:01,297 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:37:01,299 INFO L225 Difference]: With dead ends: 2156 [2018-10-15 15:37:01,299 INFO L226 Difference]: Without dead ends: 2156 [2018-10-15 15:37:01,300 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 141 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2415 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=423, Invalid=19883, Unknown=0, NotChecked=0, Total=20306 [2018-10-15 15:37:01,301 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2156 states. [2018-10-15 15:37:01,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2156 to 2101. [2018-10-15 15:37:01,312 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2101 states. [2018-10-15 15:37:01,314 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2101 states to 2101 states and 2137 transitions. [2018-10-15 15:37:01,314 INFO L78 Accepts]: Start accepts. Automaton has 2101 states and 2137 transitions. Word has length 2042 [2018-10-15 15:37:01,315 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:37:01,316 INFO L481 AbstractCegarLoop]: Abstraction has 2101 states and 2137 transitions. [2018-10-15 15:37:01,316 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-15 15:37:01,316 INFO L276 IsEmpty]: Start isEmpty. Operand 2101 states and 2137 transitions. [2018-10-15 15:37:01,347 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2101 [2018-10-15 15:37:01,347 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:37:01,348 INFO L375 BasicCegarLoop]: trace histogram [396, 360, 360, 360, 360, 37, 36, 36, 36, 36, 36, 36, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:37:01,348 INFO L424 AbstractCegarLoop]: === Iteration 47 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:37:01,349 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:37:01,349 INFO L82 PathProgramCache]: Analyzing trace with hash 220679352, now seen corresponding path program 45 times [2018-10-15 15:37:01,350 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:37:01,419 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:37:09,334 INFO L134 CoverageAnalysis]: Checked inductivity of 354132 backedges. 0 proven. 345312 refuted. 0 times theorem prover too weak. 8820 trivial. 0 not checked. [2018-10-15 15:37:09,335 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:37:09,335 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [75] total 75 [2018-10-15 15:37:09,336 INFO L460 AbstractCegarLoop]: Interpolant automaton has 75 states [2018-10-15 15:37:09,336 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2018-10-15 15:37:09,336 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=147, Invalid=5403, Unknown=0, NotChecked=0, Total=5550 [2018-10-15 15:37:09,336 INFO L87 Difference]: Start difference. First operand 2101 states and 2137 transitions. Second operand 75 states. [2018-10-15 15:37:18,692 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:37:18,692 INFO L93 Difference]: Finished difference Result 2214 states and 2252 transitions. [2018-10-15 15:37:18,692 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 111 states. [2018-10-15 15:37:18,693 INFO L78 Accepts]: Start accepts. Automaton has 75 states. Word has length 2100 [2018-10-15 15:37:18,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:37:18,697 INFO L225 Difference]: With dead ends: 2214 [2018-10-15 15:37:18,697 INFO L226 Difference]: Without dead ends: 2214 [2018-10-15 15:37:18,698 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 145 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2556 ImplicationChecksByTransitivity, 5.4s TimeCoverageRelationStatistics Valid=435, Invalid=21027, Unknown=0, NotChecked=0, Total=21462 [2018-10-15 15:37:18,699 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2214 states. [2018-10-15 15:37:18,711 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2214 to 2159. [2018-10-15 15:37:18,711 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2159 states. [2018-10-15 15:37:18,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2159 states to 2159 states and 2196 transitions. [2018-10-15 15:37:18,714 INFO L78 Accepts]: Start accepts. Automaton has 2159 states and 2196 transitions. Word has length 2100 [2018-10-15 15:37:18,715 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:37:18,715 INFO L481 AbstractCegarLoop]: Abstraction has 2159 states and 2196 transitions. [2018-10-15 15:37:18,715 INFO L482 AbstractCegarLoop]: Interpolant automaton has 75 states. [2018-10-15 15:37:18,715 INFO L276 IsEmpty]: Start isEmpty. Operand 2159 states and 2196 transitions. [2018-10-15 15:37:18,748 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2159 [2018-10-15 15:37:18,749 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:37:18,750 INFO L375 BasicCegarLoop]: trace histogram [407, 370, 370, 370, 370, 38, 37, 37, 37, 37, 37, 37, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:37:18,750 INFO L424 AbstractCegarLoop]: === Iteration 48 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:37:18,750 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:37:18,751 INFO L82 PathProgramCache]: Analyzing trace with hash -1598011005, now seen corresponding path program 46 times [2018-10-15 15:37:18,751 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:37:18,823 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:37:27,571 INFO L134 CoverageAnalysis]: Checked inductivity of 374107 backedges. 0 proven. 365042 refuted. 0 times theorem prover too weak. 9065 trivial. 0 not checked. [2018-10-15 15:37:27,571 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:37:27,572 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-15 15:37:27,572 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-15 15:37:27,573 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-15 15:37:27,573 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=151, Invalid=5701, Unknown=0, NotChecked=0, Total=5852 [2018-10-15 15:37:27,573 INFO L87 Difference]: Start difference. First operand 2159 states and 2196 transitions. Second operand 77 states. [2018-10-15 15:37:37,514 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:37:37,515 INFO L93 Difference]: Finished difference Result 2272 states and 2311 transitions. [2018-10-15 15:37:37,515 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 114 states. [2018-10-15 15:37:37,515 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 2158 [2018-10-15 15:37:37,517 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:37:37,519 INFO L225 Difference]: With dead ends: 2272 [2018-10-15 15:37:37,519 INFO L226 Difference]: Without dead ends: 2272 [2018-10-15 15:37:37,521 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 152 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 149 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2701 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=447, Invalid=22203, Unknown=0, NotChecked=0, Total=22650 [2018-10-15 15:37:37,522 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2272 states. [2018-10-15 15:37:37,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2272 to 2217. [2018-10-15 15:37:37,533 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2217 states. [2018-10-15 15:37:37,536 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2217 states to 2217 states and 2255 transitions. [2018-10-15 15:37:37,536 INFO L78 Accepts]: Start accepts. Automaton has 2217 states and 2255 transitions. Word has length 2158 [2018-10-15 15:37:37,537 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:37:37,537 INFO L481 AbstractCegarLoop]: Abstraction has 2217 states and 2255 transitions. [2018-10-15 15:37:37,537 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-15 15:37:37,537 INFO L276 IsEmpty]: Start isEmpty. Operand 2217 states and 2255 transitions. [2018-10-15 15:37:37,571 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2217 [2018-10-15 15:37:37,571 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:37:37,573 INFO L375 BasicCegarLoop]: trace histogram [418, 380, 380, 380, 380, 39, 38, 38, 38, 38, 38, 38, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:37:37,573 INFO L424 AbstractCegarLoop]: === Iteration 49 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:37:37,573 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:37:37,574 INFO L82 PathProgramCache]: Analyzing trace with hash 1007657614, now seen corresponding path program 47 times [2018-10-15 15:37:37,574 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:37:37,649 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:37:46,308 INFO L134 CoverageAnalysis]: Checked inductivity of 394630 backedges. 0 proven. 385320 refuted. 0 times theorem prover too weak. 9310 trivial. 0 not checked. [2018-10-15 15:37:46,308 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:37:46,309 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [79] total 79 [2018-10-15 15:37:46,309 INFO L460 AbstractCegarLoop]: Interpolant automaton has 79 states [2018-10-15 15:37:46,310 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 79 interpolants. [2018-10-15 15:37:46,310 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=155, Invalid=6007, Unknown=0, NotChecked=0, Total=6162 [2018-10-15 15:37:46,310 INFO L87 Difference]: Start difference. First operand 2217 states and 2255 transitions. Second operand 79 states. [2018-10-15 15:37:56,584 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:37:56,584 INFO L93 Difference]: Finished difference Result 2330 states and 2370 transitions. [2018-10-15 15:37:56,585 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-10-15 15:37:56,585 INFO L78 Accepts]: Start accepts. Automaton has 79 states. Word has length 2216 [2018-10-15 15:37:56,586 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:37:56,588 INFO L225 Difference]: With dead ends: 2330 [2018-10-15 15:37:56,588 INFO L226 Difference]: Without dead ends: 2330 [2018-10-15 15:37:56,590 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 156 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 153 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2850 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=459, Invalid=23411, Unknown=0, NotChecked=0, Total=23870 [2018-10-15 15:37:56,591 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2330 states. [2018-10-15 15:37:56,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2330 to 2275. [2018-10-15 15:37:56,604 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2275 states. [2018-10-15 15:37:56,606 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2275 states to 2275 states and 2314 transitions. [2018-10-15 15:37:56,606 INFO L78 Accepts]: Start accepts. Automaton has 2275 states and 2314 transitions. Word has length 2216 [2018-10-15 15:37:56,608 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:37:56,608 INFO L481 AbstractCegarLoop]: Abstraction has 2275 states and 2314 transitions. [2018-10-15 15:37:56,608 INFO L482 AbstractCegarLoop]: Interpolant automaton has 79 states. [2018-10-15 15:37:56,608 INFO L276 IsEmpty]: Start isEmpty. Operand 2275 states and 2314 transitions. [2018-10-15 15:37:56,643 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2275 [2018-10-15 15:37:56,643 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:37:56,644 INFO L375 BasicCegarLoop]: trace histogram [429, 390, 390, 390, 390, 40, 39, 39, 39, 39, 39, 39, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:37:56,644 INFO L424 AbstractCegarLoop]: === Iteration 50 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:37:56,645 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:37:56,645 INFO L82 PathProgramCache]: Analyzing trace with hash 849184729, now seen corresponding path program 48 times [2018-10-15 15:37:56,646 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:37:56,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:38:06,201 INFO L134 CoverageAnalysis]: Checked inductivity of 415701 backedges. 0 proven. 406146 refuted. 0 times theorem prover too weak. 9555 trivial. 0 not checked. [2018-10-15 15:38:06,201 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:38:06,202 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-15 15:38:06,203 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-15 15:38:06,203 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-15 15:38:06,203 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=159, Invalid=6321, Unknown=0, NotChecked=0, Total=6480 [2018-10-15 15:38:06,203 INFO L87 Difference]: Start difference. First operand 2275 states and 2314 transitions. Second operand 81 states. [2018-10-15 15:38:17,168 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:38:17,169 INFO L93 Difference]: Finished difference Result 2388 states and 2429 transitions. [2018-10-15 15:38:17,169 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 120 states. [2018-10-15 15:38:17,169 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 2274 [2018-10-15 15:38:17,171 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:38:17,173 INFO L225 Difference]: With dead ends: 2388 [2018-10-15 15:38:17,173 INFO L226 Difference]: Without dead ends: 2388 [2018-10-15 15:38:17,174 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 157 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3003 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=471, Invalid=24651, Unknown=0, NotChecked=0, Total=25122 [2018-10-15 15:38:17,175 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2388 states. [2018-10-15 15:38:17,187 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2388 to 2333. [2018-10-15 15:38:17,188 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2333 states. [2018-10-15 15:38:17,190 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2333 states to 2333 states and 2373 transitions. [2018-10-15 15:38:17,191 INFO L78 Accepts]: Start accepts. Automaton has 2333 states and 2373 transitions. Word has length 2274 [2018-10-15 15:38:17,192 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:38:17,192 INFO L481 AbstractCegarLoop]: Abstraction has 2333 states and 2373 transitions. [2018-10-15 15:38:17,192 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-15 15:38:17,192 INFO L276 IsEmpty]: Start isEmpty. Operand 2333 states and 2373 transitions. [2018-10-15 15:38:17,231 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2333 [2018-10-15 15:38:17,232 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:38:17,233 INFO L375 BasicCegarLoop]: trace histogram [440, 400, 400, 400, 400, 41, 40, 40, 40, 40, 40, 40, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:38:17,233 INFO L424 AbstractCegarLoop]: === Iteration 51 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:38:17,233 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:38:17,234 INFO L82 PathProgramCache]: Analyzing trace with hash -195679900, now seen corresponding path program 49 times [2018-10-15 15:38:17,235 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:38:17,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:38:27,170 INFO L134 CoverageAnalysis]: Checked inductivity of 437320 backedges. 0 proven. 427520 refuted. 0 times theorem prover too weak. 9800 trivial. 0 not checked. [2018-10-15 15:38:27,171 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:38:27,171 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [83] total 83 [2018-10-15 15:38:27,172 INFO L460 AbstractCegarLoop]: Interpolant automaton has 83 states [2018-10-15 15:38:27,172 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 83 interpolants. [2018-10-15 15:38:27,172 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=163, Invalid=6643, Unknown=0, NotChecked=0, Total=6806 [2018-10-15 15:38:27,173 INFO L87 Difference]: Start difference. First operand 2333 states and 2373 transitions. Second operand 83 states. [2018-10-15 15:38:38,568 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:38:38,568 INFO L93 Difference]: Finished difference Result 2446 states and 2488 transitions. [2018-10-15 15:38:38,569 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 123 states. [2018-10-15 15:38:38,569 INFO L78 Accepts]: Start accepts. Automaton has 83 states. Word has length 2332 [2018-10-15 15:38:38,571 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:38:38,572 INFO L225 Difference]: With dead ends: 2446 [2018-10-15 15:38:38,572 INFO L226 Difference]: Without dead ends: 2446 [2018-10-15 15:38:38,573 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 161 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3160 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=483, Invalid=25923, Unknown=0, NotChecked=0, Total=26406 [2018-10-15 15:38:38,574 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2446 states. [2018-10-15 15:38:38,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2446 to 2391. [2018-10-15 15:38:38,586 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2391 states. [2018-10-15 15:38:38,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2391 states to 2391 states and 2432 transitions. [2018-10-15 15:38:38,589 INFO L78 Accepts]: Start accepts. Automaton has 2391 states and 2432 transitions. Word has length 2332 [2018-10-15 15:38:38,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:38:38,590 INFO L481 AbstractCegarLoop]: Abstraction has 2391 states and 2432 transitions. [2018-10-15 15:38:38,590 INFO L482 AbstractCegarLoop]: Interpolant automaton has 83 states. [2018-10-15 15:38:38,591 INFO L276 IsEmpty]: Start isEmpty. Operand 2391 states and 2432 transitions. [2018-10-15 15:38:38,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2391 [2018-10-15 15:38:38,633 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:38:38,634 INFO L375 BasicCegarLoop]: trace histogram [451, 410, 410, 410, 410, 42, 41, 41, 41, 41, 41, 41, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:38:38,634 INFO L424 AbstractCegarLoop]: === Iteration 52 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:38:38,634 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:38:38,635 INFO L82 PathProgramCache]: Analyzing trace with hash 143243055, now seen corresponding path program 50 times [2018-10-15 15:38:38,636 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:38:38,716 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:38:48,790 INFO L134 CoverageAnalysis]: Checked inductivity of 459487 backedges. 0 proven. 449442 refuted. 0 times theorem prover too weak. 10045 trivial. 0 not checked. [2018-10-15 15:38:48,791 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:38:48,791 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-15 15:38:48,792 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-15 15:38:48,792 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-15 15:38:48,792 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=167, Invalid=6973, Unknown=0, NotChecked=0, Total=7140 [2018-10-15 15:38:48,792 INFO L87 Difference]: Start difference. First operand 2391 states and 2432 transitions. Second operand 85 states. [2018-10-15 15:39:00,884 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:39:00,884 INFO L93 Difference]: Finished difference Result 2504 states and 2547 transitions. [2018-10-15 15:39:00,884 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 126 states. [2018-10-15 15:39:00,885 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 2390 [2018-10-15 15:39:00,886 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:39:00,887 INFO L225 Difference]: With dead ends: 2504 [2018-10-15 15:39:00,887 INFO L226 Difference]: Without dead ends: 2504 [2018-10-15 15:39:00,888 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 168 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 165 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3321 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=495, Invalid=27227, Unknown=0, NotChecked=0, Total=27722 [2018-10-15 15:39:00,889 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2504 states. [2018-10-15 15:39:00,898 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2504 to 2449. [2018-10-15 15:39:00,898 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2449 states. [2018-10-15 15:39:00,900 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2449 states to 2449 states and 2491 transitions. [2018-10-15 15:39:00,900 INFO L78 Accepts]: Start accepts. Automaton has 2449 states and 2491 transitions. Word has length 2390 [2018-10-15 15:39:00,901 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:39:00,901 INFO L481 AbstractCegarLoop]: Abstraction has 2449 states and 2491 transitions. [2018-10-15 15:39:00,901 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-15 15:39:00,901 INFO L276 IsEmpty]: Start isEmpty. Operand 2449 states and 2491 transitions. [2018-10-15 15:39:00,935 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2449 [2018-10-15 15:39:00,935 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:39:00,936 INFO L375 BasicCegarLoop]: trace histogram [462, 420, 420, 420, 420, 43, 42, 42, 42, 42, 42, 42, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:39:00,936 INFO L424 AbstractCegarLoop]: === Iteration 53 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:39:00,936 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:39:00,937 INFO L82 PathProgramCache]: Analyzing trace with hash 1223450938, now seen corresponding path program 51 times [2018-10-15 15:39:00,937 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:39:00,998 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:39:11,654 INFO L134 CoverageAnalysis]: Checked inductivity of 482202 backedges. 0 proven. 471912 refuted. 0 times theorem prover too weak. 10290 trivial. 0 not checked. [2018-10-15 15:39:11,655 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:39:11,655 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [87] total 87 [2018-10-15 15:39:11,656 INFO L460 AbstractCegarLoop]: Interpolant automaton has 87 states [2018-10-15 15:39:11,656 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 87 interpolants. [2018-10-15 15:39:11,656 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=171, Invalid=7311, Unknown=0, NotChecked=0, Total=7482 [2018-10-15 15:39:11,656 INFO L87 Difference]: Start difference. First operand 2449 states and 2491 transitions. Second operand 87 states. [2018-10-15 15:39:24,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:39:24,213 INFO L93 Difference]: Finished difference Result 2562 states and 2606 transitions. [2018-10-15 15:39:24,213 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 129 states. [2018-10-15 15:39:24,213 INFO L78 Accepts]: Start accepts. Automaton has 87 states. Word has length 2448 [2018-10-15 15:39:24,215 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:39:24,217 INFO L225 Difference]: With dead ends: 2562 [2018-10-15 15:39:24,217 INFO L226 Difference]: Without dead ends: 2562 [2018-10-15 15:39:24,218 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 172 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 169 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3486 ImplicationChecksByTransitivity, 7.6s TimeCoverageRelationStatistics Valid=507, Invalid=28563, Unknown=0, NotChecked=0, Total=29070 [2018-10-15 15:39:24,219 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2562 states. [2018-10-15 15:39:24,228 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2562 to 2507. [2018-10-15 15:39:24,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2507 states. [2018-10-15 15:39:24,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2507 states to 2507 states and 2550 transitions. [2018-10-15 15:39:24,231 INFO L78 Accepts]: Start accepts. Automaton has 2507 states and 2550 transitions. Word has length 2448 [2018-10-15 15:39:24,231 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:39:24,232 INFO L481 AbstractCegarLoop]: Abstraction has 2507 states and 2550 transitions. [2018-10-15 15:39:24,232 INFO L482 AbstractCegarLoop]: Interpolant automaton has 87 states. [2018-10-15 15:39:24,232 INFO L276 IsEmpty]: Start isEmpty. Operand 2507 states and 2550 transitions. [2018-10-15 15:39:24,263 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2507 [2018-10-15 15:39:24,264 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:39:24,264 INFO L375 BasicCegarLoop]: trace histogram [473, 430, 430, 430, 430, 44, 43, 43, 43, 43, 43, 43, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:39:24,265 INFO L424 AbstractCegarLoop]: === Iteration 54 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:39:24,265 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:39:24,265 INFO L82 PathProgramCache]: Analyzing trace with hash 1553356677, now seen corresponding path program 52 times [2018-10-15 15:39:24,266 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:39:24,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:39:35,561 INFO L134 CoverageAnalysis]: Checked inductivity of 505465 backedges. 0 proven. 494930 refuted. 0 times theorem prover too weak. 10535 trivial. 0 not checked. [2018-10-15 15:39:35,561 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:39:35,561 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-15 15:39:35,562 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-15 15:39:35,562 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-15 15:39:35,562 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=175, Invalid=7657, Unknown=0, NotChecked=0, Total=7832 [2018-10-15 15:39:35,563 INFO L87 Difference]: Start difference. First operand 2507 states and 2550 transitions. Second operand 89 states. [2018-10-15 15:39:48,614 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:39:48,615 INFO L93 Difference]: Finished difference Result 2620 states and 2665 transitions. [2018-10-15 15:39:48,615 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 132 states. [2018-10-15 15:39:48,615 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 2506 [2018-10-15 15:39:48,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:39:48,618 INFO L225 Difference]: With dead ends: 2620 [2018-10-15 15:39:48,618 INFO L226 Difference]: Without dead ends: 2620 [2018-10-15 15:39:48,619 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 173 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3655 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=519, Invalid=29931, Unknown=0, NotChecked=0, Total=30450 [2018-10-15 15:39:48,621 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2620 states. [2018-10-15 15:39:48,630 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2620 to 2565. [2018-10-15 15:39:48,630 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2565 states. [2018-10-15 15:39:48,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2565 states to 2565 states and 2609 transitions. [2018-10-15 15:39:48,632 INFO L78 Accepts]: Start accepts. Automaton has 2565 states and 2609 transitions. Word has length 2506 [2018-10-15 15:39:48,633 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:39:48,634 INFO L481 AbstractCegarLoop]: Abstraction has 2565 states and 2609 transitions. [2018-10-15 15:39:48,634 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-15 15:39:48,634 INFO L276 IsEmpty]: Start isEmpty. Operand 2565 states and 2609 transitions. [2018-10-15 15:39:48,667 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2565 [2018-10-15 15:39:48,668 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:39:48,669 INFO L375 BasicCegarLoop]: trace histogram [484, 440, 440, 440, 440, 45, 44, 44, 44, 44, 44, 44, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:39:48,669 INFO L424 AbstractCegarLoop]: === Iteration 55 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:39:48,669 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:39:48,670 INFO L82 PathProgramCache]: Analyzing trace with hash 1929628176, now seen corresponding path program 53 times [2018-10-15 15:39:48,670 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:39:48,731 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:40:00,560 INFO L134 CoverageAnalysis]: Checked inductivity of 529276 backedges. 0 proven. 518496 refuted. 0 times theorem prover too weak. 10780 trivial. 0 not checked. [2018-10-15 15:40:00,561 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:40:00,561 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [91] total 91 [2018-10-15 15:40:00,562 INFO L460 AbstractCegarLoop]: Interpolant automaton has 91 states [2018-10-15 15:40:00,562 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 91 interpolants. [2018-10-15 15:40:00,562 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=179, Invalid=8011, Unknown=0, NotChecked=0, Total=8190 [2018-10-15 15:40:00,562 INFO L87 Difference]: Start difference. First operand 2565 states and 2609 transitions. Second operand 91 states. [2018-10-15 15:40:14,602 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:40:14,602 INFO L93 Difference]: Finished difference Result 2678 states and 2724 transitions. [2018-10-15 15:40:14,602 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 135 states. [2018-10-15 15:40:14,602 INFO L78 Accepts]: Start accepts. Automaton has 91 states. Word has length 2564 [2018-10-15 15:40:14,605 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:40:14,606 INFO L225 Difference]: With dead ends: 2678 [2018-10-15 15:40:14,606 INFO L226 Difference]: Without dead ends: 2678 [2018-10-15 15:40:14,607 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 177 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3828 ImplicationChecksByTransitivity, 8.4s TimeCoverageRelationStatistics Valid=531, Invalid=31331, Unknown=0, NotChecked=0, Total=31862 [2018-10-15 15:40:14,608 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2678 states. [2018-10-15 15:40:14,618 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2678 to 2623. [2018-10-15 15:40:14,618 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2623 states. [2018-10-15 15:40:14,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2623 states to 2623 states and 2668 transitions. [2018-10-15 15:40:14,620 INFO L78 Accepts]: Start accepts. Automaton has 2623 states and 2668 transitions. Word has length 2564 [2018-10-15 15:40:14,622 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:40:14,622 INFO L481 AbstractCegarLoop]: Abstraction has 2623 states and 2668 transitions. [2018-10-15 15:40:14,622 INFO L482 AbstractCegarLoop]: Interpolant automaton has 91 states. [2018-10-15 15:40:14,622 INFO L276 IsEmpty]: Start isEmpty. Operand 2623 states and 2668 transitions. [2018-10-15 15:40:14,658 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2623 [2018-10-15 15:40:14,658 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:40:14,659 INFO L375 BasicCegarLoop]: trace histogram [495, 450, 450, 450, 450, 46, 45, 45, 45, 45, 45, 45, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:40:14,660 INFO L424 AbstractCegarLoop]: === Iteration 56 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:40:14,660 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:40:14,660 INFO L82 PathProgramCache]: Analyzing trace with hash 1058334939, now seen corresponding path program 54 times [2018-10-15 15:40:14,661 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:40:14,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:40:27,114 INFO L134 CoverageAnalysis]: Checked inductivity of 553635 backedges. 0 proven. 542610 refuted. 0 times theorem prover too weak. 11025 trivial. 0 not checked. [2018-10-15 15:40:27,114 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:40:27,115 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-15 15:40:27,116 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-15 15:40:27,116 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-15 15:40:27,116 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=183, Invalid=8373, Unknown=0, NotChecked=0, Total=8556 [2018-10-15 15:40:27,117 INFO L87 Difference]: Start difference. First operand 2623 states and 2668 transitions. Second operand 93 states. [2018-10-15 15:40:41,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:40:41,094 INFO L93 Difference]: Finished difference Result 2736 states and 2783 transitions. [2018-10-15 15:40:41,094 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 138 states. [2018-10-15 15:40:41,094 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 2622 [2018-10-15 15:40:41,096 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:40:41,097 INFO L225 Difference]: With dead ends: 2736 [2018-10-15 15:40:41,097 INFO L226 Difference]: Without dead ends: 2736 [2018-10-15 15:40:41,098 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 181 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4005 ImplicationChecksByTransitivity, 8.3s TimeCoverageRelationStatistics Valid=543, Invalid=32763, Unknown=0, NotChecked=0, Total=33306 [2018-10-15 15:40:41,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2736 states. [2018-10-15 15:40:41,108 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2736 to 2681. [2018-10-15 15:40:41,108 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2681 states. [2018-10-15 15:40:41,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2681 states to 2681 states and 2727 transitions. [2018-10-15 15:40:41,110 INFO L78 Accepts]: Start accepts. Automaton has 2681 states and 2727 transitions. Word has length 2622 [2018-10-15 15:40:41,111 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:40:41,112 INFO L481 AbstractCegarLoop]: Abstraction has 2681 states and 2727 transitions. [2018-10-15 15:40:41,112 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-15 15:40:41,112 INFO L276 IsEmpty]: Start isEmpty. Operand 2681 states and 2727 transitions. [2018-10-15 15:40:41,147 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2681 [2018-10-15 15:40:41,148 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:40:41,148 INFO L375 BasicCegarLoop]: trace histogram [506, 460, 460, 460, 460, 47, 46, 46, 46, 46, 46, 46, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:40:41,148 INFO L424 AbstractCegarLoop]: === Iteration 57 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:40:41,149 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:40:41,149 INFO L82 PathProgramCache]: Analyzing trace with hash 839771110, now seen corresponding path program 55 times [2018-10-15 15:40:41,150 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:40:41,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:40:54,285 INFO L134 CoverageAnalysis]: Checked inductivity of 578542 backedges. 0 proven. 567272 refuted. 0 times theorem prover too weak. 11270 trivial. 0 not checked. [2018-10-15 15:40:54,285 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:40:54,285 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [95] total 95 [2018-10-15 15:40:54,286 INFO L460 AbstractCegarLoop]: Interpolant automaton has 95 states [2018-10-15 15:40:54,287 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 95 interpolants. [2018-10-15 15:40:54,287 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=187, Invalid=8743, Unknown=0, NotChecked=0, Total=8930 [2018-10-15 15:40:54,287 INFO L87 Difference]: Start difference. First operand 2681 states and 2727 transitions. Second operand 95 states. [2018-10-15 15:41:08,962 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:41:08,962 INFO L93 Difference]: Finished difference Result 2794 states and 2842 transitions. [2018-10-15 15:41:08,962 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 141 states. [2018-10-15 15:41:08,963 INFO L78 Accepts]: Start accepts. Automaton has 95 states. Word has length 2680 [2018-10-15 15:41:08,964 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:41:08,965 INFO L225 Difference]: With dead ends: 2794 [2018-10-15 15:41:08,965 INFO L226 Difference]: Without dead ends: 2794 [2018-10-15 15:41:08,966 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 188 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4186 ImplicationChecksByTransitivity, 9.1s TimeCoverageRelationStatistics Valid=555, Invalid=34227, Unknown=0, NotChecked=0, Total=34782 [2018-10-15 15:41:08,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2794 states. [2018-10-15 15:41:08,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2794 to 2739. [2018-10-15 15:41:08,976 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2739 states. [2018-10-15 15:41:08,978 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2739 states to 2739 states and 2786 transitions. [2018-10-15 15:41:08,978 INFO L78 Accepts]: Start accepts. Automaton has 2739 states and 2786 transitions. Word has length 2680 [2018-10-15 15:41:08,979 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:41:08,979 INFO L481 AbstractCegarLoop]: Abstraction has 2739 states and 2786 transitions. [2018-10-15 15:41:08,979 INFO L482 AbstractCegarLoop]: Interpolant automaton has 95 states. [2018-10-15 15:41:08,979 INFO L276 IsEmpty]: Start isEmpty. Operand 2739 states and 2786 transitions. [2018-10-15 15:41:09,015 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2739 [2018-10-15 15:41:09,016 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:41:09,016 INFO L375 BasicCegarLoop]: trace histogram [517, 470, 470, 470, 470, 48, 47, 47, 47, 47, 47, 47, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:41:09,016 INFO L424 AbstractCegarLoop]: === Iteration 58 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:41:09,017 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:41:09,017 INFO L82 PathProgramCache]: Analyzing trace with hash -157881551, now seen corresponding path program 56 times [2018-10-15 15:41:09,017 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:41:09,082 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat