java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data --generate-csv --csv-dir csv -tc ../../../trunk/examples/toolchains/AutomizerBpl.xml -s ../../../trunk/examples/settings/heapseparator/heapsep-2018-09-18.epf -i ../../../trunk/examples/programs/20170304-DifficultPathPrograms/nested1.i_4.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-d769cf3 [2018-10-15 15:06:31,918 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-15 15:06:31,920 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-15 15:06:31,932 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-15 15:06:31,932 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-15 15:06:31,933 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-15 15:06:31,934 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-15 15:06:31,936 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-15 15:06:31,938 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-15 15:06:31,938 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-15 15:06:31,939 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-15 15:06:31,939 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-15 15:06:31,940 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-15 15:06:31,941 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-15 15:06:31,944 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-15 15:06:31,945 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-15 15:06:31,946 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-15 15:06:31,947 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-15 15:06:31,952 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-15 15:06:31,957 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-15 15:06:31,958 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-15 15:06:31,962 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-15 15:06:31,964 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-15 15:06:31,966 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-15 15:06:31,967 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-15 15:06:31,967 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-15 15:06:31,968 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-15 15:06:31,971 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-15 15:06:31,972 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-15 15:06:31,973 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-15 15:06:31,973 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-15 15:06:31,974 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-15 15:06:31,975 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-15 15:06:31,975 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-15 15:06:31,977 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-15 15:06:31,978 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-15 15:06:31,978 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:06:31,994 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-15 15:06:31,995 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-15 15:06:31,996 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-15 15:06:31,996 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-15 15:06:31,997 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-15 15:06:31,997 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-15 15:06:31,997 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-15 15:06:31,998 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-15 15:06:31,998 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-15 15:06:31,998 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-15 15:06:31,998 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-15 15:06:31,998 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-15 15:06:31,999 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-15 15:06:32,000 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-15 15:06:32,000 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-15 15:06:32,064 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-15 15:06:32,078 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-15 15:06:32,083 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-15 15:06:32,085 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-15 15:06:32,085 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-15 15:06:32,086 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:06:32,086 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20170304-DifficultPathPrograms/nested1.i_4.bpl' [2018-10-15 15:06:32,136 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-15 15:06:32,138 INFO L131 ToolchainWalker]: Walking toolchain with 3 elements. [2018-10-15 15:06:32,138 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-15 15:06:32,138 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-15 15:06:32,139 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-15 15:06:32,165 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:06:32" (1/1) ... [2018-10-15 15:06:32,167 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:06:32" (1/1) ... [2018-10-15 15:06:32,177 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:06:32" (1/1) ... [2018-10-15 15:06:32,177 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:06:32" (1/1) ... [2018-10-15 15:06:32,180 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:06:32" (1/1) ... [2018-10-15 15:06:32,182 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:06:32" (1/1) ... [2018-10-15 15:06:32,182 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:06:32" (1/1) ... [2018-10-15 15:06:32,184 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-15 15:06:32,185 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-15 15:06:32,185 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-15 15:06:32,185 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-15 15:06:32,186 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:06:32" (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:06:32,248 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-15 15:06:32,248 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-15 15:06:32,548 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-15 15:06:32,548 INFO L202 PluginConnector]: Adding new model nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 15.10 03:06:32 BoogieIcfgContainer [2018-10-15 15:06:32,549 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-15 15:06:32,550 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-15 15:06:32,550 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-15 15:06:32,556 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-15 15:06:32,556 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:06:32" (1/2) ... [2018-10-15 15:06:32,557 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@71d82ec and model type nested1.i_4.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 15.10 03:06:32, skipping insertion in model container [2018-10-15 15:06:32,558 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:06:32" (2/2) ... [2018-10-15 15:06:32,561 INFO L112 eAbstractionObserver]: Analyzing ICFG nested1.i_4.bpl [2018-10-15 15:06:32,584 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-15 15:06:32,596 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-15 15:06:32,619 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-15 15:06:32,648 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-15 15:06:32,648 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-15 15:06:32,649 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-15 15:06:32,649 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-15 15:06:32,649 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-15 15:06:32,649 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-15 15:06:32,649 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-15 15:06:32,650 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-15 15:06:32,650 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-15 15:06:32,666 INFO L276 IsEmpty]: Start isEmpty. Operand 22 states. [2018-10-15 15:06:32,674 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2018-10-15 15:06:32,675 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:32,676 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-15 15:06:32,677 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:32,683 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:32,684 INFO L82 PathProgramCache]: Analyzing trace with hash 502726126, now seen corresponding path program 1 times [2018-10-15 15:06:32,746 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:32,798 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:32,889 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:06:32,891 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-15 15:06:32,892 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-15 15:06:32,895 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-15 15:06:32,908 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-15 15:06:32,908 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-15 15:06:32,910 INFO L87 Difference]: Start difference. First operand 22 states. Second operand 3 states. [2018-10-15 15:06:32,979 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:32,979 INFO L93 Difference]: Finished difference Result 32 states and 34 transitions. [2018-10-15 15:06:32,980 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-15 15:06:32,981 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 12 [2018-10-15 15:06:32,981 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:32,991 INFO L225 Difference]: With dead ends: 32 [2018-10-15 15:06:32,991 INFO L226 Difference]: Without dead ends: 32 [2018-10-15 15:06:32,994 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:06:33,012 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2018-10-15 15:06:33,027 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 24. [2018-10-15 15:06:33,028 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 24 states. [2018-10-15 15:06:33,029 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 24 states to 24 states and 25 transitions. [2018-10-15 15:06:33,031 INFO L78 Accepts]: Start accepts. Automaton has 24 states and 25 transitions. Word has length 12 [2018-10-15 15:06:33,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:33,031 INFO L481 AbstractCegarLoop]: Abstraction has 24 states and 25 transitions. [2018-10-15 15:06:33,031 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-15 15:06:33,031 INFO L276 IsEmpty]: Start isEmpty. Operand 24 states and 25 transitions. [2018-10-15 15:06:33,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2018-10-15 15:06:33,032 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:33,032 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:06:33,033 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:33,033 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:33,033 INFO L82 PathProgramCache]: Analyzing trace with hash -820818048, now seen corresponding path program 1 times [2018-10-15 15:06:33,034 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:33,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:33,082 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:06:33,083 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-15 15:06:33,083 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-10-15 15:06:33,085 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-10-15 15:06:33,085 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-10-15 15:06:33,085 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-10-15 15:06:33,086 INFO L87 Difference]: Start difference. First operand 24 states and 25 transitions. Second operand 3 states. [2018-10-15 15:06:33,141 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:33,141 INFO L93 Difference]: Finished difference Result 29 states and 30 transitions. [2018-10-15 15:06:33,141 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-10-15 15:06:33,142 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 20 [2018-10-15 15:06:33,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:33,143 INFO L225 Difference]: With dead ends: 29 [2018-10-15 15:06:33,143 INFO L226 Difference]: Without dead ends: 29 [2018-10-15 15:06:33,144 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:06:33,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2018-10-15 15:06:33,147 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 26. [2018-10-15 15:06:33,147 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 26 states. [2018-10-15 15:06:33,148 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 27 transitions. [2018-10-15 15:06:33,148 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 27 transitions. Word has length 20 [2018-10-15 15:06:33,149 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:33,149 INFO L481 AbstractCegarLoop]: Abstraction has 26 states and 27 transitions. [2018-10-15 15:06:33,149 INFO L482 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-10-15 15:06:33,149 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 27 transitions. [2018-10-15 15:06:33,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-10-15 15:06:33,150 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:33,150 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:06:33,150 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:33,151 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:33,151 INFO L82 PathProgramCache]: Analyzing trace with hash 1806874318, now seen corresponding path program 1 times [2018-10-15 15:06:33,152 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:33,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:33,261 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:06:33,262 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:33,262 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5] total 5 [2018-10-15 15:06:33,263 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-15 15:06:33,263 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-15 15:06:33,263 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-10-15 15:06:33,264 INFO L87 Difference]: Start difference. First operand 26 states and 27 transitions. Second operand 5 states. [2018-10-15 15:06:33,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:33,560 INFO L93 Difference]: Finished difference Result 34 states and 35 transitions. [2018-10-15 15:06:33,561 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-15 15:06:33,561 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 25 [2018-10-15 15:06:33,561 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:33,562 INFO L225 Difference]: With dead ends: 34 [2018-10-15 15:06:33,562 INFO L226 Difference]: Without dead ends: 34 [2018-10-15 15:06:33,563 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 2 SyntacticMatches, 0 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:06:33,563 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2018-10-15 15:06:33,566 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 31. [2018-10-15 15:06:33,566 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 31 states. [2018-10-15 15:06:33,567 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-10-15 15:06:33,568 INFO L78 Accepts]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 25 [2018-10-15 15:06:33,568 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:33,568 INFO L481 AbstractCegarLoop]: Abstraction has 31 states and 32 transitions. [2018-10-15 15:06:33,568 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-15 15:06:33,568 INFO L276 IsEmpty]: Start isEmpty. Operand 31 states and 32 transitions. [2018-10-15 15:06:33,569 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2018-10-15 15:06:33,569 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:33,570 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:06:33,570 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:33,570 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:33,570 INFO L82 PathProgramCache]: Analyzing trace with hash 582332480, now seen corresponding path program 2 times [2018-10-15 15:06:33,571 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:33,586 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:33,838 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:06:33,839 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:33,839 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2018-10-15 15:06:33,839 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-15 15:06:33,839 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-15 15:06:33,840 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-10-15 15:06:33,840 INFO L87 Difference]: Start difference. First operand 31 states and 32 transitions. Second operand 7 states. [2018-10-15 15:06:34,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:34,130 INFO L93 Difference]: Finished difference Result 39 states and 40 transitions. [2018-10-15 15:06:34,131 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-15 15:06:34,131 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 30 [2018-10-15 15:06:34,131 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:34,133 INFO L225 Difference]: With dead ends: 39 [2018-10-15 15:06:34,133 INFO L226 Difference]: Without dead ends: 39 [2018-10-15 15:06:34,134 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:06:34,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2018-10-15 15:06:34,138 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 36. [2018-10-15 15:06:34,138 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 36 states. [2018-10-15 15:06:34,139 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 37 transitions. [2018-10-15 15:06:34,140 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 37 transitions. Word has length 30 [2018-10-15 15:06:34,140 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:34,140 INFO L481 AbstractCegarLoop]: Abstraction has 36 states and 37 transitions. [2018-10-15 15:06:34,140 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-15 15:06:34,141 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 37 transitions. [2018-10-15 15:06:34,142 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2018-10-15 15:06:34,142 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:34,142 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:06:34,142 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:34,143 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:34,143 INFO L82 PathProgramCache]: Analyzing trace with hash 640601614, now seen corresponding path program 3 times [2018-10-15 15:06:34,144 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:34,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:34,402 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:06:34,402 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:34,403 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-15 15:06:34,403 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-15 15:06:34,403 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-15 15:06:34,404 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-10-15 15:06:34,404 INFO L87 Difference]: Start difference. First operand 36 states and 37 transitions. Second operand 9 states. [2018-10-15 15:06:35,036 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:35,037 INFO L93 Difference]: Finished difference Result 44 states and 45 transitions. [2018-10-15 15:06:35,038 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-10-15 15:06:35,038 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 35 [2018-10-15 15:06:35,039 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:35,039 INFO L225 Difference]: With dead ends: 44 [2018-10-15 15:06:35,039 INFO L226 Difference]: Without dead ends: 44 [2018-10-15 15:06:35,040 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:06:35,041 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2018-10-15 15:06:35,044 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 41. [2018-10-15 15:06:35,045 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 41 states. [2018-10-15 15:06:35,046 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 42 transitions. [2018-10-15 15:06:35,046 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 42 transitions. Word has length 35 [2018-10-15 15:06:35,046 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:35,046 INFO L481 AbstractCegarLoop]: Abstraction has 41 states and 42 transitions. [2018-10-15 15:06:35,047 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-15 15:06:35,047 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 42 transitions. [2018-10-15 15:06:35,048 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-10-15 15:06:35,048 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:35,048 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:06:35,049 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:35,049 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:35,049 INFO L82 PathProgramCache]: Analyzing trace with hash 1113989376, now seen corresponding path program 4 times [2018-10-15 15:06:35,050 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:35,070 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:35,282 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:06:35,282 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:35,283 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2018-10-15 15:06:35,283 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-15 15:06:35,283 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-15 15:06:35,283 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=91, Unknown=0, NotChecked=0, Total=110 [2018-10-15 15:06:35,284 INFO L87 Difference]: Start difference. First operand 41 states and 42 transitions. Second operand 11 states. [2018-10-15 15:06:35,744 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:35,744 INFO L93 Difference]: Finished difference Result 49 states and 50 transitions. [2018-10-15 15:06:35,750 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-15 15:06:35,750 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 40 [2018-10-15 15:06:35,750 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:35,751 INFO L225 Difference]: With dead ends: 49 [2018-10-15 15:06:35,751 INFO L226 Difference]: Without dead ends: 49 [2018-10-15 15:06:35,752 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:06:35,752 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2018-10-15 15:06:35,758 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 46. [2018-10-15 15:06:35,758 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 46 states. [2018-10-15 15:06:35,759 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 47 transitions. [2018-10-15 15:06:35,763 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 47 transitions. Word has length 40 [2018-10-15 15:06:35,763 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:35,763 INFO L481 AbstractCegarLoop]: Abstraction has 46 states and 47 transitions. [2018-10-15 15:06:35,763 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-15 15:06:35,764 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 47 transitions. [2018-10-15 15:06:35,764 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2018-10-15 15:06:35,765 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:35,767 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:06:35,767 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:35,767 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:35,768 INFO L82 PathProgramCache]: Analyzing trace with hash -1159277234, now seen corresponding path program 5 times [2018-10-15 15:06:35,769 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:35,796 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:36,292 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:06:36,293 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:36,293 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-15 15:06:36,294 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-15 15:06:36,294 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-15 15:06:36,294 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-10-15 15:06:36,295 INFO L87 Difference]: Start difference. First operand 46 states and 47 transitions. Second operand 13 states. [2018-10-15 15:06:36,893 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:36,893 INFO L93 Difference]: Finished difference Result 54 states and 55 transitions. [2018-10-15 15:06:36,896 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-15 15:06:36,897 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 45 [2018-10-15 15:06:36,897 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:36,898 INFO L225 Difference]: With dead ends: 54 [2018-10-15 15:06:36,899 INFO L226 Difference]: Without dead ends: 54 [2018-10-15 15:06:36,900 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=63, Invalid=443, Unknown=0, NotChecked=0, Total=506 [2018-10-15 15:06:36,900 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2018-10-15 15:06:36,903 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 51. [2018-10-15 15:06:36,903 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 51 states. [2018-10-15 15:06:36,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 52 transitions. [2018-10-15 15:06:36,905 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 52 transitions. Word has length 45 [2018-10-15 15:06:36,905 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:36,905 INFO L481 AbstractCegarLoop]: Abstraction has 51 states and 52 transitions. [2018-10-15 15:06:36,905 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-15 15:06:36,906 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 52 transitions. [2018-10-15 15:06:36,906 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2018-10-15 15:06:36,907 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:36,907 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:06:36,907 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:36,907 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:36,908 INFO L82 PathProgramCache]: Analyzing trace with hash 1070637504, now seen corresponding path program 6 times [2018-10-15 15:06:36,908 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:36,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:37,675 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:06:37,675 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:37,675 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-10-15 15:06:37,676 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-15 15:06:37,676 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-15 15:06:37,676 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-10-15 15:06:37,677 INFO L87 Difference]: Start difference. First operand 51 states and 52 transitions. Second operand 15 states. [2018-10-15 15:06:38,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:38,154 INFO L93 Difference]: Finished difference Result 59 states and 60 transitions. [2018-10-15 15:06:38,156 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-10-15 15:06:38,156 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 50 [2018-10-15 15:06:38,157 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:38,157 INFO L225 Difference]: With dead ends: 59 [2018-10-15 15:06:38,157 INFO L226 Difference]: Without dead ends: 59 [2018-10-15 15:06:38,158 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=75, Invalid=627, Unknown=0, NotChecked=0, Total=702 [2018-10-15 15:06:38,158 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2018-10-15 15:06:38,165 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 56. [2018-10-15 15:06:38,165 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 56 states. [2018-10-15 15:06:38,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 57 transitions. [2018-10-15 15:06:38,169 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 57 transitions. Word has length 50 [2018-10-15 15:06:38,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:38,169 INFO L481 AbstractCegarLoop]: Abstraction has 56 states and 57 transitions. [2018-10-15 15:06:38,169 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-15 15:06:38,169 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 57 transitions. [2018-10-15 15:06:38,170 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2018-10-15 15:06:38,170 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:38,171 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:06:38,174 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:38,174 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:38,174 INFO L82 PathProgramCache]: Analyzing trace with hash 1135529102, now seen corresponding path program 7 times [2018-10-15 15:06:38,175 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:38,190 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:38,494 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:06:38,494 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:38,495 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-15 15:06:38,495 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-15 15:06:38,495 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-15 15:06:38,496 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=241, Unknown=0, NotChecked=0, Total=272 [2018-10-15 15:06:38,496 INFO L87 Difference]: Start difference. First operand 56 states and 57 transitions. Second operand 17 states. [2018-10-15 15:06:39,483 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:39,484 INFO L93 Difference]: Finished difference Result 64 states and 65 transitions. [2018-10-15 15:06:39,484 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-15 15:06:39,484 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 55 [2018-10-15 15:06:39,485 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:39,487 INFO L225 Difference]: With dead ends: 64 [2018-10-15 15:06:39,487 INFO L226 Difference]: Without dead ends: 64 [2018-10-15 15:06:39,487 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 31 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=87, Invalid=843, Unknown=0, NotChecked=0, Total=930 [2018-10-15 15:06:39,488 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2018-10-15 15:06:39,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 61. [2018-10-15 15:06:39,492 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 61 states. [2018-10-15 15:06:39,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 62 transitions. [2018-10-15 15:06:39,493 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 62 transitions. Word has length 55 [2018-10-15 15:06:39,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:39,494 INFO L481 AbstractCegarLoop]: Abstraction has 61 states and 62 transitions. [2018-10-15 15:06:39,494 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-15 15:06:39,494 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 62 transitions. [2018-10-15 15:06:39,495 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-10-15 15:06:39,495 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:39,495 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:06:39,496 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:39,496 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:39,496 INFO L82 PathProgramCache]: Analyzing trace with hash 94450304, now seen corresponding path program 8 times [2018-10-15 15:06:39,497 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:39,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:39,953 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:06:39,953 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:39,953 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-10-15 15:06:39,954 INFO L460 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-15 15:06:39,954 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-15 15:06:39,954 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=307, Unknown=0, NotChecked=0, Total=342 [2018-10-15 15:06:39,954 INFO L87 Difference]: Start difference. First operand 61 states and 62 transitions. Second operand 19 states. [2018-10-15 15:06:40,839 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:40,840 INFO L93 Difference]: Finished difference Result 69 states and 70 transitions. [2018-10-15 15:06:40,840 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-10-15 15:06:40,840 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 60 [2018-10-15 15:06:40,841 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:40,842 INFO L225 Difference]: With dead ends: 69 [2018-10-15 15:06:40,842 INFO L226 Difference]: Without dead ends: 69 [2018-10-15 15:06:40,843 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 2 SyntacticMatches, 0 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:06:40,843 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2018-10-15 15:06:40,845 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 66. [2018-10-15 15:06:40,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 66 states. [2018-10-15 15:06:40,848 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 67 transitions. [2018-10-15 15:06:40,848 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 67 transitions. Word has length 60 [2018-10-15 15:06:40,849 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:40,850 INFO L481 AbstractCegarLoop]: Abstraction has 66 states and 67 transitions. [2018-10-15 15:06:40,850 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-15 15:06:40,850 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 67 transitions. [2018-10-15 15:06:40,851 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2018-10-15 15:06:40,851 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:40,851 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:06:40,851 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:40,851 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:40,851 INFO L82 PathProgramCache]: Analyzing trace with hash -1587891250, now seen corresponding path program 9 times [2018-10-15 15:06:40,853 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:40,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:41,319 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:06:41,319 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:41,319 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-15 15:06:41,320 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-15 15:06:41,320 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-15 15:06:41,320 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=381, Unknown=0, NotChecked=0, Total=420 [2018-10-15 15:06:41,320 INFO L87 Difference]: Start difference. First operand 66 states and 67 transitions. Second operand 21 states. [2018-10-15 15:06:42,570 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:42,573 INFO L93 Difference]: Finished difference Result 74 states and 75 transitions. [2018-10-15 15:06:42,575 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-15 15:06:42,575 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 65 [2018-10-15 15:06:42,575 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:42,576 INFO L225 Difference]: With dead ends: 74 [2018-10-15 15:06:42,576 INFO L226 Difference]: Without dead ends: 74 [2018-10-15 15:06:42,577 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 153 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=111, Invalid=1371, Unknown=0, NotChecked=0, Total=1482 [2018-10-15 15:06:42,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2018-10-15 15:06:42,589 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2018-10-15 15:06:42,589 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 71 states. [2018-10-15 15:06:42,590 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 72 transitions. [2018-10-15 15:06:42,590 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 72 transitions. Word has length 65 [2018-10-15 15:06:42,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:42,591 INFO L481 AbstractCegarLoop]: Abstraction has 71 states and 72 transitions. [2018-10-15 15:06:42,594 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-15 15:06:42,594 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 72 transitions. [2018-10-15 15:06:42,595 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2018-10-15 15:06:42,595 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:42,595 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:06:42,596 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:42,596 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:42,596 INFO L82 PathProgramCache]: Analyzing trace with hash 394515264, now seen corresponding path program 10 times [2018-10-15 15:06:42,597 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:42,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:42,756 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:06:42,757 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:42,757 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [5] total 5 [2018-10-15 15:06:42,757 INFO L460 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-10-15 15:06:42,757 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-10-15 15:06:42,757 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-10-15 15:06:42,758 INFO L87 Difference]: Start difference. First operand 71 states and 72 transitions. Second operand 5 states. [2018-10-15 15:06:42,819 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:42,819 INFO L93 Difference]: Finished difference Result 184 states and 187 transitions. [2018-10-15 15:06:42,819 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-10-15 15:06:42,820 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 70 [2018-10-15 15:06:42,820 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:42,822 INFO L225 Difference]: With dead ends: 184 [2018-10-15 15:06:42,822 INFO L226 Difference]: Without dead ends: 184 [2018-10-15 15:06:42,823 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2018-10-15 15:06:42,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 184 states. [2018-10-15 15:06:42,829 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 184 to 129. [2018-10-15 15:06:42,829 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 129 states. [2018-10-15 15:06:42,830 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 131 transitions. [2018-10-15 15:06:42,830 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 131 transitions. Word has length 70 [2018-10-15 15:06:42,830 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:42,831 INFO L481 AbstractCegarLoop]: Abstraction has 129 states and 131 transitions. [2018-10-15 15:06:42,831 INFO L482 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-10-15 15:06:42,831 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 131 transitions. [2018-10-15 15:06:42,832 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 129 [2018-10-15 15:06:42,833 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:42,833 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:06:42,833 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:42,833 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:42,833 INFO L82 PathProgramCache]: Analyzing trace with hash 1739062802, now seen corresponding path program 11 times [2018-10-15 15:06:42,834 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:42,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:43,456 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:06:43,456 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:43,457 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2018-10-15 15:06:43,457 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-10-15 15:06:43,457 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-10-15 15:06:43,457 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-10-15 15:06:43,458 INFO L87 Difference]: Start difference. First operand 129 states and 131 transitions. Second operand 7 states. [2018-10-15 15:06:43,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:43,568 INFO L93 Difference]: Finished difference Result 242 states and 246 transitions. [2018-10-15 15:06:43,569 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-15 15:06:43,569 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 128 [2018-10-15 15:06:43,570 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:43,571 INFO L225 Difference]: With dead ends: 242 [2018-10-15 15:06:43,571 INFO L226 Difference]: Without dead ends: 242 [2018-10-15 15:06:43,571 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2018-10-15 15:06:43,572 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 242 states. [2018-10-15 15:06:43,586 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 242 to 187. [2018-10-15 15:06:43,586 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 187 states. [2018-10-15 15:06:43,593 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 187 states to 187 states and 190 transitions. [2018-10-15 15:06:43,593 INFO L78 Accepts]: Start accepts. Automaton has 187 states and 190 transitions. Word has length 128 [2018-10-15 15:06:43,593 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:43,593 INFO L481 AbstractCegarLoop]: Abstraction has 187 states and 190 transitions. [2018-10-15 15:06:43,594 INFO L482 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-10-15 15:06:43,594 INFO L276 IsEmpty]: Start isEmpty. Operand 187 states and 190 transitions. [2018-10-15 15:06:43,596 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 187 [2018-10-15 15:06:43,597 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:43,597 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:06:43,597 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:43,597 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:43,597 INFO L82 PathProgramCache]: Analyzing trace with hash 193306212, now seen corresponding path program 12 times [2018-10-15 15:06:43,598 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:43,615 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:43,981 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:06:43,982 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:43,982 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-15 15:06:43,982 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-15 15:06:43,983 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-15 15:06:43,983 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=57, Unknown=0, NotChecked=0, Total=72 [2018-10-15 15:06:43,983 INFO L87 Difference]: Start difference. First operand 187 states and 190 transitions. Second operand 9 states. [2018-10-15 15:06:44,371 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:44,371 INFO L93 Difference]: Finished difference Result 300 states and 305 transitions. [2018-10-15 15:06:44,372 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-10-15 15:06:44,372 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 186 [2018-10-15 15:06:44,372 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:44,375 INFO L225 Difference]: With dead ends: 300 [2018-10-15 15:06:44,375 INFO L226 Difference]: Without dead ends: 300 [2018-10-15 15:06:44,375 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:06:44,376 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 300 states. [2018-10-15 15:06:44,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 300 to 245. [2018-10-15 15:06:44,381 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 245 states. [2018-10-15 15:06:44,382 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 245 states to 245 states and 249 transitions. [2018-10-15 15:06:44,382 INFO L78 Accepts]: Start accepts. Automaton has 245 states and 249 transitions. Word has length 186 [2018-10-15 15:06:44,382 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:44,383 INFO L481 AbstractCegarLoop]: Abstraction has 245 states and 249 transitions. [2018-10-15 15:06:44,383 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-15 15:06:44,383 INFO L276 IsEmpty]: Start isEmpty. Operand 245 states and 249 transitions. [2018-10-15 15:06:44,386 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 245 [2018-10-15 15:06:44,386 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:44,386 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:06:44,387 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:44,387 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:44,387 INFO L82 PathProgramCache]: Analyzing trace with hash -1420372938, now seen corresponding path program 13 times [2018-10-15 15:06:44,388 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:44,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:44,844 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:06:44,845 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:44,845 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2018-10-15 15:06:44,845 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2018-10-15 15:06:44,845 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2018-10-15 15:06:44,845 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=91, Unknown=0, NotChecked=0, Total=110 [2018-10-15 15:06:44,846 INFO L87 Difference]: Start difference. First operand 245 states and 249 transitions. Second operand 11 states. [2018-10-15 15:06:45,184 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:45,185 INFO L93 Difference]: Finished difference Result 358 states and 364 transitions. [2018-10-15 15:06:45,186 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-10-15 15:06:45,186 INFO L78 Accepts]: Start accepts. Automaton has 11 states. Word has length 244 [2018-10-15 15:06:45,187 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:45,188 INFO L225 Difference]: With dead ends: 358 [2018-10-15 15:06:45,188 INFO L226 Difference]: Without dead ends: 358 [2018-10-15 15:06:45,189 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 2 SyntacticMatches, 1 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:06:45,189 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 358 states. [2018-10-15 15:06:45,194 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 358 to 303. [2018-10-15 15:06:45,194 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 303 states. [2018-10-15 15:06:45,195 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 303 states to 303 states and 308 transitions. [2018-10-15 15:06:45,195 INFO L78 Accepts]: Start accepts. Automaton has 303 states and 308 transitions. Word has length 244 [2018-10-15 15:06:45,195 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:45,195 INFO L481 AbstractCegarLoop]: Abstraction has 303 states and 308 transitions. [2018-10-15 15:06:45,196 INFO L482 AbstractCegarLoop]: Interpolant automaton has 11 states. [2018-10-15 15:06:45,196 INFO L276 IsEmpty]: Start isEmpty. Operand 303 states and 308 transitions. [2018-10-15 15:06:45,199 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 303 [2018-10-15 15:06:45,199 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:45,199 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:06:45,200 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:45,200 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:45,200 INFO L82 PathProgramCache]: Analyzing trace with hash 208519048, now seen corresponding path program 14 times [2018-10-15 15:06:45,201 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:45,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:45,744 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:06:45,744 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:45,744 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-15 15:06:45,745 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-15 15:06:45,745 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-15 15:06:45,745 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-10-15 15:06:45,746 INFO L87 Difference]: Start difference. First operand 303 states and 308 transitions. Second operand 13 states. [2018-10-15 15:06:46,110 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:46,111 INFO L93 Difference]: Finished difference Result 416 states and 423 transitions. [2018-10-15 15:06:46,112 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-10-15 15:06:46,112 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 302 [2018-10-15 15:06:46,113 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:46,115 INFO L225 Difference]: With dead ends: 416 [2018-10-15 15:06:46,115 INFO L226 Difference]: Without dead ends: 416 [2018-10-15 15:06:46,116 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 2 SyntacticMatches, 1 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:06:46,116 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 416 states. [2018-10-15 15:06:46,121 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 416 to 361. [2018-10-15 15:06:46,121 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 361 states. [2018-10-15 15:06:46,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 361 states to 361 states and 367 transitions. [2018-10-15 15:06:46,122 INFO L78 Accepts]: Start accepts. Automaton has 361 states and 367 transitions. Word has length 302 [2018-10-15 15:06:46,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:46,123 INFO L481 AbstractCegarLoop]: Abstraction has 361 states and 367 transitions. [2018-10-15 15:06:46,123 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-15 15:06:46,123 INFO L276 IsEmpty]: Start isEmpty. Operand 361 states and 367 transitions. [2018-10-15 15:06:46,128 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 361 [2018-10-15 15:06:46,128 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:46,128 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:06:46,129 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:46,129 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:46,129 INFO L82 PathProgramCache]: Analyzing trace with hash 53772378, now seen corresponding path program 15 times [2018-10-15 15:06:46,130 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:46,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:47,312 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:06:47,312 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:47,312 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [15] total 15 [2018-10-15 15:06:47,313 INFO L460 AbstractCegarLoop]: Interpolant automaton has 15 states [2018-10-15 15:06:47,313 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2018-10-15 15:06:47,313 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-10-15 15:06:47,313 INFO L87 Difference]: Start difference. First operand 361 states and 367 transitions. Second operand 15 states. [2018-10-15 15:06:47,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:47,833 INFO L93 Difference]: Finished difference Result 474 states and 482 transitions. [2018-10-15 15:06:47,834 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2018-10-15 15:06:47,834 INFO L78 Accepts]: Start accepts. Automaton has 15 states. Word has length 360 [2018-10-15 15:06:47,835 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:47,838 INFO L225 Difference]: With dead ends: 474 [2018-10-15 15:06:47,838 INFO L226 Difference]: Without dead ends: 474 [2018-10-15 15:06:47,839 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:06:47,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 474 states. [2018-10-15 15:06:47,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 474 to 419. [2018-10-15 15:06:47,846 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 419 states. [2018-10-15 15:06:47,847 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 419 states to 419 states and 426 transitions. [2018-10-15 15:06:47,848 INFO L78 Accepts]: Start accepts. Automaton has 419 states and 426 transitions. Word has length 360 [2018-10-15 15:06:47,848 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:47,848 INFO L481 AbstractCegarLoop]: Abstraction has 419 states and 426 transitions. [2018-10-15 15:06:47,849 INFO L482 AbstractCegarLoop]: Interpolant automaton has 15 states. [2018-10-15 15:06:47,849 INFO L276 IsEmpty]: Start isEmpty. Operand 419 states and 426 transitions. [2018-10-15 15:06:47,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 419 [2018-10-15 15:06:47,852 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:47,852 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:06:47,853 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:47,853 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:47,853 INFO L82 PathProgramCache]: Analyzing trace with hash -450021716, now seen corresponding path program 16 times [2018-10-15 15:06:47,854 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:47,885 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:49,413 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:06:49,414 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:49,414 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-15 15:06:49,414 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-15 15:06:49,414 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-15 15:06:49,415 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=241, Unknown=0, NotChecked=0, Total=272 [2018-10-15 15:06:49,415 INFO L87 Difference]: Start difference. First operand 419 states and 426 transitions. Second operand 17 states. [2018-10-15 15:06:49,971 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:49,972 INFO L93 Difference]: Finished difference Result 532 states and 541 transitions. [2018-10-15 15:06:49,973 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-15 15:06:49,973 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 418 [2018-10-15 15:06:49,974 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:49,976 INFO L225 Difference]: With dead ends: 532 [2018-10-15 15:06:49,976 INFO L226 Difference]: Without dead ends: 532 [2018-10-15 15:06:49,976 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 91 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=87, Invalid=843, Unknown=0, NotChecked=0, Total=930 [2018-10-15 15:06:49,977 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 532 states. [2018-10-15 15:06:49,983 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 532 to 477. [2018-10-15 15:06:49,983 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 477 states. [2018-10-15 15:06:49,984 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 477 states to 477 states and 485 transitions. [2018-10-15 15:06:49,985 INFO L78 Accepts]: Start accepts. Automaton has 477 states and 485 transitions. Word has length 418 [2018-10-15 15:06:49,985 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:49,985 INFO L481 AbstractCegarLoop]: Abstraction has 477 states and 485 transitions. [2018-10-15 15:06:49,985 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-15 15:06:49,986 INFO L276 IsEmpty]: Start isEmpty. Operand 477 states and 485 transitions. [2018-10-15 15:06:49,988 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 477 [2018-10-15 15:06:49,988 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:49,989 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:06:49,989 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:49,989 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:49,989 INFO L82 PathProgramCache]: Analyzing trace with hash 2062680702, now seen corresponding path program 17 times [2018-10-15 15:06:49,990 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:50,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:51,555 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:06:51,556 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:51,556 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19] total 19 [2018-10-15 15:06:51,557 INFO L460 AbstractCegarLoop]: Interpolant automaton has 19 states [2018-10-15 15:06:51,557 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2018-10-15 15:06:51,557 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=307, Unknown=0, NotChecked=0, Total=342 [2018-10-15 15:06:51,557 INFO L87 Difference]: Start difference. First operand 477 states and 485 transitions. Second operand 19 states. [2018-10-15 15:06:52,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:52,292 INFO L93 Difference]: Finished difference Result 590 states and 600 transitions. [2018-10-15 15:06:52,292 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-10-15 15:06:52,292 INFO L78 Accepts]: Start accepts. Automaton has 19 states. Word has length 476 [2018-10-15 15:06:52,294 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:52,297 INFO L225 Difference]: With dead ends: 590 [2018-10-15 15:06:52,297 INFO L226 Difference]: Without dead ends: 590 [2018-10-15 15:06:52,297 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=99, Invalid=1091, Unknown=0, NotChecked=0, Total=1190 [2018-10-15 15:06:52,298 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 590 states. [2018-10-15 15:06:52,304 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 590 to 535. [2018-10-15 15:06:52,304 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 535 states. [2018-10-15 15:06:52,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 535 states to 535 states and 544 transitions. [2018-10-15 15:06:52,306 INFO L78 Accepts]: Start accepts. Automaton has 535 states and 544 transitions. Word has length 476 [2018-10-15 15:06:52,307 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:52,307 INFO L481 AbstractCegarLoop]: Abstraction has 535 states and 544 transitions. [2018-10-15 15:06:52,307 INFO L482 AbstractCegarLoop]: Interpolant automaton has 19 states. [2018-10-15 15:06:52,307 INFO L276 IsEmpty]: Start isEmpty. Operand 535 states and 544 transitions. [2018-10-15 15:06:52,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 535 [2018-10-15 15:06:52,310 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:52,310 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:06:52,311 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:52,311 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:52,311 INFO L82 PathProgramCache]: Analyzing trace with hash 1916077008, now seen corresponding path program 18 times [2018-10-15 15:06:52,312 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:52,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:54,275 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:06:54,276 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:54,276 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-15 15:06:54,277 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-15 15:06:54,277 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-15 15:06:54,277 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=381, Unknown=0, NotChecked=0, Total=420 [2018-10-15 15:06:54,278 INFO L87 Difference]: Start difference. First operand 535 states and 544 transitions. Second operand 21 states. [2018-10-15 15:06:55,188 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:55,189 INFO L93 Difference]: Finished difference Result 648 states and 659 transitions. [2018-10-15 15:06:55,193 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-15 15:06:55,193 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 534 [2018-10-15 15:06:55,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:55,197 INFO L225 Difference]: With dead ends: 648 [2018-10-15 15:06:55,197 INFO L226 Difference]: Without dead ends: 648 [2018-10-15 15:06:55,198 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 153 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=111, Invalid=1371, Unknown=0, NotChecked=0, Total=1482 [2018-10-15 15:06:55,198 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 648 states. [2018-10-15 15:06:55,205 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 648 to 593. [2018-10-15 15:06:55,205 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 593 states. [2018-10-15 15:06:55,206 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 593 states to 593 states and 603 transitions. [2018-10-15 15:06:55,207 INFO L78 Accepts]: Start accepts. Automaton has 593 states and 603 transitions. Word has length 534 [2018-10-15 15:06:55,207 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:55,208 INFO L481 AbstractCegarLoop]: Abstraction has 593 states and 603 transitions. [2018-10-15 15:06:55,208 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-15 15:06:55,208 INFO L276 IsEmpty]: Start isEmpty. Operand 593 states and 603 transitions. [2018-10-15 15:06:55,211 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 593 [2018-10-15 15:06:55,212 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:55,212 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:06:55,212 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:55,213 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:55,213 INFO L82 PathProgramCache]: Analyzing trace with hash 1338006178, now seen corresponding path program 19 times [2018-10-15 15:06:55,214 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:55,249 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:56,935 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:06:56,935 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:56,936 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2018-10-15 15:06:56,936 INFO L460 AbstractCegarLoop]: Interpolant automaton has 23 states [2018-10-15 15:06:56,936 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2018-10-15 15:06:56,937 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=463, Unknown=0, NotChecked=0, Total=506 [2018-10-15 15:06:56,937 INFO L87 Difference]: Start difference. First operand 593 states and 603 transitions. Second operand 23 states. [2018-10-15 15:06:58,131 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:06:58,131 INFO L93 Difference]: Finished difference Result 706 states and 718 transitions. [2018-10-15 15:06:58,132 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-10-15 15:06:58,132 INFO L78 Accepts]: Start accepts. Automaton has 23 states. Word has length 592 [2018-10-15 15:06:58,134 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:06:58,138 INFO L225 Difference]: With dead ends: 706 [2018-10-15 15:06:58,138 INFO L226 Difference]: Without dead ends: 706 [2018-10-15 15:06:58,139 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:06:58,140 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 706 states. [2018-10-15 15:06:58,149 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 706 to 651. [2018-10-15 15:06:58,149 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 651 states. [2018-10-15 15:06:58,150 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 651 states to 651 states and 662 transitions. [2018-10-15 15:06:58,151 INFO L78 Accepts]: Start accepts. Automaton has 651 states and 662 transitions. Word has length 592 [2018-10-15 15:06:58,152 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:06:58,152 INFO L481 AbstractCegarLoop]: Abstraction has 651 states and 662 transitions. [2018-10-15 15:06:58,152 INFO L482 AbstractCegarLoop]: Interpolant automaton has 23 states. [2018-10-15 15:06:58,152 INFO L276 IsEmpty]: Start isEmpty. Operand 651 states and 662 transitions. [2018-10-15 15:06:58,158 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 651 [2018-10-15 15:06:58,159 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:06:58,159 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:06:58,159 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:06:58,160 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:06:58,160 INFO L82 PathProgramCache]: Analyzing trace with hash -512350476, now seen corresponding path program 20 times [2018-10-15 15:06:58,161 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:06:58,201 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:06:59,428 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:06:59,428 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:06:59,429 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-15 15:06:59,429 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-15 15:06:59,430 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-15 15:06:59,430 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=47, Invalid=553, Unknown=0, NotChecked=0, Total=600 [2018-10-15 15:06:59,430 INFO L87 Difference]: Start difference. First operand 651 states and 662 transitions. Second operand 25 states. [2018-10-15 15:07:00,784 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:00,785 INFO L93 Difference]: Finished difference Result 764 states and 777 transitions. [2018-10-15 15:07:00,793 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-10-15 15:07:00,793 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 650 [2018-10-15 15:07:00,794 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:00,796 INFO L225 Difference]: With dead ends: 764 [2018-10-15 15:07:00,796 INFO L226 Difference]: Without dead ends: 764 [2018-10-15 15:07:00,797 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 48 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 231 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=135, Invalid=2027, Unknown=0, NotChecked=0, Total=2162 [2018-10-15 15:07:00,798 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 764 states. [2018-10-15 15:07:00,805 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 764 to 709. [2018-10-15 15:07:00,806 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-10-15 15:07:00,807 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 721 transitions. [2018-10-15 15:07:00,807 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 721 transitions. Word has length 650 [2018-10-15 15:07:00,808 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:00,808 INFO L481 AbstractCegarLoop]: Abstraction has 709 states and 721 transitions. [2018-10-15 15:07:00,808 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-15 15:07:00,808 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 721 transitions. [2018-10-15 15:07:00,813 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 709 [2018-10-15 15:07:00,813 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:00,813 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:07:00,814 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:00,814 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:00,814 INFO L82 PathProgramCache]: Analyzing trace with hash 810584262, now seen corresponding path program 21 times [2018-10-15 15:07:00,815 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:00,851 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:02,309 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:07:02,309 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:02,309 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2018-10-15 15:07:02,310 INFO L460 AbstractCegarLoop]: Interpolant automaton has 27 states [2018-10-15 15:07:02,310 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2018-10-15 15:07:02,311 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=651, Unknown=0, NotChecked=0, Total=702 [2018-10-15 15:07:02,311 INFO L87 Difference]: Start difference. First operand 709 states and 721 transitions. Second operand 27 states. [2018-10-15 15:07:03,649 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:03,649 INFO L93 Difference]: Finished difference Result 822 states and 836 transitions. [2018-10-15 15:07:03,650 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-10-15 15:07:03,650 INFO L78 Accepts]: Start accepts. Automaton has 27 states. Word has length 708 [2018-10-15 15:07:03,651 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:03,654 INFO L225 Difference]: With dead ends: 822 [2018-10-15 15:07:03,654 INFO L226 Difference]: Without dead ends: 822 [2018-10-15 15:07:03,655 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 276 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=147, Invalid=2403, Unknown=0, NotChecked=0, Total=2550 [2018-10-15 15:07:03,656 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 822 states. [2018-10-15 15:07:03,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 822 to 767. [2018-10-15 15:07:03,665 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 767 states. [2018-10-15 15:07:03,666 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 767 states to 767 states and 780 transitions. [2018-10-15 15:07:03,666 INFO L78 Accepts]: Start accepts. Automaton has 767 states and 780 transitions. Word has length 708 [2018-10-15 15:07:03,667 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:03,667 INFO L481 AbstractCegarLoop]: Abstraction has 767 states and 780 transitions. [2018-10-15 15:07:03,667 INFO L482 AbstractCegarLoop]: Interpolant automaton has 27 states. [2018-10-15 15:07:03,667 INFO L276 IsEmpty]: Start isEmpty. Operand 767 states and 780 transitions. [2018-10-15 15:07:03,672 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 767 [2018-10-15 15:07:03,673 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:03,673 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:07:03,673 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:03,673 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:03,674 INFO L82 PathProgramCache]: Analyzing trace with hash -228483048, now seen corresponding path program 22 times [2018-10-15 15:07:03,674 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:03,714 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:07,157 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:07:07,157 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:07,158 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-15 15:07:07,158 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-15 15:07:07,158 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-15 15:07:07,159 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=55, Invalid=757, Unknown=0, NotChecked=0, Total=812 [2018-10-15 15:07:07,159 INFO L87 Difference]: Start difference. First operand 767 states and 780 transitions. Second operand 29 states. [2018-10-15 15:07:08,615 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:08,616 INFO L93 Difference]: Finished difference Result 880 states and 895 transitions. [2018-10-15 15:07:08,616 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2018-10-15 15:07:08,616 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 766 [2018-10-15 15:07:08,617 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:08,622 INFO L225 Difference]: With dead ends: 880 [2018-10-15 15:07:08,622 INFO L226 Difference]: Without dead ends: 880 [2018-10-15 15:07:08,624 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 325 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=159, Invalid=2811, Unknown=0, NotChecked=0, Total=2970 [2018-10-15 15:07:08,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 880 states. [2018-10-15 15:07:08,633 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 880 to 825. [2018-10-15 15:07:08,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 825 states. [2018-10-15 15:07:08,635 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 825 states to 825 states and 839 transitions. [2018-10-15 15:07:08,635 INFO L78 Accepts]: Start accepts. Automaton has 825 states and 839 transitions. Word has length 766 [2018-10-15 15:07:08,636 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:08,636 INFO L481 AbstractCegarLoop]: Abstraction has 825 states and 839 transitions. [2018-10-15 15:07:08,636 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-15 15:07:08,636 INFO L276 IsEmpty]: Start isEmpty. Operand 825 states and 839 transitions. [2018-10-15 15:07:08,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 825 [2018-10-15 15:07:08,643 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:08,643 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:07:08,643 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:08,644 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:08,644 INFO L82 PathProgramCache]: Analyzing trace with hash 2094238954, now seen corresponding path program 23 times [2018-10-15 15:07:08,645 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:08,691 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:10,663 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:07:10,664 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:10,664 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [31] total 31 [2018-10-15 15:07:10,664 INFO L460 AbstractCegarLoop]: Interpolant automaton has 31 states [2018-10-15 15:07:10,664 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2018-10-15 15:07:10,665 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=59, Invalid=871, Unknown=0, NotChecked=0, Total=930 [2018-10-15 15:07:10,665 INFO L87 Difference]: Start difference. First operand 825 states and 839 transitions. Second operand 31 states. [2018-10-15 15:07:12,509 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:12,509 INFO L93 Difference]: Finished difference Result 938 states and 954 transitions. [2018-10-15 15:07:12,510 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2018-10-15 15:07:12,510 INFO L78 Accepts]: Start accepts. Automaton has 31 states. Word has length 824 [2018-10-15 15:07:12,511 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:12,515 INFO L225 Difference]: With dead ends: 938 [2018-10-15 15:07:12,515 INFO L226 Difference]: Without dead ends: 938 [2018-10-15 15:07:12,517 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 378 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=171, Invalid=3251, Unknown=0, NotChecked=0, Total=3422 [2018-10-15 15:07:12,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 938 states. [2018-10-15 15:07:12,526 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 938 to 883. [2018-10-15 15:07:12,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 883 states. [2018-10-15 15:07:12,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 883 states to 883 states and 898 transitions. [2018-10-15 15:07:12,528 INFO L78 Accepts]: Start accepts. Automaton has 883 states and 898 transitions. Word has length 824 [2018-10-15 15:07:12,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:12,529 INFO L481 AbstractCegarLoop]: Abstraction has 883 states and 898 transitions. [2018-10-15 15:07:12,529 INFO L482 AbstractCegarLoop]: Interpolant automaton has 31 states. [2018-10-15 15:07:12,529 INFO L276 IsEmpty]: Start isEmpty. Operand 883 states and 898 transitions. [2018-10-15 15:07:12,536 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 883 [2018-10-15 15:07:12,537 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:12,537 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:07:12,537 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:12,537 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:12,538 INFO L82 PathProgramCache]: Analyzing trace with hash 904425276, now seen corresponding path program 24 times [2018-10-15 15:07:12,539 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:12,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:15,805 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:07:15,805 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:15,805 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-15 15:07:15,806 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-15 15:07:15,806 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-15 15:07:15,807 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=63, Invalid=993, Unknown=0, NotChecked=0, Total=1056 [2018-10-15 15:07:15,807 INFO L87 Difference]: Start difference. First operand 883 states and 898 transitions. Second operand 33 states. [2018-10-15 15:07:16,640 WARN L179 SmtUtils]: Spent 113.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-10-15 15:07:18,081 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:18,082 INFO L93 Difference]: Finished difference Result 996 states and 1013 transitions. [2018-10-15 15:07:18,082 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 48 states. [2018-10-15 15:07:18,082 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 882 [2018-10-15 15:07:18,083 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:18,087 INFO L225 Difference]: With dead ends: 996 [2018-10-15 15:07:18,087 INFO L226 Difference]: Without dead ends: 996 [2018-10-15 15:07:18,088 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 64 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 61 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 435 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=183, Invalid=3723, Unknown=0, NotChecked=0, Total=3906 [2018-10-15 15:07:18,089 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 996 states. [2018-10-15 15:07:18,098 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 996 to 941. [2018-10-15 15:07:18,098 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 941 states. [2018-10-15 15:07:18,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 941 states to 941 states and 957 transitions. [2018-10-15 15:07:18,100 INFO L78 Accepts]: Start accepts. Automaton has 941 states and 957 transitions. Word has length 882 [2018-10-15 15:07:18,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:18,101 INFO L481 AbstractCegarLoop]: Abstraction has 941 states and 957 transitions. [2018-10-15 15:07:18,101 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-15 15:07:18,101 INFO L276 IsEmpty]: Start isEmpty. Operand 941 states and 957 transitions. [2018-10-15 15:07:18,109 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 941 [2018-10-15 15:07:18,109 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:18,109 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:07:18,110 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:18,110 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:18,110 INFO L82 PathProgramCache]: Analyzing trace with hash -2030409970, now seen corresponding path program 25 times [2018-10-15 15:07:18,111 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:18,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:21,465 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:07:21,466 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:21,466 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [35] total 35 [2018-10-15 15:07:21,466 INFO L460 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-10-15 15:07:21,467 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-10-15 15:07:21,467 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=1123, Unknown=0, NotChecked=0, Total=1190 [2018-10-15 15:07:21,467 INFO L87 Difference]: Start difference. First operand 941 states and 957 transitions. Second operand 35 states. [2018-10-15 15:07:22,115 WARN L179 SmtUtils]: Spent 149.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-10-15 15:07:24,006 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:24,007 INFO L93 Difference]: Finished difference Result 1054 states and 1072 transitions. [2018-10-15 15:07:24,007 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-10-15 15:07:24,007 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 940 [2018-10-15 15:07:24,008 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:24,013 INFO L225 Difference]: With dead ends: 1054 [2018-10-15 15:07:24,013 INFO L226 Difference]: Without dead ends: 1054 [2018-10-15 15:07:24,014 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 65 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 496 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=195, Invalid=4227, Unknown=0, NotChecked=0, Total=4422 [2018-10-15 15:07:24,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1054 states. [2018-10-15 15:07:24,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1054 to 999. [2018-10-15 15:07:24,025 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 999 states. [2018-10-15 15:07:24,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 999 states to 999 states and 1016 transitions. [2018-10-15 15:07:24,027 INFO L78 Accepts]: Start accepts. Automaton has 999 states and 1016 transitions. Word has length 940 [2018-10-15 15:07:24,027 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:24,027 INFO L481 AbstractCegarLoop]: Abstraction has 999 states and 1016 transitions. [2018-10-15 15:07:24,028 INFO L482 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-10-15 15:07:24,028 INFO L276 IsEmpty]: Start isEmpty. Operand 999 states and 1016 transitions. [2018-10-15 15:07:24,036 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 999 [2018-10-15 15:07:24,036 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:24,037 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:07:24,037 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:24,038 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:24,038 INFO L82 PathProgramCache]: Analyzing trace with hash 1316721760, now seen corresponding path program 26 times [2018-10-15 15:07:24,039 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:24,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:26,697 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:07:26,697 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:26,698 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-15 15:07:26,698 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-15 15:07:26,699 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-15 15:07:26,699 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=1261, Unknown=0, NotChecked=0, Total=1332 [2018-10-15 15:07:26,699 INFO L87 Difference]: Start difference. First operand 999 states and 1016 transitions. Second operand 37 states. [2018-10-15 15:07:29,189 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:29,189 INFO L93 Difference]: Finished difference Result 1112 states and 1131 transitions. [2018-10-15 15:07:29,189 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2018-10-15 15:07:29,189 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 998 [2018-10-15 15:07:29,190 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:29,193 INFO L225 Difference]: With dead ends: 1112 [2018-10-15 15:07:29,193 INFO L226 Difference]: Without dead ends: 1112 [2018-10-15 15:07:29,194 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 72 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 561 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=207, Invalid=4763, Unknown=0, NotChecked=0, Total=4970 [2018-10-15 15:07:29,195 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1112 states. [2018-10-15 15:07:29,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1112 to 1057. [2018-10-15 15:07:29,206 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1057 states. [2018-10-15 15:07:29,208 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1057 states to 1057 states and 1075 transitions. [2018-10-15 15:07:29,208 INFO L78 Accepts]: Start accepts. Automaton has 1057 states and 1075 transitions. Word has length 998 [2018-10-15 15:07:29,209 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:29,209 INFO L481 AbstractCegarLoop]: Abstraction has 1057 states and 1075 transitions. [2018-10-15 15:07:29,209 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-15 15:07:29,209 INFO L276 IsEmpty]: Start isEmpty. Operand 1057 states and 1075 transitions. [2018-10-15 15:07:29,218 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1057 [2018-10-15 15:07:29,218 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:29,219 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:07:29,219 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:29,220 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:29,220 INFO L82 PathProgramCache]: Analyzing trace with hash -772401358, now seen corresponding path program 27 times [2018-10-15 15:07:29,221 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:29,269 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:32,166 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:07:32,166 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:32,166 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [39] total 39 [2018-10-15 15:07:32,167 INFO L460 AbstractCegarLoop]: Interpolant automaton has 39 states [2018-10-15 15:07:32,167 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 39 interpolants. [2018-10-15 15:07:32,167 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=1407, Unknown=0, NotChecked=0, Total=1482 [2018-10-15 15:07:32,167 INFO L87 Difference]: Start difference. First operand 1057 states and 1075 transitions. Second operand 39 states. [2018-10-15 15:07:35,136 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:35,136 INFO L93 Difference]: Finished difference Result 1170 states and 1190 transitions. [2018-10-15 15:07:35,136 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-10-15 15:07:35,136 INFO L78 Accepts]: Start accepts. Automaton has 39 states. Word has length 1056 [2018-10-15 15:07:35,137 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:35,140 INFO L225 Difference]: With dead ends: 1170 [2018-10-15 15:07:35,140 INFO L226 Difference]: Without dead ends: 1170 [2018-10-15 15:07:35,142 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 630 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=219, Invalid=5331, Unknown=0, NotChecked=0, Total=5550 [2018-10-15 15:07:35,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1170 states. [2018-10-15 15:07:35,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1170 to 1115. [2018-10-15 15:07:35,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1115 states. [2018-10-15 15:07:35,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1115 states to 1115 states and 1134 transitions. [2018-10-15 15:07:35,153 INFO L78 Accepts]: Start accepts. Automaton has 1115 states and 1134 transitions. Word has length 1056 [2018-10-15 15:07:35,154 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:35,154 INFO L481 AbstractCegarLoop]: Abstraction has 1115 states and 1134 transitions. [2018-10-15 15:07:35,154 INFO L482 AbstractCegarLoop]: Interpolant automaton has 39 states. [2018-10-15 15:07:35,154 INFO L276 IsEmpty]: Start isEmpty. Operand 1115 states and 1134 transitions. [2018-10-15 15:07:35,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1115 [2018-10-15 15:07:35,165 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:35,165 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:07:35,165 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:35,166 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:35,166 INFO L82 PathProgramCache]: Analyzing trace with hash 806096772, now seen corresponding path program 28 times [2018-10-15 15:07:35,167 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:35,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:38,021 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:07:38,021 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:38,022 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-15 15:07:38,022 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-15 15:07:38,022 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-15 15:07:38,023 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=1561, Unknown=0, NotChecked=0, Total=1640 [2018-10-15 15:07:38,023 INFO L87 Difference]: Start difference. First operand 1115 states and 1134 transitions. Second operand 41 states. [2018-10-15 15:07:41,155 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:41,155 INFO L93 Difference]: Finished difference Result 1228 states and 1249 transitions. [2018-10-15 15:07:41,155 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-10-15 15:07:41,156 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 1114 [2018-10-15 15:07:41,157 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:41,162 INFO L225 Difference]: With dead ends: 1228 [2018-10-15 15:07:41,162 INFO L226 Difference]: Without dead ends: 1228 [2018-10-15 15:07:41,164 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:07:41,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1228 states. [2018-10-15 15:07:41,174 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1228 to 1173. [2018-10-15 15:07:41,174 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1173 states. [2018-10-15 15:07:41,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1173 states to 1173 states and 1193 transitions. [2018-10-15 15:07:41,176 INFO L78 Accepts]: Start accepts. Automaton has 1173 states and 1193 transitions. Word has length 1114 [2018-10-15 15:07:41,177 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:41,177 INFO L481 AbstractCegarLoop]: Abstraction has 1173 states and 1193 transitions. [2018-10-15 15:07:41,177 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-15 15:07:41,177 INFO L276 IsEmpty]: Start isEmpty. Operand 1173 states and 1193 transitions. [2018-10-15 15:07:41,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1173 [2018-10-15 15:07:41,188 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:41,189 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:07:41,189 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:41,189 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:41,190 INFO L82 PathProgramCache]: Analyzing trace with hash 1383570774, now seen corresponding path program 29 times [2018-10-15 15:07:41,190 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:41,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:44,566 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:07:44,566 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:44,566 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [43] total 43 [2018-10-15 15:07:44,567 INFO L460 AbstractCegarLoop]: Interpolant automaton has 43 states [2018-10-15 15:07:44,567 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2018-10-15 15:07:44,567 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=1723, Unknown=0, NotChecked=0, Total=1806 [2018-10-15 15:07:44,568 INFO L87 Difference]: Start difference. First operand 1173 states and 1193 transitions. Second operand 43 states. [2018-10-15 15:07:48,034 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:48,034 INFO L93 Difference]: Finished difference Result 1286 states and 1308 transitions. [2018-10-15 15:07:48,034 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 63 states. [2018-10-15 15:07:48,035 INFO L78 Accepts]: Start accepts. Automaton has 43 states. Word has length 1172 [2018-10-15 15:07:48,035 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:48,039 INFO L225 Difference]: With dead ends: 1286 [2018-10-15 15:07:48,039 INFO L226 Difference]: Without dead ends: 1286 [2018-10-15 15:07:48,040 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:07:48,040 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1286 states. [2018-10-15 15:07:48,050 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1286 to 1231. [2018-10-15 15:07:48,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1231 states. [2018-10-15 15:07:48,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1231 states to 1231 states and 1252 transitions. [2018-10-15 15:07:48,052 INFO L78 Accepts]: Start accepts. Automaton has 1231 states and 1252 transitions. Word has length 1172 [2018-10-15 15:07:48,053 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:48,053 INFO L481 AbstractCegarLoop]: Abstraction has 1231 states and 1252 transitions. [2018-10-15 15:07:48,053 INFO L482 AbstractCegarLoop]: Interpolant automaton has 43 states. [2018-10-15 15:07:48,053 INFO L276 IsEmpty]: Start isEmpty. Operand 1231 states and 1252 transitions. [2018-10-15 15:07:48,065 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1231 [2018-10-15 15:07:48,066 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:48,066 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:07:48,067 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:48,067 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:48,067 INFO L82 PathProgramCache]: Analyzing trace with hash 1611325608, now seen corresponding path program 30 times [2018-10-15 15:07:48,068 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:48,118 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:07:52,727 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:07:52,727 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:07:52,727 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-15 15:07:52,728 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-15 15:07:52,728 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-15 15:07:52,728 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=1893, Unknown=0, NotChecked=0, Total=1980 [2018-10-15 15:07:52,729 INFO L87 Difference]: Start difference. First operand 1231 states and 1252 transitions. Second operand 45 states. [2018-10-15 15:07:56,440 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:07:56,441 INFO L93 Difference]: Finished difference Result 1344 states and 1367 transitions. [2018-10-15 15:07:56,441 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 66 states. [2018-10-15 15:07:56,441 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 1230 [2018-10-15 15:07:56,443 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:07:56,447 INFO L225 Difference]: With dead ends: 1344 [2018-10-15 15:07:56,447 INFO L226 Difference]: Without dead ends: 1344 [2018-10-15 15:07:56,448 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 861 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=255, Invalid=7227, Unknown=0, NotChecked=0, Total=7482 [2018-10-15 15:07:56,449 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1344 states. [2018-10-15 15:07:56,459 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1344 to 1289. [2018-10-15 15:07:56,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1289 states. [2018-10-15 15:07:56,462 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1289 states to 1289 states and 1311 transitions. [2018-10-15 15:07:56,462 INFO L78 Accepts]: Start accepts. Automaton has 1289 states and 1311 transitions. Word has length 1230 [2018-10-15 15:07:56,463 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:07:56,463 INFO L481 AbstractCegarLoop]: Abstraction has 1289 states and 1311 transitions. [2018-10-15 15:07:56,463 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-15 15:07:56,463 INFO L276 IsEmpty]: Start isEmpty. Operand 1289 states and 1311 transitions. [2018-10-15 15:07:56,476 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1289 [2018-10-15 15:07:56,477 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:07:56,477 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:07:56,478 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:07:56,478 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:07:56,478 INFO L82 PathProgramCache]: Analyzing trace with hash -1364199046, now seen corresponding path program 31 times [2018-10-15 15:07:56,479 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:07:56,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:08:00,388 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:08:00,389 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:08:00,389 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [47] total 47 [2018-10-15 15:08:00,390 INFO L460 AbstractCegarLoop]: Interpolant automaton has 47 states [2018-10-15 15:08:00,390 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 47 interpolants. [2018-10-15 15:08:00,391 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=2071, Unknown=0, NotChecked=0, Total=2162 [2018-10-15 15:08:00,391 INFO L87 Difference]: Start difference. First operand 1289 states and 1311 transitions. Second operand 47 states. [2018-10-15 15:08:04,445 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:08:04,445 INFO L93 Difference]: Finished difference Result 1402 states and 1426 transitions. [2018-10-15 15:08:04,446 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 69 states. [2018-10-15 15:08:04,446 INFO L78 Accepts]: Start accepts. Automaton has 47 states. Word has length 1288 [2018-10-15 15:08:04,447 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:08:04,452 INFO L225 Difference]: With dead ends: 1402 [2018-10-15 15:08:04,452 INFO L226 Difference]: Without dead ends: 1402 [2018-10-15 15:08:04,453 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 946 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=267, Invalid=7923, Unknown=0, NotChecked=0, Total=8190 [2018-10-15 15:08:04,454 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1402 states. [2018-10-15 15:08:04,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1402 to 1347. [2018-10-15 15:08:04,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1347 states. [2018-10-15 15:08:04,465 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1347 states to 1347 states and 1370 transitions. [2018-10-15 15:08:04,465 INFO L78 Accepts]: Start accepts. Automaton has 1347 states and 1370 transitions. Word has length 1288 [2018-10-15 15:08:04,466 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:08:04,466 INFO L481 AbstractCegarLoop]: Abstraction has 1347 states and 1370 transitions. [2018-10-15 15:08:04,466 INFO L482 AbstractCegarLoop]: Interpolant automaton has 47 states. [2018-10-15 15:08:04,466 INFO L276 IsEmpty]: Start isEmpty. Operand 1347 states and 1370 transitions. [2018-10-15 15:08:04,480 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1347 [2018-10-15 15:08:04,480 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:08:04,481 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:08:04,481 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:08:04,481 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:08:04,482 INFO L82 PathProgramCache]: Analyzing trace with hash 896075724, now seen corresponding path program 32 times [2018-10-15 15:08:04,482 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:08:04,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:08:08,534 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:08:08,534 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:08:08,534 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-15 15:08:08,535 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-15 15:08:08,535 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-15 15:08:08,535 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=95, Invalid=2257, Unknown=0, NotChecked=0, Total=2352 [2018-10-15 15:08:08,536 INFO L87 Difference]: Start difference. First operand 1347 states and 1370 transitions. Second operand 49 states. [2018-10-15 15:08:12,976 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:08:12,976 INFO L93 Difference]: Finished difference Result 1460 states and 1485 transitions. [2018-10-15 15:08:12,977 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-10-15 15:08:12,977 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 1346 [2018-10-15 15:08:12,978 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:08:12,982 INFO L225 Difference]: With dead ends: 1460 [2018-10-15 15:08:12,982 INFO L226 Difference]: Without dead ends: 1460 [2018-10-15 15:08:12,983 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 93 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1035 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=279, Invalid=8651, Unknown=0, NotChecked=0, Total=8930 [2018-10-15 15:08:12,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1460 states. [2018-10-15 15:08:12,994 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1460 to 1405. [2018-10-15 15:08:12,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1405 states. [2018-10-15 15:08:12,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1405 states to 1405 states and 1429 transitions. [2018-10-15 15:08:12,997 INFO L78 Accepts]: Start accepts. Automaton has 1405 states and 1429 transitions. Word has length 1346 [2018-10-15 15:08:12,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:08:12,998 INFO L481 AbstractCegarLoop]: Abstraction has 1405 states and 1429 transitions. [2018-10-15 15:08:12,998 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-15 15:08:12,998 INFO L276 IsEmpty]: Start isEmpty. Operand 1405 states and 1429 transitions. [2018-10-15 15:08:13,014 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1405 [2018-10-15 15:08:13,015 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:08:13,015 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:08:13,016 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:08:13,016 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:08:13,016 INFO L82 PathProgramCache]: Analyzing trace with hash 2119183262, now seen corresponding path program 33 times [2018-10-15 15:08:13,017 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:08:13,068 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:08:17,141 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:08:17,141 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:08:17,141 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [51] total 51 [2018-10-15 15:08:17,142 INFO L460 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-10-15 15:08:17,142 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-10-15 15:08:17,142 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=99, Invalid=2451, Unknown=0, NotChecked=0, Total=2550 [2018-10-15 15:08:17,143 INFO L87 Difference]: Start difference. First operand 1405 states and 1429 transitions. Second operand 51 states. [2018-10-15 15:08:21,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:08:21,783 INFO L93 Difference]: Finished difference Result 1518 states and 1544 transitions. [2018-10-15 15:08:21,783 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 75 states. [2018-10-15 15:08:21,783 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 1404 [2018-10-15 15:08:21,785 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:08:21,790 INFO L225 Difference]: With dead ends: 1518 [2018-10-15 15:08:21,790 INFO L226 Difference]: Without dead ends: 1518 [2018-10-15 15:08:21,791 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 100 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 97 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1128 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=291, Invalid=9411, Unknown=0, NotChecked=0, Total=9702 [2018-10-15 15:08:21,792 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1518 states. [2018-10-15 15:08:21,802 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1518 to 1463. [2018-10-15 15:08:21,802 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1463 states. [2018-10-15 15:08:21,805 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1463 states to 1463 states and 1488 transitions. [2018-10-15 15:08:21,805 INFO L78 Accepts]: Start accepts. Automaton has 1463 states and 1488 transitions. Word has length 1404 [2018-10-15 15:08:21,806 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:08:21,806 INFO L481 AbstractCegarLoop]: Abstraction has 1463 states and 1488 transitions. [2018-10-15 15:08:21,806 INFO L482 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-10-15 15:08:21,806 INFO L276 IsEmpty]: Start isEmpty. Operand 1463 states and 1488 transitions. [2018-10-15 15:08:21,823 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1463 [2018-10-15 15:08:21,823 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:08:21,824 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:08:21,824 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:08:21,824 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:08:21,825 INFO L82 PathProgramCache]: Analyzing trace with hash 412583152, now seen corresponding path program 34 times [2018-10-15 15:08:21,825 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:08:21,875 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:08:26,032 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:08:26,033 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:08:26,033 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-15 15:08:26,034 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-15 15:08:26,034 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-15 15:08:26,034 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=2653, Unknown=0, NotChecked=0, Total=2756 [2018-10-15 15:08:26,034 INFO L87 Difference]: Start difference. First operand 1463 states and 1488 transitions. Second operand 53 states. [2018-10-15 15:08:30,940 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:08:30,940 INFO L93 Difference]: Finished difference Result 1576 states and 1603 transitions. [2018-10-15 15:08:30,941 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 78 states. [2018-10-15 15:08:30,941 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 1462 [2018-10-15 15:08:30,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:08:30,946 INFO L225 Difference]: With dead ends: 1576 [2018-10-15 15:08:30,946 INFO L226 Difference]: Without dead ends: 1576 [2018-10-15 15:08:30,947 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 104 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1225 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=303, Invalid=10203, Unknown=0, NotChecked=0, Total=10506 [2018-10-15 15:08:30,947 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1576 states. [2018-10-15 15:08:30,955 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1576 to 1521. [2018-10-15 15:08:30,955 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1521 states. [2018-10-15 15:08:30,957 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1521 states to 1521 states and 1547 transitions. [2018-10-15 15:08:30,957 INFO L78 Accepts]: Start accepts. Automaton has 1521 states and 1547 transitions. Word has length 1462 [2018-10-15 15:08:30,958 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:08:30,958 INFO L481 AbstractCegarLoop]: Abstraction has 1521 states and 1547 transitions. [2018-10-15 15:08:30,958 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-15 15:08:30,958 INFO L276 IsEmpty]: Start isEmpty. Operand 1521 states and 1547 transitions. [2018-10-15 15:08:30,975 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1521 [2018-10-15 15:08:30,975 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:08:30,976 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:08:30,976 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:08:30,976 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:08:30,977 INFO L82 PathProgramCache]: Analyzing trace with hash -1970719806, now seen corresponding path program 35 times [2018-10-15 15:08:30,977 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:08:31,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:08:35,497 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:08:35,497 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:08:35,497 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [55] total 55 [2018-10-15 15:08:35,498 INFO L460 AbstractCegarLoop]: Interpolant automaton has 55 states [2018-10-15 15:08:35,499 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 55 interpolants. [2018-10-15 15:08:35,499 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=2863, Unknown=0, NotChecked=0, Total=2970 [2018-10-15 15:08:35,499 INFO L87 Difference]: Start difference. First operand 1521 states and 1547 transitions. Second operand 55 states. [2018-10-15 15:08:41,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:08:41,179 INFO L93 Difference]: Finished difference Result 1634 states and 1662 transitions. [2018-10-15 15:08:41,180 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 81 states. [2018-10-15 15:08:41,180 INFO L78 Accepts]: Start accepts. Automaton has 55 states. Word has length 1520 [2018-10-15 15:08:41,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:08:41,187 INFO L225 Difference]: With dead ends: 1634 [2018-10-15 15:08:41,187 INFO L226 Difference]: Without dead ends: 1634 [2018-10-15 15:08:41,188 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 108 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 105 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1326 ImplicationChecksByTransitivity, 3.2s TimeCoverageRelationStatistics Valid=315, Invalid=11027, Unknown=0, NotChecked=0, Total=11342 [2018-10-15 15:08:41,189 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1634 states. [2018-10-15 15:08:41,198 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1634 to 1579. [2018-10-15 15:08:41,198 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1579 states. [2018-10-15 15:08:41,200 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1579 states to 1579 states and 1606 transitions. [2018-10-15 15:08:41,200 INFO L78 Accepts]: Start accepts. Automaton has 1579 states and 1606 transitions. Word has length 1520 [2018-10-15 15:08:41,201 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:08:41,201 INFO L481 AbstractCegarLoop]: Abstraction has 1579 states and 1606 transitions. [2018-10-15 15:08:41,201 INFO L482 AbstractCegarLoop]: Interpolant automaton has 55 states. [2018-10-15 15:08:41,201 INFO L276 IsEmpty]: Start isEmpty. Operand 1579 states and 1606 transitions. [2018-10-15 15:08:41,216 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1579 [2018-10-15 15:08:41,217 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:08:41,217 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:08:41,218 INFO L424 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:08:41,218 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:08:41,218 INFO L82 PathProgramCache]: Analyzing trace with hash -1014540268, now seen corresponding path program 36 times [2018-10-15 15:08:41,219 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:08:41,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:08:46,282 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:08:46,282 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:08:46,282 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-15 15:08:46,283 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-15 15:08:46,283 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-15 15:08:46,283 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=111, Invalid=3081, Unknown=0, NotChecked=0, Total=3192 [2018-10-15 15:08:46,284 INFO L87 Difference]: Start difference. First operand 1579 states and 1606 transitions. Second operand 57 states. [2018-10-15 15:08:52,153 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:08:52,154 INFO L93 Difference]: Finished difference Result 1692 states and 1721 transitions. [2018-10-15 15:08:52,154 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-10-15 15:08:52,154 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 1578 [2018-10-15 15:08:52,156 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:08:52,162 INFO L225 Difference]: With dead ends: 1692 [2018-10-15 15:08:52,163 INFO L226 Difference]: Without dead ends: 1692 [2018-10-15 15:08:52,164 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 109 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1431 ImplicationChecksByTransitivity, 3.7s TimeCoverageRelationStatistics Valid=327, Invalid=11883, Unknown=0, NotChecked=0, Total=12210 [2018-10-15 15:08:52,165 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1692 states. [2018-10-15 15:08:52,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1692 to 1637. [2018-10-15 15:08:52,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1637 states. [2018-10-15 15:08:52,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1637 states to 1637 states and 1665 transitions. [2018-10-15 15:08:52,179 INFO L78 Accepts]: Start accepts. Automaton has 1637 states and 1665 transitions. Word has length 1578 [2018-10-15 15:08:52,180 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:08:52,180 INFO L481 AbstractCegarLoop]: Abstraction has 1637 states and 1665 transitions. [2018-10-15 15:08:52,180 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-15 15:08:52,181 INFO L276 IsEmpty]: Start isEmpty. Operand 1637 states and 1665 transitions. [2018-10-15 15:08:52,199 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1637 [2018-10-15 15:08:52,199 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:08:52,200 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:08:52,201 INFO L424 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:08:52,201 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:08:52,201 INFO L82 PathProgramCache]: Analyzing trace with hash 235672038, now seen corresponding path program 37 times [2018-10-15 15:08:52,202 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:08:52,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:08:58,440 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:08:58,440 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:08:58,440 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [59] total 59 [2018-10-15 15:08:58,441 INFO L460 AbstractCegarLoop]: Interpolant automaton has 59 states [2018-10-15 15:08:58,441 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 59 interpolants. [2018-10-15 15:08:58,441 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=115, Invalid=3307, Unknown=0, NotChecked=0, Total=3422 [2018-10-15 15:08:58,442 INFO L87 Difference]: Start difference. First operand 1637 states and 1665 transitions. Second operand 59 states. [2018-10-15 15:09:04,473 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:09:04,473 INFO L93 Difference]: Finished difference Result 1750 states and 1780 transitions. [2018-10-15 15:09:04,473 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 87 states. [2018-10-15 15:09:04,474 INFO L78 Accepts]: Start accepts. Automaton has 59 states. Word has length 1636 [2018-10-15 15:09:04,475 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:09:04,481 INFO L225 Difference]: With dead ends: 1750 [2018-10-15 15:09:04,481 INFO L226 Difference]: Without dead ends: 1750 [2018-10-15 15:09:04,481 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1540 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=339, Invalid=12771, Unknown=0, NotChecked=0, Total=13110 [2018-10-15 15:09:04,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1750 states. [2018-10-15 15:09:04,490 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1750 to 1695. [2018-10-15 15:09:04,490 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1695 states. [2018-10-15 15:09:04,492 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1695 states to 1695 states and 1724 transitions. [2018-10-15 15:09:04,492 INFO L78 Accepts]: Start accepts. Automaton has 1695 states and 1724 transitions. Word has length 1636 [2018-10-15 15:09:04,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:09:04,493 INFO L481 AbstractCegarLoop]: Abstraction has 1695 states and 1724 transitions. [2018-10-15 15:09:04,493 INFO L482 AbstractCegarLoop]: Interpolant automaton has 59 states. [2018-10-15 15:09:04,493 INFO L276 IsEmpty]: Start isEmpty. Operand 1695 states and 1724 transitions. [2018-10-15 15:09:04,508 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1695 [2018-10-15 15:09:04,508 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:09:04,509 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:09:04,509 INFO L424 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:09:04,509 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:09:04,510 INFO L82 PathProgramCache]: Analyzing trace with hash -2119597768, now seen corresponding path program 38 times [2018-10-15 15:09:04,510 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:09:04,557 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:09:11,142 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:09:11,142 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:09:11,143 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-15 15:09:11,143 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-15 15:09:11,144 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-15 15:09:11,144 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=119, Invalid=3541, Unknown=0, NotChecked=0, Total=3660 [2018-10-15 15:09:11,144 INFO L87 Difference]: Start difference. First operand 1695 states and 1724 transitions. Second operand 61 states. [2018-10-15 15:09:17,906 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:09:17,906 INFO L93 Difference]: Finished difference Result 1808 states and 1839 transitions. [2018-10-15 15:09:17,907 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 90 states. [2018-10-15 15:09:17,907 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 1694 [2018-10-15 15:09:17,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:09:17,912 INFO L225 Difference]: With dead ends: 1808 [2018-10-15 15:09:17,913 INFO L226 Difference]: Without dead ends: 1808 [2018-10-15 15:09:17,913 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 117 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1653 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=351, Invalid=13691, Unknown=0, NotChecked=0, Total=14042 [2018-10-15 15:09:17,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1808 states. [2018-10-15 15:09:17,924 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1808 to 1753. [2018-10-15 15:09:17,924 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1753 states. [2018-10-15 15:09:17,926 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1753 states to 1753 states and 1783 transitions. [2018-10-15 15:09:17,926 INFO L78 Accepts]: Start accepts. Automaton has 1753 states and 1783 transitions. Word has length 1694 [2018-10-15 15:09:17,927 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:09:17,927 INFO L481 AbstractCegarLoop]: Abstraction has 1753 states and 1783 transitions. [2018-10-15 15:09:17,927 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-15 15:09:17,927 INFO L276 IsEmpty]: Start isEmpty. Operand 1753 states and 1783 transitions. [2018-10-15 15:09:17,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1753 [2018-10-15 15:09:17,944 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:09:17,945 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:09:17,945 INFO L424 AbstractCegarLoop]: === Iteration 41 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:09:17,945 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:09:17,945 INFO L82 PathProgramCache]: Analyzing trace with hash -183908854, now seen corresponding path program 39 times [2018-10-15 15:09:17,946 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:09:18,000 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:09:23,530 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:09:23,530 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:09:23,531 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [63] total 63 [2018-10-15 15:09:23,531 INFO L460 AbstractCegarLoop]: Interpolant automaton has 63 states [2018-10-15 15:09:23,532 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 63 interpolants. [2018-10-15 15:09:23,532 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=123, Invalid=3783, Unknown=0, NotChecked=0, Total=3906 [2018-10-15 15:09:23,532 INFO L87 Difference]: Start difference. First operand 1753 states and 1783 transitions. Second operand 63 states. [2018-10-15 15:09:30,430 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:09:30,431 INFO L93 Difference]: Finished difference Result 1866 states and 1898 transitions. [2018-10-15 15:09:30,431 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-10-15 15:09:30,431 INFO L78 Accepts]: Start accepts. Automaton has 63 states. Word has length 1752 [2018-10-15 15:09:30,433 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:09:30,438 INFO L225 Difference]: With dead ends: 1866 [2018-10-15 15:09:30,439 INFO L226 Difference]: Without dead ends: 1866 [2018-10-15 15:09:30,440 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1770 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=363, Invalid=14643, Unknown=0, NotChecked=0, Total=15006 [2018-10-15 15:09:30,441 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1866 states. [2018-10-15 15:09:30,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1866 to 1811. [2018-10-15 15:09:30,453 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1811 states. [2018-10-15 15:09:30,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1811 states to 1811 states and 1842 transitions. [2018-10-15 15:09:30,456 INFO L78 Accepts]: Start accepts. Automaton has 1811 states and 1842 transitions. Word has length 1752 [2018-10-15 15:09:30,457 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:09:30,457 INFO L481 AbstractCegarLoop]: Abstraction has 1811 states and 1842 transitions. [2018-10-15 15:09:30,457 INFO L482 AbstractCegarLoop]: Interpolant automaton has 63 states. [2018-10-15 15:09:30,457 INFO L276 IsEmpty]: Start isEmpty. Operand 1811 states and 1842 transitions. [2018-10-15 15:09:30,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1811 [2018-10-15 15:09:30,475 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:09:30,476 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:09:30,476 INFO L424 AbstractCegarLoop]: === Iteration 42 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:09:30,477 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:09:30,477 INFO L82 PathProgramCache]: Analyzing trace with hash 1877934172, now seen corresponding path program 40 times [2018-10-15 15:09:30,478 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:09:30,534 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:09:36,810 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:09:36,810 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:09:36,810 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-15 15:09:36,811 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-15 15:09:36,811 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-15 15:09:36,811 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=4033, Unknown=0, NotChecked=0, Total=4160 [2018-10-15 15:09:36,811 INFO L87 Difference]: Start difference. First operand 1811 states and 1842 transitions. Second operand 65 states. [2018-10-15 15:09:44,354 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:09:44,354 INFO L93 Difference]: Finished difference Result 1924 states and 1957 transitions. [2018-10-15 15:09:44,355 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 96 states. [2018-10-15 15:09:44,355 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 1810 [2018-10-15 15:09:44,356 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:09:44,361 INFO L225 Difference]: With dead ends: 1924 [2018-10-15 15:09:44,361 INFO L226 Difference]: Without dead ends: 1924 [2018-10-15 15:09:44,363 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 125 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1891 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=375, Invalid=15627, Unknown=0, NotChecked=0, Total=16002 [2018-10-15 15:09:44,364 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1924 states. [2018-10-15 15:09:44,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1924 to 1869. [2018-10-15 15:09:44,375 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1869 states. [2018-10-15 15:09:44,378 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1869 states to 1869 states and 1901 transitions. [2018-10-15 15:09:44,378 INFO L78 Accepts]: Start accepts. Automaton has 1869 states and 1901 transitions. Word has length 1810 [2018-10-15 15:09:44,379 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:09:44,379 INFO L481 AbstractCegarLoop]: Abstraction has 1869 states and 1901 transitions. [2018-10-15 15:09:44,379 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-15 15:09:44,379 INFO L276 IsEmpty]: Start isEmpty. Operand 1869 states and 1901 transitions. [2018-10-15 15:09:44,404 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1869 [2018-10-15 15:09:44,404 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:09:44,405 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:09:44,405 INFO L424 AbstractCegarLoop]: === Iteration 43 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:09:44,405 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:09:44,406 INFO L82 PathProgramCache]: Analyzing trace with hash 489902126, now seen corresponding path program 41 times [2018-10-15 15:09:44,406 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:09:44,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:09:50,613 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:09:50,613 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:09:50,613 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [67] total 67 [2018-10-15 15:09:50,614 INFO L460 AbstractCegarLoop]: Interpolant automaton has 67 states [2018-10-15 15:09:50,614 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 67 interpolants. [2018-10-15 15:09:50,615 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=131, Invalid=4291, Unknown=0, NotChecked=0, Total=4422 [2018-10-15 15:09:50,615 INFO L87 Difference]: Start difference. First operand 1869 states and 1901 transitions. Second operand 67 states. [2018-10-15 15:09:58,300 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:09:58,301 INFO L93 Difference]: Finished difference Result 1982 states and 2016 transitions. [2018-10-15 15:09:58,301 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 99 states. [2018-10-15 15:09:58,301 INFO L78 Accepts]: Start accepts. Automaton has 67 states. Word has length 1868 [2018-10-15 15:09:58,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:09:58,306 INFO L225 Difference]: With dead ends: 1982 [2018-10-15 15:09:58,306 INFO L226 Difference]: Without dead ends: 1982 [2018-10-15 15:09:58,307 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 132 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 129 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2016 ImplicationChecksByTransitivity, 4.4s TimeCoverageRelationStatistics Valid=387, Invalid=16643, Unknown=0, NotChecked=0, Total=17030 [2018-10-15 15:09:58,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1982 states. [2018-10-15 15:09:58,320 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1982 to 1927. [2018-10-15 15:09:58,321 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1927 states. [2018-10-15 15:09:58,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1927 states to 1927 states and 1960 transitions. [2018-10-15 15:09:58,323 INFO L78 Accepts]: Start accepts. Automaton has 1927 states and 1960 transitions. Word has length 1868 [2018-10-15 15:09:58,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:09:58,324 INFO L481 AbstractCegarLoop]: Abstraction has 1927 states and 1960 transitions. [2018-10-15 15:09:58,324 INFO L482 AbstractCegarLoop]: Interpolant automaton has 67 states. [2018-10-15 15:09:58,324 INFO L276 IsEmpty]: Start isEmpty. Operand 1927 states and 1960 transitions. [2018-10-15 15:09:58,343 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1927 [2018-10-15 15:09:58,343 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:09:58,344 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:09:58,344 INFO L424 AbstractCegarLoop]: === Iteration 44 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:09:58,344 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:09:58,345 INFO L82 PathProgramCache]: Analyzing trace with hash -1127688832, now seen corresponding path program 42 times [2018-10-15 15:09:58,345 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:09:58,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:10:05,136 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:10:05,136 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:10:05,136 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-15 15:10:05,137 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-15 15:10:05,137 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-15 15:10:05,138 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=135, Invalid=4557, Unknown=0, NotChecked=0, Total=4692 [2018-10-15 15:10:05,138 INFO L87 Difference]: Start difference. First operand 1927 states and 1960 transitions. Second operand 69 states. [2018-10-15 15:10:13,227 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:10:13,227 INFO L93 Difference]: Finished difference Result 2040 states and 2075 transitions. [2018-10-15 15:10:13,228 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 102 states. [2018-10-15 15:10:13,228 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 1926 [2018-10-15 15:10:13,230 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:10:13,233 INFO L225 Difference]: With dead ends: 2040 [2018-10-15 15:10:13,233 INFO L226 Difference]: Without dead ends: 2040 [2018-10-15 15:10:13,234 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 133 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2145 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=399, Invalid=17691, Unknown=0, NotChecked=0, Total=18090 [2018-10-15 15:10:13,235 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2040 states. [2018-10-15 15:10:13,247 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2040 to 1985. [2018-10-15 15:10:13,247 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 1985 states. [2018-10-15 15:10:13,249 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1985 states to 1985 states and 2019 transitions. [2018-10-15 15:10:13,249 INFO L78 Accepts]: Start accepts. Automaton has 1985 states and 2019 transitions. Word has length 1926 [2018-10-15 15:10:13,249 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:10:13,250 INFO L481 AbstractCegarLoop]: Abstraction has 1985 states and 2019 transitions. [2018-10-15 15:10:13,250 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-15 15:10:13,250 INFO L276 IsEmpty]: Start isEmpty. Operand 1985 states and 2019 transitions. [2018-10-15 15:10:13,289 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 1985 [2018-10-15 15:10:13,289 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:10:13,290 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:10:13,290 INFO L424 AbstractCegarLoop]: === Iteration 45 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:10:13,290 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:10:13,291 INFO L82 PathProgramCache]: Analyzing trace with hash -1782992814, now seen corresponding path program 43 times [2018-10-15 15:10:13,291 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:10:13,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:10:20,528 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:10:20,529 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:10:20,529 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [71] total 71 [2018-10-15 15:10:20,530 INFO L460 AbstractCegarLoop]: Interpolant automaton has 71 states [2018-10-15 15:10:20,530 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 71 interpolants. [2018-10-15 15:10:20,530 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=139, Invalid=4831, Unknown=0, NotChecked=0, Total=4970 [2018-10-15 15:10:20,530 INFO L87 Difference]: Start difference. First operand 1985 states and 2019 transitions. Second operand 71 states. [2018-10-15 15:10:29,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:10:29,297 INFO L93 Difference]: Finished difference Result 2098 states and 2134 transitions. [2018-10-15 15:10:29,297 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 105 states. [2018-10-15 15:10:29,297 INFO L78 Accepts]: Start accepts. Automaton has 71 states. Word has length 1984 [2018-10-15 15:10:29,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:10:29,301 INFO L225 Difference]: With dead ends: 2098 [2018-10-15 15:10:29,301 INFO L226 Difference]: Without dead ends: 2098 [2018-10-15 15:10:29,302 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 140 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 137 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2278 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=411, Invalid=18771, Unknown=0, NotChecked=0, Total=19182 [2018-10-15 15:10:29,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2098 states. [2018-10-15 15:10:29,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2098 to 2043. [2018-10-15 15:10:29,312 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2043 states. [2018-10-15 15:10:29,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2043 states to 2043 states and 2078 transitions. [2018-10-15 15:10:29,313 INFO L78 Accepts]: Start accepts. Automaton has 2043 states and 2078 transitions. Word has length 1984 [2018-10-15 15:10:29,314 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:10:29,314 INFO L481 AbstractCegarLoop]: Abstraction has 2043 states and 2078 transitions. [2018-10-15 15:10:29,314 INFO L482 AbstractCegarLoop]: Interpolant automaton has 71 states. [2018-10-15 15:10:29,314 INFO L276 IsEmpty]: Start isEmpty. Operand 2043 states and 2078 transitions. [2018-10-15 15:10:29,336 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2043 [2018-10-15 15:10:29,336 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:10:29,337 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:10:29,337 INFO L424 AbstractCegarLoop]: === Iteration 46 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:10:29,337 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:10:29,338 INFO L82 PathProgramCache]: Analyzing trace with hash -400031580, now seen corresponding path program 44 times [2018-10-15 15:10:29,338 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:10:29,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:10:36,702 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:10:36,703 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:10:36,703 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-15 15:10:36,704 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-15 15:10:36,705 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-15 15:10:36,705 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=143, Invalid=5113, Unknown=0, NotChecked=0, Total=5256 [2018-10-15 15:10:36,705 INFO L87 Difference]: Start difference. First operand 2043 states and 2078 transitions. Second operand 73 states. [2018-10-15 15:10:46,103 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:10:46,104 INFO L93 Difference]: Finished difference Result 2156 states and 2193 transitions. [2018-10-15 15:10:46,104 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 108 states. [2018-10-15 15:10:46,104 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 2042 [2018-10-15 15:10:46,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:10:46,109 INFO L225 Difference]: With dead ends: 2156 [2018-10-15 15:10:46,109 INFO L226 Difference]: Without dead ends: 2156 [2018-10-15 15:10:46,110 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 141 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2415 ImplicationChecksByTransitivity, 5.3s TimeCoverageRelationStatistics Valid=423, Invalid=19883, Unknown=0, NotChecked=0, Total=20306 [2018-10-15 15:10:46,111 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2156 states. [2018-10-15 15:10:46,124 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2156 to 2101. [2018-10-15 15:10:46,124 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2101 states. [2018-10-15 15:10:46,126 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2101 states to 2101 states and 2137 transitions. [2018-10-15 15:10:46,127 INFO L78 Accepts]: Start accepts. Automaton has 2101 states and 2137 transitions. Word has length 2042 [2018-10-15 15:10:46,128 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:10:46,128 INFO L481 AbstractCegarLoop]: Abstraction has 2101 states and 2137 transitions. [2018-10-15 15:10:46,128 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-15 15:10:46,128 INFO L276 IsEmpty]: Start isEmpty. Operand 2101 states and 2137 transitions. [2018-10-15 15:10:46,159 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2101 [2018-10-15 15:10:46,159 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:10:46,160 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:10:46,161 INFO L424 AbstractCegarLoop]: === Iteration 47 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:10:46,161 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:10:46,162 INFO L82 PathProgramCache]: Analyzing trace with hash -548542858, now seen corresponding path program 45 times [2018-10-15 15:10:46,162 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:10:46,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:10:54,751 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:10:54,751 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:10:54,752 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [75] total 75 [2018-10-15 15:10:54,752 INFO L460 AbstractCegarLoop]: Interpolant automaton has 75 states [2018-10-15 15:10:54,753 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 75 interpolants. [2018-10-15 15:10:54,753 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=147, Invalid=5403, Unknown=0, NotChecked=0, Total=5550 [2018-10-15 15:10:54,753 INFO L87 Difference]: Start difference. First operand 2101 states and 2137 transitions. Second operand 75 states. [2018-10-15 15:11:04,321 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:11:04,321 INFO L93 Difference]: Finished difference Result 2214 states and 2252 transitions. [2018-10-15 15:11:04,321 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 111 states. [2018-10-15 15:11:04,322 INFO L78 Accepts]: Start accepts. Automaton has 75 states. Word has length 2100 [2018-10-15 15:11:04,323 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:11:04,327 INFO L225 Difference]: With dead ends: 2214 [2018-10-15 15:11:04,327 INFO L226 Difference]: Without dead ends: 2214 [2018-10-15 15:11:04,328 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 145 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2556 ImplicationChecksByTransitivity, 6.0s TimeCoverageRelationStatistics Valid=435, Invalid=21027, Unknown=0, NotChecked=0, Total=21462 [2018-10-15 15:11:04,329 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2214 states. [2018-10-15 15:11:04,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2214 to 2159. [2018-10-15 15:11:04,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2159 states. [2018-10-15 15:11:04,345 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2159 states to 2159 states and 2196 transitions. [2018-10-15 15:11:04,345 INFO L78 Accepts]: Start accepts. Automaton has 2159 states and 2196 transitions. Word has length 2100 [2018-10-15 15:11:04,346 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:11:04,346 INFO L481 AbstractCegarLoop]: Abstraction has 2159 states and 2196 transitions. [2018-10-15 15:11:04,346 INFO L482 AbstractCegarLoop]: Interpolant automaton has 75 states. [2018-10-15 15:11:04,346 INFO L276 IsEmpty]: Start isEmpty. Operand 2159 states and 2196 transitions. [2018-10-15 15:11:04,378 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2159 [2018-10-15 15:11:04,379 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:11:04,380 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:11:04,380 INFO L424 AbstractCegarLoop]: === Iteration 48 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:11:04,380 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:11:04,381 INFO L82 PathProgramCache]: Analyzing trace with hash 58556872, now seen corresponding path program 46 times [2018-10-15 15:11:04,381 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:11:04,459 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:11:12,935 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:11:12,935 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:11:12,936 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-15 15:11:12,937 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-15 15:11:12,937 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-15 15:11:12,937 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=151, Invalid=5701, Unknown=0, NotChecked=0, Total=5852 [2018-10-15 15:11:12,937 INFO L87 Difference]: Start difference. First operand 2159 states and 2196 transitions. Second operand 77 states. [2018-10-15 15:11:22,954 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:11:22,954 INFO L93 Difference]: Finished difference Result 2272 states and 2311 transitions. [2018-10-15 15:11:22,955 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 114 states. [2018-10-15 15:11:22,955 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 2158 [2018-10-15 15:11:22,957 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:11:22,960 INFO L225 Difference]: With dead ends: 2272 [2018-10-15 15:11:22,960 INFO L226 Difference]: Without dead ends: 2272 [2018-10-15 15:11:22,961 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 152 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 149 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2701 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=447, Invalid=22203, Unknown=0, NotChecked=0, Total=22650 [2018-10-15 15:11:22,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2272 states. [2018-10-15 15:11:22,976 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2272 to 2217. [2018-10-15 15:11:22,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2217 states. [2018-10-15 15:11:22,979 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2217 states to 2217 states and 2255 transitions. [2018-10-15 15:11:22,979 INFO L78 Accepts]: Start accepts. Automaton has 2217 states and 2255 transitions. Word has length 2158 [2018-10-15 15:11:22,980 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:11:22,980 INFO L481 AbstractCegarLoop]: Abstraction has 2217 states and 2255 transitions. [2018-10-15 15:11:22,980 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-15 15:11:22,981 INFO L276 IsEmpty]: Start isEmpty. Operand 2217 states and 2255 transitions. [2018-10-15 15:11:23,014 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2217 [2018-10-15 15:11:23,015 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:11:23,016 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:11:23,016 INFO L424 AbstractCegarLoop]: === Iteration 49 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:11:23,016 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:11:23,017 INFO L82 PathProgramCache]: Analyzing trace with hash 740356762, now seen corresponding path program 47 times [2018-10-15 15:11:23,017 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:11:23,094 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:11:32,133 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:11:32,133 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:11:32,134 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [79] total 79 [2018-10-15 15:11:32,134 INFO L460 AbstractCegarLoop]: Interpolant automaton has 79 states [2018-10-15 15:11:32,135 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 79 interpolants. [2018-10-15 15:11:32,135 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=155, Invalid=6007, Unknown=0, NotChecked=0, Total=6162 [2018-10-15 15:11:32,135 INFO L87 Difference]: Start difference. First operand 2217 states and 2255 transitions. Second operand 79 states. [2018-10-15 15:11:42,637 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:11:42,638 INFO L93 Difference]: Finished difference Result 2330 states and 2370 transitions. [2018-10-15 15:11:42,638 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-10-15 15:11:42,638 INFO L78 Accepts]: Start accepts. Automaton has 79 states. Word has length 2216 [2018-10-15 15:11:42,640 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:11:42,641 INFO L225 Difference]: With dead ends: 2330 [2018-10-15 15:11:42,641 INFO L226 Difference]: Without dead ends: 2330 [2018-10-15 15:11:42,642 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 156 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 153 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2850 ImplicationChecksByTransitivity, 6.3s TimeCoverageRelationStatistics Valid=459, Invalid=23411, Unknown=0, NotChecked=0, Total=23870 [2018-10-15 15:11:42,643 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2330 states. [2018-10-15 15:11:42,654 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2330 to 2275. [2018-10-15 15:11:42,654 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2275 states. [2018-10-15 15:11:42,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2275 states to 2275 states and 2314 transitions. [2018-10-15 15:11:42,657 INFO L78 Accepts]: Start accepts. Automaton has 2275 states and 2314 transitions. Word has length 2216 [2018-10-15 15:11:42,658 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:11:42,658 INFO L481 AbstractCegarLoop]: Abstraction has 2275 states and 2314 transitions. [2018-10-15 15:11:42,658 INFO L482 AbstractCegarLoop]: Interpolant automaton has 79 states. [2018-10-15 15:11:42,658 INFO L276 IsEmpty]: Start isEmpty. Operand 2275 states and 2314 transitions. [2018-10-15 15:11:42,695 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2275 [2018-10-15 15:11:42,696 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:11:42,697 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:11:42,697 INFO L424 AbstractCegarLoop]: === Iteration 50 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:11:42,697 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:11:42,698 INFO L82 PathProgramCache]: Analyzing trace with hash -239445780, now seen corresponding path program 48 times [2018-10-15 15:11:42,698 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:11:42,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:11:52,109 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:11:52,109 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:11:52,110 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-15 15:11:52,111 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-15 15:11:52,111 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-15 15:11:52,111 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=159, Invalid=6321, Unknown=0, NotChecked=0, Total=6480 [2018-10-15 15:11:52,112 INFO L87 Difference]: Start difference. First operand 2275 states and 2314 transitions. Second operand 81 states. [2018-10-15 15:12:03,212 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:12:03,212 INFO L93 Difference]: Finished difference Result 2388 states and 2429 transitions. [2018-10-15 15:12:03,212 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 120 states. [2018-10-15 15:12:03,213 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 2274 [2018-10-15 15:12:03,214 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:12:03,215 INFO L225 Difference]: With dead ends: 2388 [2018-10-15 15:12:03,215 INFO L226 Difference]: Without dead ends: 2388 [2018-10-15 15:12:03,217 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 157 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3003 ImplicationChecksByTransitivity, 6.5s TimeCoverageRelationStatistics Valid=471, Invalid=24651, Unknown=0, NotChecked=0, Total=25122 [2018-10-15 15:12:03,218 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2388 states. [2018-10-15 15:12:03,230 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2388 to 2333. [2018-10-15 15:12:03,230 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2333 states. [2018-10-15 15:12:03,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2333 states to 2333 states and 2373 transitions. [2018-10-15 15:12:03,232 INFO L78 Accepts]: Start accepts. Automaton has 2333 states and 2373 transitions. Word has length 2274 [2018-10-15 15:12:03,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:12:03,233 INFO L481 AbstractCegarLoop]: Abstraction has 2333 states and 2373 transitions. [2018-10-15 15:12:03,233 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-15 15:12:03,233 INFO L276 IsEmpty]: Start isEmpty. Operand 2333 states and 2373 transitions. [2018-10-15 15:12:03,260 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2333 [2018-10-15 15:12:03,260 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:12:03,261 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:12:03,261 INFO L424 AbstractCegarLoop]: === Iteration 51 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:12:03,262 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:12:03,262 INFO L82 PathProgramCache]: Analyzing trace with hash -1612458818, now seen corresponding path program 49 times [2018-10-15 15:12:03,263 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:12:03,321 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:12:13,175 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:12:13,175 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:12:13,176 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [83] total 83 [2018-10-15 15:12:13,177 INFO L460 AbstractCegarLoop]: Interpolant automaton has 83 states [2018-10-15 15:12:13,177 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 83 interpolants. [2018-10-15 15:12:13,177 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=163, Invalid=6643, Unknown=0, NotChecked=0, Total=6806 [2018-10-15 15:12:13,178 INFO L87 Difference]: Start difference. First operand 2333 states and 2373 transitions. Second operand 83 states. [2018-10-15 15:12:24,667 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:12:24,667 INFO L93 Difference]: Finished difference Result 2446 states and 2488 transitions. [2018-10-15 15:12:24,668 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 123 states. [2018-10-15 15:12:24,668 INFO L78 Accepts]: Start accepts. Automaton has 83 states. Word has length 2332 [2018-10-15 15:12:24,670 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:12:24,671 INFO L225 Difference]: With dead ends: 2446 [2018-10-15 15:12:24,672 INFO L226 Difference]: Without dead ends: 2446 [2018-10-15 15:12:24,673 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:12:24,674 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2446 states. [2018-10-15 15:12:24,683 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2446 to 2391. [2018-10-15 15:12:24,683 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2391 states. [2018-10-15 15:12:24,685 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2391 states to 2391 states and 2432 transitions. [2018-10-15 15:12:24,685 INFO L78 Accepts]: Start accepts. Automaton has 2391 states and 2432 transitions. Word has length 2332 [2018-10-15 15:12:24,686 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:12:24,686 INFO L481 AbstractCegarLoop]: Abstraction has 2391 states and 2432 transitions. [2018-10-15 15:12:24,686 INFO L482 AbstractCegarLoop]: Interpolant automaton has 83 states. [2018-10-15 15:12:24,686 INFO L276 IsEmpty]: Start isEmpty. Operand 2391 states and 2432 transitions. [2018-10-15 15:12:24,715 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2391 [2018-10-15 15:12:24,716 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:12:24,716 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:12:24,717 INFO L424 AbstractCegarLoop]: === Iteration 52 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:12:24,717 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:12:24,718 INFO L82 PathProgramCache]: Analyzing trace with hash -1487960560, now seen corresponding path program 50 times [2018-10-15 15:12:24,718 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:12:24,777 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:12:34,918 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:12:34,918 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:12:34,919 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-15 15:12:34,919 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-15 15:12:34,920 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-15 15:12:34,920 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=167, Invalid=6973, Unknown=0, NotChecked=0, Total=7140 [2018-10-15 15:12:34,920 INFO L87 Difference]: Start difference. First operand 2391 states and 2432 transitions. Second operand 85 states. [2018-10-15 15:12:47,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:12:47,196 INFO L93 Difference]: Finished difference Result 2504 states and 2547 transitions. [2018-10-15 15:12:47,197 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 126 states. [2018-10-15 15:12:47,197 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 2390 [2018-10-15 15:12:47,198 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:12:47,199 INFO L225 Difference]: With dead ends: 2504 [2018-10-15 15:12:47,199 INFO L226 Difference]: Without dead ends: 2504 [2018-10-15 15:12:47,200 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 168 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 165 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3321 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=495, Invalid=27227, Unknown=0, NotChecked=0, Total=27722 [2018-10-15 15:12:47,201 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2504 states. [2018-10-15 15:12:47,211 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2504 to 2449. [2018-10-15 15:12:47,211 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2449 states. [2018-10-15 15:12:47,213 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2449 states to 2449 states and 2491 transitions. [2018-10-15 15:12:47,213 INFO L78 Accepts]: Start accepts. Automaton has 2449 states and 2491 transitions. Word has length 2390 [2018-10-15 15:12:47,214 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:12:47,214 INFO L481 AbstractCegarLoop]: Abstraction has 2449 states and 2491 transitions. [2018-10-15 15:12:47,214 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-15 15:12:47,214 INFO L276 IsEmpty]: Start isEmpty. Operand 2449 states and 2491 transitions. [2018-10-15 15:12:47,244 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2449 [2018-10-15 15:12:47,244 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:12:47,245 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:12:47,245 INFO L424 AbstractCegarLoop]: === Iteration 53 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:12:47,245 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:12:47,246 INFO L82 PathProgramCache]: Analyzing trace with hash -1882747678, now seen corresponding path program 51 times [2018-10-15 15:12:47,246 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:12:47,307 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:12:57,818 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:12:57,818 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:12:57,819 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [87] total 87 [2018-10-15 15:12:57,819 INFO L460 AbstractCegarLoop]: Interpolant automaton has 87 states [2018-10-15 15:12:57,820 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 87 interpolants. [2018-10-15 15:12:57,820 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=171, Invalid=7311, Unknown=0, NotChecked=0, Total=7482 [2018-10-15 15:12:57,820 INFO L87 Difference]: Start difference. First operand 2449 states and 2491 transitions. Second operand 87 states. [2018-10-15 15:13:10,425 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:13:10,425 INFO L93 Difference]: Finished difference Result 2562 states and 2606 transitions. [2018-10-15 15:13:10,426 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 129 states. [2018-10-15 15:13:10,426 INFO L78 Accepts]: Start accepts. Automaton has 87 states. Word has length 2448 [2018-10-15 15:13:10,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:13:10,429 INFO L225 Difference]: With dead ends: 2562 [2018-10-15 15:13:10,429 INFO L226 Difference]: Without dead ends: 2562 [2018-10-15 15:13:10,430 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 172 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 169 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3486 ImplicationChecksByTransitivity, 7.2s TimeCoverageRelationStatistics Valid=507, Invalid=28563, Unknown=0, NotChecked=0, Total=29070 [2018-10-15 15:13:10,431 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2562 states. [2018-10-15 15:13:10,440 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2562 to 2507. [2018-10-15 15:13:10,440 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2507 states. [2018-10-15 15:13:10,442 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2507 states to 2507 states and 2550 transitions. [2018-10-15 15:13:10,442 INFO L78 Accepts]: Start accepts. Automaton has 2507 states and 2550 transitions. Word has length 2448 [2018-10-15 15:13:10,443 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:13:10,443 INFO L481 AbstractCegarLoop]: Abstraction has 2507 states and 2550 transitions. [2018-10-15 15:13:10,443 INFO L482 AbstractCegarLoop]: Interpolant automaton has 87 states. [2018-10-15 15:13:10,443 INFO L276 IsEmpty]: Start isEmpty. Operand 2507 states and 2550 transitions. [2018-10-15 15:13:10,475 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2507 [2018-10-15 15:13:10,475 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:13:10,476 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:13:10,476 INFO L424 AbstractCegarLoop]: === Iteration 54 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:13:10,476 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:13:10,477 INFO L82 PathProgramCache]: Analyzing trace with hash 1781401908, now seen corresponding path program 52 times [2018-10-15 15:13:10,477 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:13:10,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:13:21,654 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:13:21,655 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:13:21,655 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-15 15:13:21,656 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-15 15:13:21,656 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-15 15:13:21,656 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=175, Invalid=7657, Unknown=0, NotChecked=0, Total=7832 [2018-10-15 15:13:21,656 INFO L87 Difference]: Start difference. First operand 2507 states and 2550 transitions. Second operand 89 states. [2018-10-15 15:13:35,049 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:13:35,049 INFO L93 Difference]: Finished difference Result 2620 states and 2665 transitions. [2018-10-15 15:13:35,050 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 132 states. [2018-10-15 15:13:35,050 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 2506 [2018-10-15 15:13:35,052 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:13:35,053 INFO L225 Difference]: With dead ends: 2620 [2018-10-15 15:13:35,053 INFO L226 Difference]: Without dead ends: 2620 [2018-10-15 15:13:35,054 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 173 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3655 ImplicationChecksByTransitivity, 7.9s TimeCoverageRelationStatistics Valid=519, Invalid=29931, Unknown=0, NotChecked=0, Total=30450 [2018-10-15 15:13:35,056 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2620 states. [2018-10-15 15:13:35,066 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2620 to 2565. [2018-10-15 15:13:35,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2565 states. [2018-10-15 15:13:35,068 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2565 states to 2565 states and 2609 transitions. [2018-10-15 15:13:35,068 INFO L78 Accepts]: Start accepts. Automaton has 2565 states and 2609 transitions. Word has length 2506 [2018-10-15 15:13:35,069 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:13:35,069 INFO L481 AbstractCegarLoop]: Abstraction has 2565 states and 2609 transitions. [2018-10-15 15:13:35,069 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-15 15:13:35,069 INFO L276 IsEmpty]: Start isEmpty. Operand 2565 states and 2609 transitions. [2018-10-15 15:13:35,103 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2565 [2018-10-15 15:13:35,103 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:13:35,104 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:13:35,104 INFO L424 AbstractCegarLoop]: === Iteration 55 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:13:35,104 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:13:35,105 INFO L82 PathProgramCache]: Analyzing trace with hash -1031988474, now seen corresponding path program 53 times [2018-10-15 15:13:35,105 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:13:35,167 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:13:47,074 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:13:47,075 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:13:47,075 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [91] total 91 [2018-10-15 15:13:47,076 INFO L460 AbstractCegarLoop]: Interpolant automaton has 91 states [2018-10-15 15:13:47,076 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 91 interpolants. [2018-10-15 15:13:47,077 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=179, Invalid=8011, Unknown=0, NotChecked=0, Total=8190 [2018-10-15 15:13:47,077 INFO L87 Difference]: Start difference. First operand 2565 states and 2609 transitions. Second operand 91 states. [2018-10-15 15:14:01,268 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:14:01,268 INFO L93 Difference]: Finished difference Result 2678 states and 2724 transitions. [2018-10-15 15:14:01,268 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 135 states. [2018-10-15 15:14:01,269 INFO L78 Accepts]: Start accepts. Automaton has 91 states. Word has length 2564 [2018-10-15 15:14:01,271 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:14:01,272 INFO L225 Difference]: With dead ends: 2678 [2018-10-15 15:14:01,272 INFO L226 Difference]: Without dead ends: 2678 [2018-10-15 15:14:01,274 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 177 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3828 ImplicationChecksByTransitivity, 8.5s TimeCoverageRelationStatistics Valid=531, Invalid=31331, Unknown=0, NotChecked=0, Total=31862 [2018-10-15 15:14:01,275 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2678 states. [2018-10-15 15:14:01,286 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2678 to 2623. [2018-10-15 15:14:01,286 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2623 states. [2018-10-15 15:14:01,288 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2623 states to 2623 states and 2668 transitions. [2018-10-15 15:14:01,289 INFO L78 Accepts]: Start accepts. Automaton has 2623 states and 2668 transitions. Word has length 2564 [2018-10-15 15:14:01,289 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:14:01,289 INFO L481 AbstractCegarLoop]: Abstraction has 2623 states and 2668 transitions. [2018-10-15 15:14:01,289 INFO L482 AbstractCegarLoop]: Interpolant automaton has 91 states. [2018-10-15 15:14:01,290 INFO L276 IsEmpty]: Start isEmpty. Operand 2623 states and 2668 transitions. [2018-10-15 15:14:01,325 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2623 [2018-10-15 15:14:01,325 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:14:01,326 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:14:01,326 INFO L424 AbstractCegarLoop]: === Iteration 56 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:14:01,327 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:14:01,327 INFO L82 PathProgramCache]: Analyzing trace with hash 298246744, now seen corresponding path program 54 times [2018-10-15 15:14:01,328 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:14:01,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:14:13,577 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:14:13,577 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:14:13,577 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-15 15:14:13,579 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-15 15:14:13,579 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-15 15:14:13,579 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=183, Invalid=8373, Unknown=0, NotChecked=0, Total=8556 [2018-10-15 15:14:13,579 INFO L87 Difference]: Start difference. First operand 2623 states and 2668 transitions. Second operand 93 states. [2018-10-15 15:14:28,234 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:14:28,234 INFO L93 Difference]: Finished difference Result 2736 states and 2783 transitions. [2018-10-15 15:14:28,235 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 138 states. [2018-10-15 15:14:28,235 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 2622 [2018-10-15 15:14:28,237 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:14:28,238 INFO L225 Difference]: With dead ends: 2736 [2018-10-15 15:14:28,238 INFO L226 Difference]: Without dead ends: 2736 [2018-10-15 15:14:28,239 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 181 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4005 ImplicationChecksByTransitivity, 8.5s TimeCoverageRelationStatistics Valid=543, Invalid=32763, Unknown=0, NotChecked=0, Total=33306 [2018-10-15 15:14:28,240 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2736 states. [2018-10-15 15:14:28,250 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2736 to 2681. [2018-10-15 15:14:28,251 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2681 states. [2018-10-15 15:14:28,252 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2681 states to 2681 states and 2727 transitions. [2018-10-15 15:14:28,253 INFO L78 Accepts]: Start accepts. Automaton has 2681 states and 2727 transitions. Word has length 2622 [2018-10-15 15:14:28,253 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:14:28,254 INFO L481 AbstractCegarLoop]: Abstraction has 2681 states and 2727 transitions. [2018-10-15 15:14:28,254 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-15 15:14:28,254 INFO L276 IsEmpty]: Start isEmpty. Operand 2681 states and 2727 transitions. [2018-10-15 15:14:28,290 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2681 [2018-10-15 15:14:28,290 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:14:28,291 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:14:28,291 INFO L424 AbstractCegarLoop]: === Iteration 57 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:14:28,291 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:14:28,291 INFO L82 PathProgramCache]: Analyzing trace with hash -1338671318, now seen corresponding path program 55 times [2018-10-15 15:14:28,292 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:14:28,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-15 15:14:41,349 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:14:41,350 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-15 15:14:41,350 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [95] total 95 [2018-10-15 15:14:41,351 INFO L460 AbstractCegarLoop]: Interpolant automaton has 95 states [2018-10-15 15:14:41,351 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 95 interpolants. [2018-10-15 15:14:41,351 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=187, Invalid=8743, Unknown=0, NotChecked=0, Total=8930 [2018-10-15 15:14:41,352 INFO L87 Difference]: Start difference. First operand 2681 states and 2727 transitions. Second operand 95 states. [2018-10-15 15:14:56,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-15 15:14:56,520 INFO L93 Difference]: Finished difference Result 2794 states and 2842 transitions. [2018-10-15 15:14:56,520 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 141 states. [2018-10-15 15:14:56,520 INFO L78 Accepts]: Start accepts. Automaton has 95 states. Word has length 2680 [2018-10-15 15:14:56,522 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-15 15:14:56,523 INFO L225 Difference]: With dead ends: 2794 [2018-10-15 15:14:56,523 INFO L226 Difference]: Without dead ends: 2794 [2018-10-15 15:14:56,524 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 188 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4186 ImplicationChecksByTransitivity, 9.3s TimeCoverageRelationStatistics Valid=555, Invalid=34227, Unknown=0, NotChecked=0, Total=34782 [2018-10-15 15:14:56,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2794 states. [2018-10-15 15:14:56,535 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2794 to 2739. [2018-10-15 15:14:56,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 2739 states. [2018-10-15 15:14:56,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2739 states to 2739 states and 2786 transitions. [2018-10-15 15:14:56,537 INFO L78 Accepts]: Start accepts. Automaton has 2739 states and 2786 transitions. Word has length 2680 [2018-10-15 15:14:56,538 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-15 15:14:56,538 INFO L481 AbstractCegarLoop]: Abstraction has 2739 states and 2786 transitions. [2018-10-15 15:14:56,538 INFO L482 AbstractCegarLoop]: Interpolant automaton has 95 states. [2018-10-15 15:14:56,538 INFO L276 IsEmpty]: Start isEmpty. Operand 2739 states and 2786 transitions. [2018-10-15 15:14:56,574 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 2739 [2018-10-15 15:14:56,574 INFO L367 BasicCegarLoop]: Found error trace [2018-10-15 15:14:56,574 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:14:56,575 INFO L424 AbstractCegarLoop]: === Iteration 58 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-15 15:14:56,575 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-15 15:14:56,575 INFO L82 PathProgramCache]: Analyzing trace with hash 1191907708, now seen corresponding path program 56 times [2018-10-15 15:14:56,576 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-15 15:14:56,641 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat