java -Xmx8000000000 -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data --generate-csv --csv-dir csv -tc ../../../trunk/examples/toolchains/AutomizerBpl.xml -s ../../../trunk/examples/settings/heapseparator/heapsep-2018-09-18.epf -i ../../../trunk/examples/programs/20181010-MemSafetyPathprograms/count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl -------------------------------------------------------------------------------- This is Ultimate 0.1.23-093a8c0 [2018-10-14 16:36:27,856 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-10-14 16:36:27,858 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-10-14 16:36:27,869 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-10-14 16:36:27,869 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-10-14 16:36:27,870 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-10-14 16:36:27,872 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-10-14 16:36:27,874 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-10-14 16:36:27,875 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-10-14 16:36:27,876 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-10-14 16:36:27,877 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-10-14 16:36:27,877 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-10-14 16:36:27,878 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-10-14 16:36:27,879 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-10-14 16:36:27,883 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-10-14 16:36:27,883 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-10-14 16:36:27,887 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-10-14 16:36:27,889 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-10-14 16:36:27,891 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-10-14 16:36:27,896 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-10-14 16:36:27,901 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-10-14 16:36:27,902 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-10-14 16:36:27,904 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-10-14 16:36:27,904 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-10-14 16:36:27,905 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-10-14 16:36:27,905 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-10-14 16:36:27,906 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-10-14 16:36:27,907 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-10-14 16:36:27,908 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-10-14 16:36:27,909 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-10-14 16:36:27,909 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-10-14 16:36:27,910 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-10-14 16:36:27,910 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-10-14 16:36:27,910 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-10-14 16:36:27,911 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-10-14 16:36:27,912 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-10-14 16:36:27,912 INFO L98 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/heapseparator/heapsep-2018-09-18.epf [2018-10-14 16:36:27,926 INFO L110 SettingsManager]: Loading preferences was successful [2018-10-14 16:36:27,926 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-10-14 16:36:27,928 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-10-14 16:36:27,928 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-10-14 16:36:27,928 INFO L133 SettingsManager]: * Parallel states before merging=1 [2018-10-14 16:36:27,928 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-10-14 16:36:27,929 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-10-14 16:36:27,929 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-10-14 16:36:27,929 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-10-14 16:36:27,929 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_TreeInterpolation [2018-10-14 16:36:27,930 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-10-14 16:36:27,930 INFO L133 SettingsManager]: * Order in Petri net unfolding=Ken McMillan [2018-10-14 16:36:27,930 INFO L133 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2018-10-14 16:36:27,931 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-10-14 16:36:27,932 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-10-14 16:36:27,993 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-10-14 16:36:28,007 INFO L258 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-10-14 16:36:28,015 INFO L214 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2018-10-14 16:36:28,017 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2018-10-14 16:36:28,017 INFO L276 PluginConnector]: Boogie PL CUP Parser initialized [2018-10-14 16:36:28,018 INFO L418 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl [2018-10-14 16:36:28,018 INFO L111 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/programs/20181010-MemSafetyPathprograms/count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl' [2018-10-14 16:36:28,081 INFO L296 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-10-14 16:36:28,082 INFO L131 ToolchainWalker]: Walking toolchain with 3 elements. [2018-10-14 16:36:28,085 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-10-14 16:36:28,085 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-10-14 16:36:28,085 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-10-14 16:36:28,108 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:36:28" (1/1) ... [2018-10-14 16:36:28,110 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:36:28" (1/1) ... [2018-10-14 16:36:28,123 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:36:28" (1/1) ... [2018-10-14 16:36:28,124 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:36:28" (1/1) ... [2018-10-14 16:36:28,131 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:36:28" (1/1) ... [2018-10-14 16:36:28,134 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:36:28" (1/1) ... [2018-10-14 16:36:28,135 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:36:28" (1/1) ... [2018-10-14 16:36:28,137 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-10-14 16:36:28,138 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-10-14 16:36:28,138 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-10-14 16:36:28,139 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-10-14 16:36:28,140 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:36:28" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-10-14 16:36:28,200 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2018-10-14 16:36:28,200 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-10-14 16:36:28,200 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-10-14 16:36:28,704 INFO L341 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-10-14 16:36:28,705 INFO L202 PluginConnector]: Adding new model count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 04:36:28 BoogieIcfgContainer [2018-10-14 16:36:28,705 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-10-14 16:36:28,706 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-10-14 16:36:28,707 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-10-14 16:36:28,710 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-10-14 16:36:28,711 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 14.10 04:36:28" (1/2) ... [2018-10-14 16:36:28,712 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@407fc2ae and model type count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.10 04:36:28, skipping insertion in model container [2018-10-14 16:36:28,712 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.10 04:36:28" (2/2) ... [2018-10-14 16:36:28,714 INFO L112 eAbstractionObserver]: Analyzing ICFG count_down-alloca_true-valid-memsafety_true-termination.i_8.bpl [2018-10-14 16:36:28,724 INFO L136 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:Craig_TreeInterpolation Determinization: PREDICATE_ABSTRACTION [2018-10-14 16:36:28,733 INFO L148 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2018-10-14 16:36:28,751 INFO L257 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2018-10-14 16:36:28,781 INFO L133 ementStrategyFactory]: Using default assertion order modulation [2018-10-14 16:36:28,782 INFO L382 AbstractCegarLoop]: Interprodecural is true [2018-10-14 16:36:28,782 INFO L383 AbstractCegarLoop]: Hoare is false [2018-10-14 16:36:28,783 INFO L384 AbstractCegarLoop]: Compute interpolants for Craig_TreeInterpolation [2018-10-14 16:36:28,783 INFO L385 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2018-10-14 16:36:28,783 INFO L386 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-10-14 16:36:28,783 INFO L387 AbstractCegarLoop]: Difference is false [2018-10-14 16:36:28,783 INFO L388 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-10-14 16:36:28,783 INFO L393 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-10-14 16:36:28,803 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states. [2018-10-14 16:36:28,812 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-10-14 16:36:28,813 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:28,814 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:28,815 INFO L424 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:28,821 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:28,822 INFO L82 PathProgramCache]: Analyzing trace with hash 1633044116, now seen corresponding path program 1 times [2018-10-14 16:36:28,888 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:28,946 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:29,120 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:29,127 INFO L312 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-10-14 16:36:29,128 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-10-14 16:36:29,135 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-10-14 16:36:29,147 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-10-14 16:36:29,148 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-14 16:36:29,150 INFO L87 Difference]: Start difference. First operand 60 states. Second operand 4 states. [2018-10-14 16:36:29,247 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:29,247 INFO L93 Difference]: Finished difference Result 73 states and 74 transitions. [2018-10-14 16:36:29,248 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-10-14 16:36:29,249 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 32 [2018-10-14 16:36:29,249 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:29,261 INFO L225 Difference]: With dead ends: 73 [2018-10-14 16:36:29,261 INFO L226 Difference]: Without dead ends: 73 [2018-10-14 16:36:29,263 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-10-14 16:36:29,282 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2018-10-14 16:36:29,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 59. [2018-10-14 16:36:29,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 59 states. [2018-10-14 16:36:29,304 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 60 transitions. [2018-10-14 16:36:29,306 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 60 transitions. Word has length 32 [2018-10-14 16:36:29,306 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:29,306 INFO L481 AbstractCegarLoop]: Abstraction has 59 states and 60 transitions. [2018-10-14 16:36:29,307 INFO L482 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-10-14 16:36:29,307 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 60 transitions. [2018-10-14 16:36:29,308 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2018-10-14 16:36:29,309 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:29,309 INFO L375 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:29,309 INFO L424 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:29,310 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:29,310 INFO L82 PathProgramCache]: Analyzing trace with hash -60124276, now seen corresponding path program 1 times [2018-10-14 16:36:29,311 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:29,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:29,635 WARN L179 SmtUtils]: Spent 119.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 17 [2018-10-14 16:36:30,127 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:30,127 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:30,128 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2018-10-14 16:36:30,130 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2018-10-14 16:36:30,130 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2018-10-14 16:36:30,131 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2018-10-14 16:36:30,131 INFO L87 Difference]: Start difference. First operand 59 states and 60 transitions. Second operand 12 states. [2018-10-14 16:36:30,968 WARN L179 SmtUtils]: Spent 126.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-10-14 16:36:31,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:31,304 INFO L93 Difference]: Finished difference Result 121 states and 123 transitions. [2018-10-14 16:36:31,304 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-10-14 16:36:31,305 INFO L78 Accepts]: Start accepts. Automaton has 12 states. Word has length 48 [2018-10-14 16:36:31,305 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:31,308 INFO L225 Difference]: With dead ends: 121 [2018-10-14 16:36:31,309 INFO L226 Difference]: Without dead ends: 121 [2018-10-14 16:36:31,310 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 20 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=84, Invalid=296, Unknown=0, NotChecked=0, Total=380 [2018-10-14 16:36:31,311 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2018-10-14 16:36:31,319 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 80. [2018-10-14 16:36:31,320 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 80 states. [2018-10-14 16:36:31,321 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 82 transitions. [2018-10-14 16:36:31,322 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 82 transitions. Word has length 48 [2018-10-14 16:36:31,322 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:31,323 INFO L481 AbstractCegarLoop]: Abstraction has 80 states and 82 transitions. [2018-10-14 16:36:31,323 INFO L482 AbstractCegarLoop]: Interpolant automaton has 12 states. [2018-10-14 16:36:31,323 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 82 transitions. [2018-10-14 16:36:31,325 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 63 [2018-10-14 16:36:31,325 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:31,325 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:31,326 INFO L424 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:31,326 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:31,326 INFO L82 PathProgramCache]: Analyzing trace with hash -2063516096, now seen corresponding path program 1 times [2018-10-14 16:36:31,327 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:31,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:31,517 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 3 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:31,517 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:31,518 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-14 16:36:31,519 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-14 16:36:31,519 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-14 16:36:31,519 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-10-14 16:36:31,520 INFO L87 Difference]: Start difference. First operand 80 states and 82 transitions. Second operand 9 states. [2018-10-14 16:36:32,143 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:32,144 INFO L93 Difference]: Finished difference Result 105 states and 106 transitions. [2018-10-14 16:36:32,144 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-10-14 16:36:32,145 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 62 [2018-10-14 16:36:32,145 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:32,146 INFO L225 Difference]: With dead ends: 105 [2018-10-14 16:36:32,147 INFO L226 Difference]: Without dead ends: 89 [2018-10-14 16:36:32,147 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2018-10-14 16:36:32,148 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-10-14 16:36:32,153 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 75. [2018-10-14 16:36:32,153 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 75 states. [2018-10-14 16:36:32,154 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 76 transitions. [2018-10-14 16:36:32,155 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 76 transitions. Word has length 62 [2018-10-14 16:36:32,155 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:32,155 INFO L481 AbstractCegarLoop]: Abstraction has 75 states and 76 transitions. [2018-10-14 16:36:32,155 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-14 16:36:32,156 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 76 transitions. [2018-10-14 16:36:32,157 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2018-10-14 16:36:32,158 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:32,158 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:32,158 INFO L424 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:32,158 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:32,159 INFO L82 PathProgramCache]: Analyzing trace with hash -2114588540, now seen corresponding path program 2 times [2018-10-14 16:36:32,160 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:32,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:32,498 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-10-14 16:36:32,498 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:32,498 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2018-10-14 16:36:32,499 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-10-14 16:36:32,499 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-10-14 16:36:32,500 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-10-14 16:36:32,500 INFO L87 Difference]: Start difference. First operand 75 states and 76 transitions. Second operand 9 states. [2018-10-14 16:36:32,712 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:32,712 INFO L93 Difference]: Finished difference Result 88 states and 89 transitions. [2018-10-14 16:36:32,712 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-10-14 16:36:32,712 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 64 [2018-10-14 16:36:32,713 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:32,714 INFO L225 Difference]: With dead ends: 88 [2018-10-14 16:36:32,714 INFO L226 Difference]: Without dead ends: 88 [2018-10-14 16:36:32,715 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=93, Unknown=0, NotChecked=0, Total=132 [2018-10-14 16:36:32,715 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2018-10-14 16:36:32,721 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 79. [2018-10-14 16:36:32,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 79 states. [2018-10-14 16:36:32,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 80 transitions. [2018-10-14 16:36:32,723 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 80 transitions. Word has length 64 [2018-10-14 16:36:32,723 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:32,723 INFO L481 AbstractCegarLoop]: Abstraction has 79 states and 80 transitions. [2018-10-14 16:36:32,724 INFO L482 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-10-14 16:36:32,724 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 80 transitions. [2018-10-14 16:36:32,726 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2018-10-14 16:36:32,726 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:32,726 INFO L375 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:32,727 INFO L424 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:32,727 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:32,727 INFO L82 PathProgramCache]: Analyzing trace with hash -502625992, now seen corresponding path program 2 times [2018-10-14 16:36:32,728 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:32,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:33,073 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 22 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:33,073 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:33,074 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-14 16:36:33,074 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-14 16:36:33,075 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-14 16:36:33,075 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-10-14 16:36:33,076 INFO L87 Difference]: Start difference. First operand 79 states and 80 transitions. Second operand 13 states. [2018-10-14 16:36:34,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:34,161 INFO L93 Difference]: Finished difference Result 174 states and 176 transitions. [2018-10-14 16:36:34,162 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-10-14 16:36:34,162 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 78 [2018-10-14 16:36:34,163 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:34,166 INFO L225 Difference]: With dead ends: 174 [2018-10-14 16:36:34,166 INFO L226 Difference]: Without dead ends: 174 [2018-10-14 16:36:34,167 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 184 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=135, Invalid=735, Unknown=0, NotChecked=0, Total=870 [2018-10-14 16:36:34,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-10-14 16:36:34,176 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 93. [2018-10-14 16:36:34,176 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 93 states. [2018-10-14 16:36:34,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 94 transitions. [2018-10-14 16:36:34,178 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 94 transitions. Word has length 78 [2018-10-14 16:36:34,178 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:34,178 INFO L481 AbstractCegarLoop]: Abstraction has 93 states and 94 transitions. [2018-10-14 16:36:34,179 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-14 16:36:34,179 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 94 transitions. [2018-10-14 16:36:34,187 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2018-10-14 16:36:34,187 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:34,187 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:34,189 INFO L424 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:34,189 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:34,189 INFO L82 PathProgramCache]: Analyzing trace with hash 75224812, now seen corresponding path program 3 times [2018-10-14 16:36:34,190 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:34,214 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:34,422 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 8 proven. 32 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:34,422 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:34,422 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2018-10-14 16:36:34,423 INFO L460 AbstractCegarLoop]: Interpolant automaton has 13 states [2018-10-14 16:36:34,423 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2018-10-14 16:36:34,424 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2018-10-14 16:36:34,424 INFO L87 Difference]: Start difference. First operand 93 states and 94 transitions. Second operand 13 states. [2018-10-14 16:36:34,982 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:34,982 INFO L93 Difference]: Finished difference Result 153 states and 154 transitions. [2018-10-14 16:36:34,984 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-10-14 16:36:34,984 INFO L78 Accepts]: Start accepts. Automaton has 13 states. Word has length 92 [2018-10-14 16:36:34,984 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:34,985 INFO L225 Difference]: With dead ends: 153 [2018-10-14 16:36:34,985 INFO L226 Difference]: Without dead ends: 123 [2018-10-14 16:36:34,986 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 95 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=117, Invalid=483, Unknown=0, NotChecked=0, Total=600 [2018-10-14 16:36:34,987 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2018-10-14 16:36:34,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 109. [2018-10-14 16:36:34,993 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 109 states. [2018-10-14 16:36:34,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 110 transitions. [2018-10-14 16:36:34,994 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 110 transitions. Word has length 92 [2018-10-14 16:36:34,995 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:34,995 INFO L481 AbstractCegarLoop]: Abstraction has 109 states and 110 transitions. [2018-10-14 16:36:34,995 INFO L482 AbstractCegarLoop]: Interpolant automaton has 13 states. [2018-10-14 16:36:34,995 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 110 transitions. [2018-10-14 16:36:34,997 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2018-10-14 16:36:34,997 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:34,998 INFO L375 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:34,998 INFO L424 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:34,998 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:34,999 INFO L82 PathProgramCache]: Analyzing trace with hash 925474788, now seen corresponding path program 4 times [2018-10-14 16:36:34,999 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:35,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:35,441 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 0 proven. 73 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:35,442 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:35,442 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-14 16:36:35,443 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-14 16:36:35,443 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-14 16:36:35,443 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=238, Unknown=0, NotChecked=0, Total=272 [2018-10-14 16:36:35,443 INFO L87 Difference]: Start difference. First operand 109 states and 110 transitions. Second operand 17 states. [2018-10-14 16:36:37,147 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:37,148 INFO L93 Difference]: Finished difference Result 143 states and 144 transitions. [2018-10-14 16:36:37,148 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-14 16:36:37,148 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 108 [2018-10-14 16:36:37,149 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:37,150 INFO L225 Difference]: With dead ends: 143 [2018-10-14 16:36:37,150 INFO L226 Difference]: Without dead ends: 143 [2018-10-14 16:36:37,152 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 179 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=185, Invalid=1075, Unknown=0, NotChecked=0, Total=1260 [2018-10-14 16:36:37,153 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2018-10-14 16:36:37,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 123. [2018-10-14 16:36:37,158 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 123 states. [2018-10-14 16:36:37,160 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 124 transitions. [2018-10-14 16:36:37,160 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 124 transitions. Word has length 108 [2018-10-14 16:36:37,160 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:37,160 INFO L481 AbstractCegarLoop]: Abstraction has 123 states and 124 transitions. [2018-10-14 16:36:37,161 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-14 16:36:37,161 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 124 transitions. [2018-10-14 16:36:37,162 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 123 [2018-10-14 16:36:37,162 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:37,163 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:37,163 INFO L424 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:37,163 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:37,163 INFO L82 PathProgramCache]: Analyzing trace with hash -1310207848, now seen corresponding path program 5 times [2018-10-14 16:36:37,164 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:37,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:37,675 INFO L134 CoverageAnalysis]: Checked inductivity of 105 backedges. 27 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:37,675 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:37,675 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [17] total 17 [2018-10-14 16:36:37,676 INFO L460 AbstractCegarLoop]: Interpolant automaton has 17 states [2018-10-14 16:36:37,676 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2018-10-14 16:36:37,676 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=226, Unknown=0, NotChecked=0, Total=272 [2018-10-14 16:36:37,677 INFO L87 Difference]: Start difference. First operand 123 states and 124 transitions. Second operand 17 states. [2018-10-14 16:36:38,109 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:38,109 INFO L93 Difference]: Finished difference Result 197 states and 198 transitions. [2018-10-14 16:36:38,109 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-10-14 16:36:38,109 INFO L78 Accepts]: Start accepts. Automaton has 17 states. Word has length 122 [2018-10-14 16:36:38,110 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:38,111 INFO L225 Difference]: With dead ends: 197 [2018-10-14 16:36:38,111 INFO L226 Difference]: Without dead ends: 153 [2018-10-14 16:36:38,112 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 216 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=198, Invalid=924, Unknown=0, NotChecked=0, Total=1122 [2018-10-14 16:36:38,112 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2018-10-14 16:36:38,118 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 139. [2018-10-14 16:36:38,118 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 139 states. [2018-10-14 16:36:38,119 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 140 transitions. [2018-10-14 16:36:38,119 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 140 transitions. Word has length 122 [2018-10-14 16:36:38,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:38,119 INFO L481 AbstractCegarLoop]: Abstraction has 139 states and 140 transitions. [2018-10-14 16:36:38,120 INFO L482 AbstractCegarLoop]: Interpolant automaton has 17 states. [2018-10-14 16:36:38,120 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 140 transitions. [2018-10-14 16:36:38,121 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2018-10-14 16:36:38,122 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:38,122 INFO L375 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:38,122 INFO L424 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:38,122 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:38,123 INFO L82 PathProgramCache]: Analyzing trace with hash -708208752, now seen corresponding path program 6 times [2018-10-14 16:36:38,123 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:38,139 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:38,635 INFO L134 CoverageAnalysis]: Checked inductivity of 154 backedges. 14 proven. 140 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:38,635 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:38,635 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-14 16:36:38,636 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-14 16:36:38,636 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-14 16:36:38,636 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=375, Unknown=0, NotChecked=0, Total=420 [2018-10-14 16:36:38,636 INFO L87 Difference]: Start difference. First operand 139 states and 140 transitions. Second operand 21 states. [2018-10-14 16:36:40,352 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:40,352 INFO L93 Difference]: Finished difference Result 173 states and 174 transitions. [2018-10-14 16:36:40,354 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-10-14 16:36:40,354 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 138 [2018-10-14 16:36:40,355 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:40,356 INFO L225 Difference]: With dead ends: 173 [2018-10-14 16:36:40,356 INFO L226 Difference]: Without dead ends: 173 [2018-10-14 16:36:40,357 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 330 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=259, Invalid=1721, Unknown=0, NotChecked=0, Total=1980 [2018-10-14 16:36:40,358 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2018-10-14 16:36:40,365 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 153. [2018-10-14 16:36:40,366 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 153 states. [2018-10-14 16:36:40,371 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 154 transitions. [2018-10-14 16:36:40,371 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 154 transitions. Word has length 138 [2018-10-14 16:36:40,372 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:40,372 INFO L481 AbstractCegarLoop]: Abstraction has 153 states and 154 transitions. [2018-10-14 16:36:40,372 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-14 16:36:40,372 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 154 transitions. [2018-10-14 16:36:40,375 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 153 [2018-10-14 16:36:40,376 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:40,376 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:40,376 INFO L424 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:40,376 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:40,381 INFO L82 PathProgramCache]: Analyzing trace with hash -516494524, now seen corresponding path program 7 times [2018-10-14 16:36:40,382 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:40,407 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:41,352 INFO L134 CoverageAnalysis]: Checked inductivity of 200 backedges. 60 proven. 140 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:41,353 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:41,353 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21] total 21 [2018-10-14 16:36:41,353 INFO L460 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-10-14 16:36:41,354 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-10-14 16:36:41,354 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=354, Unknown=0, NotChecked=0, Total=420 [2018-10-14 16:36:41,354 INFO L87 Difference]: Start difference. First operand 153 states and 154 transitions. Second operand 21 states. [2018-10-14 16:36:42,019 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:42,019 INFO L93 Difference]: Finished difference Result 241 states and 242 transitions. [2018-10-14 16:36:42,019 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-10-14 16:36:42,019 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 152 [2018-10-14 16:36:42,020 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:42,021 INFO L225 Difference]: With dead ends: 241 [2018-10-14 16:36:42,021 INFO L226 Difference]: Without dead ends: 183 [2018-10-14 16:36:42,022 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 384 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=303, Invalid=1503, Unknown=0, NotChecked=0, Total=1806 [2018-10-14 16:36:42,023 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 183 states. [2018-10-14 16:36:42,025 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 183 to 169. [2018-10-14 16:36:42,026 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 169 states. [2018-10-14 16:36:42,026 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 169 states to 169 states and 170 transitions. [2018-10-14 16:36:42,027 INFO L78 Accepts]: Start accepts. Automaton has 169 states and 170 transitions. Word has length 152 [2018-10-14 16:36:42,027 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:42,027 INFO L481 AbstractCegarLoop]: Abstraction has 169 states and 170 transitions. [2018-10-14 16:36:42,027 INFO L482 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-10-14 16:36:42,027 INFO L276 IsEmpty]: Start isEmpty. Operand 169 states and 170 transitions. [2018-10-14 16:36:42,029 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 169 [2018-10-14 16:36:42,029 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:42,030 INFO L375 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:42,030 INFO L424 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:42,030 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:42,030 INFO L82 PathProgramCache]: Analyzing trace with hash 297545788, now seen corresponding path program 8 times [2018-10-14 16:36:42,031 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:42,047 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:42,597 INFO L134 CoverageAnalysis]: Checked inductivity of 265 backedges. 44 proven. 221 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:42,598 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:42,598 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-14 16:36:42,598 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-14 16:36:42,599 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-14 16:36:42,599 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=542, Unknown=0, NotChecked=0, Total=600 [2018-10-14 16:36:42,599 INFO L87 Difference]: Start difference. First operand 169 states and 170 transitions. Second operand 25 states. [2018-10-14 16:36:44,520 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:44,520 INFO L93 Difference]: Finished difference Result 203 states and 204 transitions. [2018-10-14 16:36:44,521 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-10-14 16:36:44,521 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 168 [2018-10-14 16:36:44,521 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:44,522 INFO L225 Difference]: With dead ends: 203 [2018-10-14 16:36:44,522 INFO L226 Difference]: Without dead ends: 203 [2018-10-14 16:36:44,524 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 523 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=349, Invalid=2513, Unknown=0, NotChecked=0, Total=2862 [2018-10-14 16:36:44,524 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2018-10-14 16:36:44,527 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 183. [2018-10-14 16:36:44,527 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 183 states. [2018-10-14 16:36:44,528 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 183 states to 183 states and 184 transitions. [2018-10-14 16:36:44,528 INFO L78 Accepts]: Start accepts. Automaton has 183 states and 184 transitions. Word has length 168 [2018-10-14 16:36:44,528 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:44,529 INFO L481 AbstractCegarLoop]: Abstraction has 183 states and 184 transitions. [2018-10-14 16:36:44,529 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-14 16:36:44,529 INFO L276 IsEmpty]: Start isEmpty. Operand 183 states and 184 transitions. [2018-10-14 16:36:44,531 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 183 [2018-10-14 16:36:44,531 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:44,531 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:44,531 INFO L424 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:44,531 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:44,532 INFO L82 PathProgramCache]: Analyzing trace with hash -198514960, now seen corresponding path program 9 times [2018-10-14 16:36:44,532 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:44,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:45,654 INFO L134 CoverageAnalysis]: Checked inductivity of 325 backedges. 107 proven. 218 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:45,655 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:45,655 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [25] total 25 [2018-10-14 16:36:45,655 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-10-14 16:36:45,656 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-10-14 16:36:45,656 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=90, Invalid=510, Unknown=0, NotChecked=0, Total=600 [2018-10-14 16:36:45,656 INFO L87 Difference]: Start difference. First operand 183 states and 184 transitions. Second operand 25 states. [2018-10-14 16:36:46,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:46,409 INFO L93 Difference]: Finished difference Result 285 states and 286 transitions. [2018-10-14 16:36:46,410 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-10-14 16:36:46,410 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 182 [2018-10-14 16:36:46,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:46,412 INFO L225 Difference]: With dead ends: 285 [2018-10-14 16:36:46,412 INFO L226 Difference]: Without dead ends: 213 [2018-10-14 16:36:46,413 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 599 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=432, Invalid=2220, Unknown=0, NotChecked=0, Total=2652 [2018-10-14 16:36:46,414 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 213 states. [2018-10-14 16:36:46,417 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 213 to 199. [2018-10-14 16:36:46,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 199 states. [2018-10-14 16:36:46,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 199 states to 199 states and 200 transitions. [2018-10-14 16:36:46,418 INFO L78 Accepts]: Start accepts. Automaton has 199 states and 200 transitions. Word has length 182 [2018-10-14 16:36:46,418 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:46,418 INFO L481 AbstractCegarLoop]: Abstraction has 199 states and 200 transitions. [2018-10-14 16:36:46,419 INFO L482 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-10-14 16:36:46,419 INFO L276 IsEmpty]: Start isEmpty. Operand 199 states and 200 transitions. [2018-10-14 16:36:46,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 199 [2018-10-14 16:36:46,421 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:46,421 INFO L375 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:46,422 INFO L424 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:46,422 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:46,422 INFO L82 PathProgramCache]: Analyzing trace with hash 1151543784, now seen corresponding path program 10 times [2018-10-14 16:36:46,423 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:46,440 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:47,112 INFO L134 CoverageAnalysis]: Checked inductivity of 406 backedges. 128 proven. 278 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:47,112 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:47,113 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-14 16:36:47,113 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-14 16:36:47,113 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-14 16:36:47,114 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=721, Unknown=0, NotChecked=0, Total=812 [2018-10-14 16:36:47,114 INFO L87 Difference]: Start difference. First operand 199 states and 200 transitions. Second operand 29 states. [2018-10-14 16:36:49,995 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:49,996 INFO L93 Difference]: Finished difference Result 233 states and 234 transitions. [2018-10-14 16:36:49,997 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 44 states. [2018-10-14 16:36:49,997 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 198 [2018-10-14 16:36:49,997 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:49,998 INFO L225 Difference]: With dead ends: 233 [2018-10-14 16:36:49,999 INFO L226 Difference]: Without dead ends: 233 [2018-10-14 16:36:50,000 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 914 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=742, Invalid=3418, Unknown=0, NotChecked=0, Total=4160 [2018-10-14 16:36:50,001 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 233 states. [2018-10-14 16:36:50,003 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 233 to 213. [2018-10-14 16:36:50,004 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-10-14 16:36:50,005 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 214 transitions. [2018-10-14 16:36:50,005 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 214 transitions. Word has length 198 [2018-10-14 16:36:50,005 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:50,005 INFO L481 AbstractCegarLoop]: Abstraction has 213 states and 214 transitions. [2018-10-14 16:36:50,006 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-14 16:36:50,006 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 214 transitions. [2018-10-14 16:36:50,007 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 213 [2018-10-14 16:36:50,007 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:50,007 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:50,007 INFO L424 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:50,008 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:50,008 INFO L82 PathProgramCache]: Analyzing trace with hash -430603364, now seen corresponding path program 11 times [2018-10-14 16:36:50,009 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:50,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:50,753 INFO L134 CoverageAnalysis]: Checked inductivity of 480 backedges. 168 proven. 312 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:50,753 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:50,753 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29] total 29 [2018-10-14 16:36:50,754 INFO L460 AbstractCegarLoop]: Interpolant automaton has 29 states [2018-10-14 16:36:50,754 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 29 interpolants. [2018-10-14 16:36:50,754 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=118, Invalid=694, Unknown=0, NotChecked=0, Total=812 [2018-10-14 16:36:50,754 INFO L87 Difference]: Start difference. First operand 213 states and 214 transitions. Second operand 29 states. [2018-10-14 16:36:52,044 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:52,045 INFO L93 Difference]: Finished difference Result 329 states and 330 transitions. [2018-10-14 16:36:52,045 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-10-14 16:36:52,045 INFO L78 Accepts]: Start accepts. Automaton has 29 states. Word has length 212 [2018-10-14 16:36:52,046 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:52,047 INFO L225 Difference]: With dead ends: 329 [2018-10-14 16:36:52,048 INFO L226 Difference]: Without dead ends: 243 [2018-10-14 16:36:52,049 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 61 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 59 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 861 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=585, Invalid=3075, Unknown=0, NotChecked=0, Total=3660 [2018-10-14 16:36:52,049 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 243 states. [2018-10-14 16:36:52,052 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 243 to 229. [2018-10-14 16:36:52,052 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 229 states. [2018-10-14 16:36:52,053 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 230 transitions. [2018-10-14 16:36:52,054 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 230 transitions. Word has length 212 [2018-10-14 16:36:52,054 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:52,054 INFO L481 AbstractCegarLoop]: Abstraction has 229 states and 230 transitions. [2018-10-14 16:36:52,054 INFO L482 AbstractCegarLoop]: Interpolant automaton has 29 states. [2018-10-14 16:36:52,054 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 230 transitions. [2018-10-14 16:36:52,055 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 229 [2018-10-14 16:36:52,055 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:52,056 INFO L375 BasicCegarLoop]: trace histogram [7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:52,056 INFO L424 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:52,056 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:52,056 INFO L82 PathProgramCache]: Analyzing trace with hash 1508918420, now seen corresponding path program 12 times [2018-10-14 16:36:52,057 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:52,085 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:52,923 INFO L134 CoverageAnalysis]: Checked inductivity of 577 backedges. 200 proven. 377 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:52,923 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:52,923 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-14 16:36:52,924 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-14 16:36:52,924 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-14 16:36:52,924 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=948, Unknown=0, NotChecked=0, Total=1056 [2018-10-14 16:36:52,925 INFO L87 Difference]: Start difference. First operand 229 states and 230 transitions. Second operand 33 states. [2018-10-14 16:36:55,050 WARN L179 SmtUtils]: Spent 165.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 41 [2018-10-14 16:36:56,179 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:56,180 INFO L93 Difference]: Finished difference Result 263 states and 264 transitions. [2018-10-14 16:36:56,180 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 49 states. [2018-10-14 16:36:56,180 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 228 [2018-10-14 16:36:56,181 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:56,182 INFO L225 Difference]: With dead ends: 263 [2018-10-14 16:36:56,182 INFO L226 Difference]: Without dead ends: 263 [2018-10-14 16:36:56,184 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1181 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=869, Invalid=4387, Unknown=0, NotChecked=0, Total=5256 [2018-10-14 16:36:56,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 263 states. [2018-10-14 16:36:56,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 263 to 243. [2018-10-14 16:36:56,188 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 243 states. [2018-10-14 16:36:56,189 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 243 states to 243 states and 244 transitions. [2018-10-14 16:36:56,189 INFO L78 Accepts]: Start accepts. Automaton has 243 states and 244 transitions. Word has length 228 [2018-10-14 16:36:56,189 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:56,189 INFO L481 AbstractCegarLoop]: Abstraction has 243 states and 244 transitions. [2018-10-14 16:36:56,189 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-14 16:36:56,190 INFO L276 IsEmpty]: Start isEmpty. Operand 243 states and 244 transitions. [2018-10-14 16:36:56,191 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 243 [2018-10-14 16:36:56,191 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:56,191 INFO L375 BasicCegarLoop]: trace histogram [8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:56,191 INFO L424 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:56,191 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:56,192 INFO L82 PathProgramCache]: Analyzing trace with hash -652705464, now seen corresponding path program 13 times [2018-10-14 16:36:56,192 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:56,210 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:57,049 INFO L134 CoverageAnalysis]: Checked inductivity of 665 backedges. 243 proven. 422 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:57,049 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:57,050 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [33] total 33 [2018-10-14 16:36:57,050 INFO L460 AbstractCegarLoop]: Interpolant automaton has 33 states [2018-10-14 16:36:57,050 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 33 interpolants. [2018-10-14 16:36:57,051 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=906, Unknown=0, NotChecked=0, Total=1056 [2018-10-14 16:36:57,051 INFO L87 Difference]: Start difference. First operand 243 states and 244 transitions. Second operand 33 states. [2018-10-14 16:36:58,213 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:36:58,213 INFO L93 Difference]: Finished difference Result 373 states and 374 transitions. [2018-10-14 16:36:58,213 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-10-14 16:36:58,213 INFO L78 Accepts]: Start accepts. Automaton has 33 states. Word has length 242 [2018-10-14 16:36:58,214 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:36:58,218 INFO L225 Difference]: With dead ends: 373 [2018-10-14 16:36:58,218 INFO L226 Difference]: Without dead ends: 273 [2018-10-14 16:36:58,220 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1170 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=762, Invalid=4068, Unknown=0, NotChecked=0, Total=4830 [2018-10-14 16:36:58,220 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 273 states. [2018-10-14 16:36:58,223 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 273 to 259. [2018-10-14 16:36:58,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 259 states. [2018-10-14 16:36:58,224 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 259 states to 259 states and 260 transitions. [2018-10-14 16:36:58,225 INFO L78 Accepts]: Start accepts. Automaton has 259 states and 260 transitions. Word has length 242 [2018-10-14 16:36:58,225 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:36:58,225 INFO L481 AbstractCegarLoop]: Abstraction has 259 states and 260 transitions. [2018-10-14 16:36:58,225 INFO L482 AbstractCegarLoop]: Interpolant automaton has 33 states. [2018-10-14 16:36:58,225 INFO L276 IsEmpty]: Start isEmpty. Operand 259 states and 260 transitions. [2018-10-14 16:36:58,227 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 259 [2018-10-14 16:36:58,227 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:36:58,227 INFO L375 BasicCegarLoop]: trace histogram [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:36:58,227 INFO L424 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:36:58,228 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:36:58,228 INFO L82 PathProgramCache]: Analyzing trace with hash 1524973632, now seen corresponding path program 14 times [2018-10-14 16:36:58,228 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:36:58,251 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:36:59,072 INFO L134 CoverageAnalysis]: Checked inductivity of 778 backedges. 288 proven. 490 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:36:59,072 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:36:59,073 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-14 16:36:59,073 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-14 16:36:59,073 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-14 16:36:59,074 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=1205, Unknown=0, NotChecked=0, Total=1332 [2018-10-14 16:36:59,074 INFO L87 Difference]: Start difference. First operand 259 states and 260 transitions. Second operand 37 states. [2018-10-14 16:37:02,981 WARN L179 SmtUtils]: Spent 136.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 41 [2018-10-14 16:37:03,382 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:03,382 INFO L93 Difference]: Finished difference Result 293 states and 294 transitions. [2018-10-14 16:37:03,389 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2018-10-14 16:37:03,389 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 258 [2018-10-14 16:37:03,390 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:03,391 INFO L225 Difference]: With dead ends: 293 [2018-10-14 16:37:03,391 INFO L226 Difference]: Without dead ends: 293 [2018-10-14 16:37:03,394 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1523 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=1031, Invalid=5611, Unknown=0, NotChecked=0, Total=6642 [2018-10-14 16:37:03,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 293 states. [2018-10-14 16:37:03,402 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 293 to 273. [2018-10-14 16:37:03,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 273 states. [2018-10-14 16:37:03,404 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 273 states to 273 states and 274 transitions. [2018-10-14 16:37:03,404 INFO L78 Accepts]: Start accepts. Automaton has 273 states and 274 transitions. Word has length 258 [2018-10-14 16:37:03,404 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:03,405 INFO L481 AbstractCegarLoop]: Abstraction has 273 states and 274 transitions. [2018-10-14 16:37:03,405 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-14 16:37:03,405 INFO L276 IsEmpty]: Start isEmpty. Operand 273 states and 274 transitions. [2018-10-14 16:37:03,406 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 273 [2018-10-14 16:37:03,406 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:03,406 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:03,407 INFO L424 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:03,407 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:03,407 INFO L82 PathProgramCache]: Analyzing trace with hash -1616535564, now seen corresponding path program 15 times [2018-10-14 16:37:03,408 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:03,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:04,449 INFO L134 CoverageAnalysis]: Checked inductivity of 880 backedges. 332 proven. 548 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:04,449 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:04,449 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [37] total 37 [2018-10-14 16:37:04,450 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2018-10-14 16:37:04,450 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2018-10-14 16:37:04,450 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=186, Invalid=1146, Unknown=0, NotChecked=0, Total=1332 [2018-10-14 16:37:04,450 INFO L87 Difference]: Start difference. First operand 273 states and 274 transitions. Second operand 37 states. [2018-10-14 16:37:06,038 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:06,039 INFO L93 Difference]: Finished difference Result 417 states and 418 transitions. [2018-10-14 16:37:06,039 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-10-14 16:37:06,039 INFO L78 Accepts]: Start accepts. Automaton has 37 states. Word has length 272 [2018-10-14 16:37:06,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:06,042 INFO L225 Difference]: With dead ends: 417 [2018-10-14 16:37:06,042 INFO L226 Difference]: Without dead ends: 303 [2018-10-14 16:37:06,045 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1526 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=963, Invalid=5199, Unknown=0, NotChecked=0, Total=6162 [2018-10-14 16:37:06,045 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 303 states. [2018-10-14 16:37:06,049 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 303 to 289. [2018-10-14 16:37:06,049 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 289 states. [2018-10-14 16:37:06,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 289 states to 289 states and 290 transitions. [2018-10-14 16:37:06,050 INFO L78 Accepts]: Start accepts. Automaton has 289 states and 290 transitions. Word has length 272 [2018-10-14 16:37:06,050 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:06,050 INFO L481 AbstractCegarLoop]: Abstraction has 289 states and 290 transitions. [2018-10-14 16:37:06,050 INFO L482 AbstractCegarLoop]: Interpolant automaton has 37 states. [2018-10-14 16:37:06,051 INFO L276 IsEmpty]: Start isEmpty. Operand 289 states and 290 transitions. [2018-10-14 16:37:06,052 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 289 [2018-10-14 16:37:06,052 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:06,052 INFO L375 BasicCegarLoop]: trace histogram [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:06,053 INFO L424 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:06,053 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:06,053 INFO L82 PathProgramCache]: Analyzing trace with hash -90972948, now seen corresponding path program 16 times [2018-10-14 16:37:06,054 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:06,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:06,985 INFO L134 CoverageAnalysis]: Checked inductivity of 1009 backedges. 392 proven. 617 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:06,985 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:06,985 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-14 16:37:06,986 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-14 16:37:06,986 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-14 16:37:06,987 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=148, Invalid=1492, Unknown=0, NotChecked=0, Total=1640 [2018-10-14 16:37:06,987 INFO L87 Difference]: Start difference. First operand 289 states and 290 transitions. Second operand 41 states. [2018-10-14 16:37:11,374 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:11,374 INFO L93 Difference]: Finished difference Result 323 states and 324 transitions. [2018-10-14 16:37:11,374 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 61 states. [2018-10-14 16:37:11,375 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 288 [2018-10-14 16:37:11,375 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:11,376 INFO L225 Difference]: With dead ends: 323 [2018-10-14 16:37:11,376 INFO L226 Difference]: Without dead ends: 323 [2018-10-14 16:37:11,379 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1906 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=1208, Invalid=6982, Unknown=0, NotChecked=0, Total=8190 [2018-10-14 16:37:11,379 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 323 states. [2018-10-14 16:37:11,382 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 323 to 303. [2018-10-14 16:37:11,383 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 303 states. [2018-10-14 16:37:11,383 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 303 states to 303 states and 304 transitions. [2018-10-14 16:37:11,384 INFO L78 Accepts]: Start accepts. Automaton has 303 states and 304 transitions. Word has length 288 [2018-10-14 16:37:11,384 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:11,384 INFO L481 AbstractCegarLoop]: Abstraction has 303 states and 304 transitions. [2018-10-14 16:37:11,384 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-14 16:37:11,385 INFO L276 IsEmpty]: Start isEmpty. Operand 303 states and 304 transitions. [2018-10-14 16:37:11,386 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 303 [2018-10-14 16:37:11,386 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:11,386 INFO L375 BasicCegarLoop]: trace histogram [10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:11,387 INFO L424 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:11,387 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:11,387 INFO L82 PathProgramCache]: Analyzing trace with hash 1258200992, now seen corresponding path program 17 times [2018-10-14 16:37:11,388 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:11,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:12,411 INFO L134 CoverageAnalysis]: Checked inductivity of 1125 backedges. 435 proven. 690 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:12,411 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:12,411 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [41] total 41 [2018-10-14 16:37:12,412 INFO L460 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-10-14 16:37:12,412 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-10-14 16:37:12,413 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=226, Invalid=1414, Unknown=0, NotChecked=0, Total=1640 [2018-10-14 16:37:12,413 INFO L87 Difference]: Start difference. First operand 303 states and 304 transitions. Second operand 41 states. [2018-10-14 16:37:13,768 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:13,769 INFO L93 Difference]: Finished difference Result 461 states and 462 transitions. [2018-10-14 16:37:13,769 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2018-10-14 16:37:13,769 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 302 [2018-10-14 16:37:13,770 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:13,772 INFO L225 Difference]: With dead ends: 461 [2018-10-14 16:37:13,772 INFO L226 Difference]: Without dead ends: 333 [2018-10-14 16:37:13,773 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 86 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1929 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=1188, Invalid=6468, Unknown=0, NotChecked=0, Total=7656 [2018-10-14 16:37:13,774 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 333 states. [2018-10-14 16:37:13,777 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 333 to 319. [2018-10-14 16:37:13,778 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 319 states. [2018-10-14 16:37:13,778 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 319 states to 319 states and 320 transitions. [2018-10-14 16:37:13,778 INFO L78 Accepts]: Start accepts. Automaton has 319 states and 320 transitions. Word has length 302 [2018-10-14 16:37:13,779 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:13,779 INFO L481 AbstractCegarLoop]: Abstraction has 319 states and 320 transitions. [2018-10-14 16:37:13,779 INFO L482 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-10-14 16:37:13,779 INFO L276 IsEmpty]: Start isEmpty. Operand 319 states and 320 transitions. [2018-10-14 16:37:13,781 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 319 [2018-10-14 16:37:13,781 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:13,781 INFO L375 BasicCegarLoop]: trace histogram [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:13,782 INFO L424 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:13,782 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:13,782 INFO L82 PathProgramCache]: Analyzing trace with hash 568187544, now seen corresponding path program 18 times [2018-10-14 16:37:13,783 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:13,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:15,834 INFO L134 CoverageAnalysis]: Checked inductivity of 1270 backedges. 512 proven. 758 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:15,835 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:15,835 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-14 16:37:15,835 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-14 16:37:15,836 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-14 16:37:15,836 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=219, Invalid=1761, Unknown=0, NotChecked=0, Total=1980 [2018-10-14 16:37:15,837 INFO L87 Difference]: Start difference. First operand 319 states and 320 transitions. Second operand 45 states. [2018-10-14 16:37:20,413 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:20,413 INFO L93 Difference]: Finished difference Result 353 states and 354 transitions. [2018-10-14 16:37:20,414 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 72 states. [2018-10-14 16:37:20,414 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 318 [2018-10-14 16:37:20,415 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:20,416 INFO L225 Difference]: With dead ends: 353 [2018-10-14 16:37:20,416 INFO L226 Difference]: Without dead ends: 353 [2018-10-14 16:37:20,418 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 109 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2716 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=1920, Invalid=9000, Unknown=0, NotChecked=0, Total=10920 [2018-10-14 16:37:20,418 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 353 states. [2018-10-14 16:37:20,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 353 to 333. [2018-10-14 16:37:20,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 333 states. [2018-10-14 16:37:20,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 333 states to 333 states and 334 transitions. [2018-10-14 16:37:20,423 INFO L78 Accepts]: Start accepts. Automaton has 333 states and 334 transitions. Word has length 318 [2018-10-14 16:37:20,423 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:20,424 INFO L481 AbstractCegarLoop]: Abstraction has 333 states and 334 transitions. [2018-10-14 16:37:20,424 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-14 16:37:20,424 INFO L276 IsEmpty]: Start isEmpty. Operand 333 states and 334 transitions. [2018-10-14 16:37:20,425 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 333 [2018-10-14 16:37:20,425 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:20,426 INFO L375 BasicCegarLoop]: trace histogram [11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:20,426 INFO L424 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:20,426 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:20,426 INFO L82 PathProgramCache]: Analyzing trace with hash -1242218420, now seen corresponding path program 19 times [2018-10-14 16:37:20,427 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:20,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:21,451 INFO L134 CoverageAnalysis]: Checked inductivity of 1400 backedges. 552 proven. 848 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:21,452 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:21,452 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [45] total 45 [2018-10-14 16:37:21,452 INFO L460 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-10-14 16:37:21,452 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-10-14 16:37:21,453 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=270, Invalid=1710, Unknown=0, NotChecked=0, Total=1980 [2018-10-14 16:37:21,453 INFO L87 Difference]: Start difference. First operand 333 states and 334 transitions. Second operand 45 states. [2018-10-14 16:37:23,419 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:23,419 INFO L93 Difference]: Finished difference Result 505 states and 506 transitions. [2018-10-14 16:37:23,420 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-10-14 16:37:23,420 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 332 [2018-10-14 16:37:23,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:23,422 INFO L225 Difference]: With dead ends: 505 [2018-10-14 16:37:23,422 INFO L226 Difference]: Without dead ends: 363 [2018-10-14 16:37:23,423 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 97 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 95 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2379 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=1437, Invalid=7875, Unknown=0, NotChecked=0, Total=9312 [2018-10-14 16:37:23,424 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 363 states. [2018-10-14 16:37:23,427 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 363 to 349. [2018-10-14 16:37:23,428 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 349 states. [2018-10-14 16:37:23,428 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 349 states to 349 states and 350 transitions. [2018-10-14 16:37:23,428 INFO L78 Accepts]: Start accepts. Automaton has 349 states and 350 transitions. Word has length 332 [2018-10-14 16:37:23,429 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:23,429 INFO L481 AbstractCegarLoop]: Abstraction has 349 states and 350 transitions. [2018-10-14 16:37:23,429 INFO L482 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-10-14 16:37:23,429 INFO L276 IsEmpty]: Start isEmpty. Operand 349 states and 350 transitions. [2018-10-14 16:37:23,431 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 349 [2018-10-14 16:37:23,431 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:23,431 INFO L375 BasicCegarLoop]: trace histogram [11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:23,431 INFO L424 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:23,432 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:23,432 INFO L82 PathProgramCache]: Analyzing trace with hash 2071263556, now seen corresponding path program 20 times [2018-10-14 16:37:23,433 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:23,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:25,115 INFO L134 CoverageAnalysis]: Checked inductivity of 1561 backedges. 648 proven. 913 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:25,116 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:25,116 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-14 16:37:25,116 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-14 16:37:25,117 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-14 16:37:25,117 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=244, Invalid=2108, Unknown=0, NotChecked=0, Total=2352 [2018-10-14 16:37:25,117 INFO L87 Difference]: Start difference. First operand 349 states and 350 transitions. Second operand 49 states. [2018-10-14 16:37:31,170 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:31,171 INFO L93 Difference]: Finished difference Result 383 states and 384 transitions. [2018-10-14 16:37:31,171 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-14 16:37:31,171 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 348 [2018-10-14 16:37:31,171 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:31,172 INFO L225 Difference]: With dead ends: 383 [2018-10-14 16:37:31,173 INFO L226 Difference]: Without dead ends: 383 [2018-10-14 16:37:31,174 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 117 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3155 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=2127, Invalid=10529, Unknown=0, NotChecked=0, Total=12656 [2018-10-14 16:37:31,174 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 383 states. [2018-10-14 16:37:31,178 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 383 to 363. [2018-10-14 16:37:31,178 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 363 states. [2018-10-14 16:37:31,179 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 363 states to 363 states and 364 transitions. [2018-10-14 16:37:31,179 INFO L78 Accepts]: Start accepts. Automaton has 363 states and 364 transitions. Word has length 348 [2018-10-14 16:37:31,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:31,179 INFO L481 AbstractCegarLoop]: Abstraction has 363 states and 364 transitions. [2018-10-14 16:37:31,180 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-14 16:37:31,180 INFO L276 IsEmpty]: Start isEmpty. Operand 363 states and 364 transitions. [2018-10-14 16:37:31,181 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 363 [2018-10-14 16:37:31,182 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:31,182 INFO L375 BasicCegarLoop]: trace histogram [12, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:31,182 INFO L424 AbstractCegarLoop]: === Iteration 24 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:31,182 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:31,183 INFO L82 PathProgramCache]: Analyzing trace with hash 288047608, now seen corresponding path program 21 times [2018-10-14 16:37:31,183 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:31,205 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:32,927 INFO L134 CoverageAnalysis]: Checked inductivity of 1705 backedges. 683 proven. 1022 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:32,928 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:32,928 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [49] total 49 [2018-10-14 16:37:32,928 INFO L460 AbstractCegarLoop]: Interpolant automaton has 49 states [2018-10-14 16:37:32,929 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 49 interpolants. [2018-10-14 16:37:32,929 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=318, Invalid=2034, Unknown=0, NotChecked=0, Total=2352 [2018-10-14 16:37:32,930 INFO L87 Difference]: Start difference. First operand 363 states and 364 transitions. Second operand 49 states. [2018-10-14 16:37:35,187 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:35,188 INFO L93 Difference]: Finished difference Result 549 states and 550 transitions. [2018-10-14 16:37:35,188 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 71 states. [2018-10-14 16:37:35,188 INFO L78 Accepts]: Start accepts. Automaton has 49 states. Word has length 362 [2018-10-14 16:37:35,189 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:35,191 INFO L225 Difference]: With dead ends: 549 [2018-10-14 16:37:35,191 INFO L226 Difference]: Without dead ends: 393 [2018-10-14 16:37:35,193 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 104 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2876 ImplicationChecksByTransitivity, 2.7s TimeCoverageRelationStatistics Valid=1710, Invalid=9420, Unknown=0, NotChecked=0, Total=11130 [2018-10-14 16:37:35,193 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 393 states. [2018-10-14 16:37:35,197 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 393 to 379. [2018-10-14 16:37:35,197 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 379 states. [2018-10-14 16:37:35,198 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 379 states to 379 states and 380 transitions. [2018-10-14 16:37:35,198 INFO L78 Accepts]: Start accepts. Automaton has 379 states and 380 transitions. Word has length 362 [2018-10-14 16:37:35,198 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:35,198 INFO L481 AbstractCegarLoop]: Abstraction has 379 states and 380 transitions. [2018-10-14 16:37:35,199 INFO L482 AbstractCegarLoop]: Interpolant automaton has 49 states. [2018-10-14 16:37:35,199 INFO L276 IsEmpty]: Start isEmpty. Operand 379 states and 380 transitions. [2018-10-14 16:37:35,217 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 379 [2018-10-14 16:37:35,218 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:35,218 INFO L375 BasicCegarLoop]: trace histogram [12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:35,218 INFO L424 AbstractCegarLoop]: === Iteration 25 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:35,218 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:35,219 INFO L82 PathProgramCache]: Analyzing trace with hash -2426640, now seen corresponding path program 22 times [2018-10-14 16:37:35,219 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:35,243 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:36,848 INFO L134 CoverageAnalysis]: Checked inductivity of 1882 backedges. 800 proven. 1082 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:36,849 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:36,849 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-14 16:37:36,849 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-14 16:37:36,850 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-14 16:37:36,850 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=271, Invalid=2485, Unknown=0, NotChecked=0, Total=2756 [2018-10-14 16:37:36,850 INFO L87 Difference]: Start difference. First operand 379 states and 380 transitions. Second operand 53 states. [2018-10-14 16:37:42,927 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:42,927 INFO L93 Difference]: Finished difference Result 413 states and 414 transitions. [2018-10-14 16:37:42,927 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-14 16:37:42,927 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 378 [2018-10-14 16:37:42,928 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:42,929 INFO L225 Difference]: With dead ends: 413 [2018-10-14 16:37:42,929 INFO L226 Difference]: Without dead ends: 413 [2018-10-14 16:37:42,930 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 126 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3697 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=2377, Invalid=12385, Unknown=0, NotChecked=0, Total=14762 [2018-10-14 16:37:42,931 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 413 states. [2018-10-14 16:37:42,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 413 to 393. [2018-10-14 16:37:42,935 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 393 states. [2018-10-14 16:37:42,936 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 393 states to 393 states and 394 transitions. [2018-10-14 16:37:42,936 INFO L78 Accepts]: Start accepts. Automaton has 393 states and 394 transitions. Word has length 378 [2018-10-14 16:37:42,936 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:42,936 INFO L481 AbstractCegarLoop]: Abstraction has 393 states and 394 transitions. [2018-10-14 16:37:42,937 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-14 16:37:42,937 INFO L276 IsEmpty]: Start isEmpty. Operand 393 states and 394 transitions. [2018-10-14 16:37:42,939 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 393 [2018-10-14 16:37:42,939 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:42,939 INFO L375 BasicCegarLoop]: trace histogram [13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:42,939 INFO L424 AbstractCegarLoop]: === Iteration 26 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:42,940 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:42,940 INFO L82 PathProgramCache]: Analyzing trace with hash 1863476388, now seen corresponding path program 23 times [2018-10-14 16:37:42,940 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:42,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:43,967 INFO L134 CoverageAnalysis]: Checked inductivity of 2040 backedges. 828 proven. 1212 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:43,967 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:43,967 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [53] total 53 [2018-10-14 16:37:43,968 INFO L460 AbstractCegarLoop]: Interpolant automaton has 53 states [2018-10-14 16:37:43,969 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 53 interpolants. [2018-10-14 16:37:43,969 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=370, Invalid=2386, Unknown=0, NotChecked=0, Total=2756 [2018-10-14 16:37:43,969 INFO L87 Difference]: Start difference. First operand 393 states and 394 transitions. Second operand 53 states. [2018-10-14 16:37:46,567 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:46,568 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-14 16:37:46,568 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 77 states. [2018-10-14 16:37:46,568 INFO L78 Accepts]: Start accepts. Automaton has 53 states. Word has length 392 [2018-10-14 16:37:46,568 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:46,570 INFO L225 Difference]: With dead ends: 593 [2018-10-14 16:37:46,570 INFO L226 Difference]: Without dead ends: 423 [2018-10-14 16:37:46,571 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3420 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=2007, Invalid=11103, Unknown=0, NotChecked=0, Total=13110 [2018-10-14 16:37:46,571 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 423 states. [2018-10-14 16:37:46,575 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 423 to 409. [2018-10-14 16:37:46,575 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 409 states. [2018-10-14 16:37:46,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 409 states to 409 states and 410 transitions. [2018-10-14 16:37:46,576 INFO L78 Accepts]: Start accepts. Automaton has 409 states and 410 transitions. Word has length 392 [2018-10-14 16:37:46,576 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:46,576 INFO L481 AbstractCegarLoop]: Abstraction has 409 states and 410 transitions. [2018-10-14 16:37:46,577 INFO L482 AbstractCegarLoop]: Interpolant automaton has 53 states. [2018-10-14 16:37:46,577 INFO L276 IsEmpty]: Start isEmpty. Operand 409 states and 410 transitions. [2018-10-14 16:37:46,579 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 409 [2018-10-14 16:37:46,579 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:46,579 INFO L375 BasicCegarLoop]: trace histogram [13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:46,579 INFO L424 AbstractCegarLoop]: === Iteration 27 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:46,580 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:46,580 INFO L82 PathProgramCache]: Analyzing trace with hash -2124310116, now seen corresponding path program 24 times [2018-10-14 16:37:46,580 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:46,606 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:49,397 INFO L134 CoverageAnalysis]: Checked inductivity of 2233 backedges. 860 proven. 1373 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:49,398 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:49,398 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-14 16:37:49,398 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-14 16:37:49,399 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-14 16:37:49,399 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=234, Invalid=2958, Unknown=0, NotChecked=0, Total=3192 [2018-10-14 16:37:49,399 INFO L87 Difference]: Start difference. First operand 409 states and 410 transitions. Second operand 57 states. [2018-10-14 16:37:56,990 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:37:56,991 INFO L93 Difference]: Finished difference Result 443 states and 444 transitions. [2018-10-14 16:37:56,991 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 84 states. [2018-10-14 16:37:56,991 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 408 [2018-10-14 16:37:56,992 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:37:56,993 INFO L225 Difference]: With dead ends: 443 [2018-10-14 16:37:56,994 INFO L226 Difference]: Without dead ends: 443 [2018-10-14 16:37:56,995 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 124 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3543 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=1645, Invalid=14105, Unknown=0, NotChecked=0, Total=15750 [2018-10-14 16:37:56,995 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 443 states. [2018-10-14 16:37:56,999 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 443 to 423. [2018-10-14 16:37:56,999 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 423 states. [2018-10-14 16:37:57,000 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 423 states to 423 states and 424 transitions. [2018-10-14 16:37:57,000 INFO L78 Accepts]: Start accepts. Automaton has 423 states and 424 transitions. Word has length 408 [2018-10-14 16:37:57,001 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:37:57,001 INFO L481 AbstractCegarLoop]: Abstraction has 423 states and 424 transitions. [2018-10-14 16:37:57,001 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-14 16:37:57,001 INFO L276 IsEmpty]: Start isEmpty. Operand 423 states and 424 transitions. [2018-10-14 16:37:57,003 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 423 [2018-10-14 16:37:57,003 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:37:57,004 INFO L375 BasicCegarLoop]: trace histogram [14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:37:57,004 INFO L424 AbstractCegarLoop]: === Iteration 28 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:37:57,004 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:37:57,004 INFO L82 PathProgramCache]: Analyzing trace with hash 1340893264, now seen corresponding path program 25 times [2018-10-14 16:37:57,005 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:37:57,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:37:58,710 INFO L134 CoverageAnalysis]: Checked inductivity of 2405 backedges. 987 proven. 1418 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:37:58,710 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:37:58,710 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [57] total 57 [2018-10-14 16:37:58,711 INFO L460 AbstractCegarLoop]: Interpolant automaton has 57 states [2018-10-14 16:37:58,711 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 57 interpolants. [2018-10-14 16:37:58,711 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=426, Invalid=2766, Unknown=0, NotChecked=0, Total=3192 [2018-10-14 16:37:58,712 INFO L87 Difference]: Start difference. First operand 423 states and 424 transitions. Second operand 57 states. [2018-10-14 16:38:01,463 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:38:01,463 INFO L93 Difference]: Finished difference Result 637 states and 638 transitions. [2018-10-14 16:38:01,463 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-10-14 16:38:01,463 INFO L78 Accepts]: Start accepts. Automaton has 57 states. Word has length 422 [2018-10-14 16:38:01,464 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:38:01,466 INFO L225 Difference]: With dead ends: 637 [2018-10-14 16:38:01,466 INFO L226 Difference]: Without dead ends: 453 [2018-10-14 16:38:01,467 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4011 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=2328, Invalid=12924, Unknown=0, NotChecked=0, Total=15252 [2018-10-14 16:38:01,468 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 453 states. [2018-10-14 16:38:01,472 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 453 to 439. [2018-10-14 16:38:01,472 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 439 states. [2018-10-14 16:38:01,473 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 439 states to 439 states and 440 transitions. [2018-10-14 16:38:01,473 INFO L78 Accepts]: Start accepts. Automaton has 439 states and 440 transitions. Word has length 422 [2018-10-14 16:38:01,473 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:38:01,473 INFO L481 AbstractCegarLoop]: Abstraction has 439 states and 440 transitions. [2018-10-14 16:38:01,473 INFO L482 AbstractCegarLoop]: Interpolant automaton has 57 states. [2018-10-14 16:38:01,474 INFO L276 IsEmpty]: Start isEmpty. Operand 439 states and 440 transitions. [2018-10-14 16:38:01,476 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 439 [2018-10-14 16:38:01,476 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:38:01,477 INFO L375 BasicCegarLoop]: trace histogram [14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:38:01,477 INFO L424 AbstractCegarLoop]: === Iteration 29 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:38:01,477 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:38:01,477 INFO L82 PathProgramCache]: Analyzing trace with hash 942316360, now seen corresponding path program 26 times [2018-10-14 16:38:01,478 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:38:01,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:38:03,225 INFO L134 CoverageAnalysis]: Checked inductivity of 2614 backedges. 1152 proven. 1462 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:38:03,225 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:38:03,226 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-14 16:38:03,226 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-14 16:38:03,226 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-14 16:38:03,227 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=411, Invalid=3249, Unknown=0, NotChecked=0, Total=3660 [2018-10-14 16:38:03,227 INFO L87 Difference]: Start difference. First operand 439 states and 440 transitions. Second operand 61 states. [2018-10-14 16:38:11,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:38:11,333 INFO L93 Difference]: Finished difference Result 473 states and 474 transitions. [2018-10-14 16:38:11,334 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 100 states. [2018-10-14 16:38:11,334 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 438 [2018-10-14 16:38:11,334 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:38:11,335 INFO L225 Difference]: With dead ends: 473 [2018-10-14 16:38:11,335 INFO L226 Difference]: Without dead ends: 473 [2018-10-14 16:38:11,337 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5462 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=3658, Invalid=17222, Unknown=0, NotChecked=0, Total=20880 [2018-10-14 16:38:11,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 473 states. [2018-10-14 16:38:11,342 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 473 to 453. [2018-10-14 16:38:11,342 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 453 states. [2018-10-14 16:38:11,343 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 453 states to 453 states and 454 transitions. [2018-10-14 16:38:11,343 INFO L78 Accepts]: Start accepts. Automaton has 453 states and 454 transitions. Word has length 438 [2018-10-14 16:38:11,343 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:38:11,343 INFO L481 AbstractCegarLoop]: Abstraction has 453 states and 454 transitions. [2018-10-14 16:38:11,343 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-14 16:38:11,344 INFO L276 IsEmpty]: Start isEmpty. Operand 453 states and 454 transitions. [2018-10-14 16:38:11,346 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 453 [2018-10-14 16:38:11,346 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:38:11,346 INFO L375 BasicCegarLoop]: trace histogram [15, 15, 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:38:11,347 INFO L424 AbstractCegarLoop]: === Iteration 30 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:38:11,347 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:38:11,347 INFO L82 PathProgramCache]: Analyzing trace with hash 768281852, now seen corresponding path program 27 times [2018-10-14 16:38:11,348 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:38:11,375 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:38:12,872 INFO L134 CoverageAnalysis]: Checked inductivity of 2800 backedges. 1160 proven. 1640 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:38:12,872 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:38:12,873 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [61] total 61 [2018-10-14 16:38:12,873 INFO L460 AbstractCegarLoop]: Interpolant automaton has 61 states [2018-10-14 16:38:12,873 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 61 interpolants. [2018-10-14 16:38:12,873 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=486, Invalid=3174, Unknown=0, NotChecked=0, Total=3660 [2018-10-14 16:38:12,874 INFO L87 Difference]: Start difference. First operand 453 states and 454 transitions. Second operand 61 states. [2018-10-14 16:38:15,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:38:15,833 INFO L93 Difference]: Finished difference Result 681 states and 682 transitions. [2018-10-14 16:38:15,833 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 89 states. [2018-10-14 16:38:15,833 INFO L78 Accepts]: Start accepts. Automaton has 61 states. Word has length 452 [2018-10-14 16:38:15,834 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:38:15,836 INFO L225 Difference]: With dead ends: 681 [2018-10-14 16:38:15,836 INFO L226 Difference]: Without dead ends: 483 [2018-10-14 16:38:15,838 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 131 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4649 ImplicationChecksByTransitivity, 2.9s TimeCoverageRelationStatistics Valid=2673, Invalid=14883, Unknown=0, NotChecked=0, Total=17556 [2018-10-14 16:38:15,839 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 483 states. [2018-10-14 16:38:15,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 483 to 469. [2018-10-14 16:38:15,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 469 states. [2018-10-14 16:38:15,843 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 469 states to 469 states and 470 transitions. [2018-10-14 16:38:15,844 INFO L78 Accepts]: Start accepts. Automaton has 469 states and 470 transitions. Word has length 452 [2018-10-14 16:38:15,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:38:15,844 INFO L481 AbstractCegarLoop]: Abstraction has 469 states and 470 transitions. [2018-10-14 16:38:15,844 INFO L482 AbstractCegarLoop]: Interpolant automaton has 61 states. [2018-10-14 16:38:15,844 INFO L276 IsEmpty]: Start isEmpty. Operand 469 states and 470 transitions. [2018-10-14 16:38:15,847 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 469 [2018-10-14 16:38:15,847 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:38:15,847 INFO L375 BasicCegarLoop]: trace histogram [15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:38:15,847 INFO L424 AbstractCegarLoop]: === Iteration 31 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:38:15,848 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:38:15,848 INFO L82 PathProgramCache]: Analyzing trace with hash 1311227380, now seen corresponding path program 28 times [2018-10-14 16:38:15,848 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:38:15,877 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:38:18,118 INFO L134 CoverageAnalysis]: Checked inductivity of 3025 backedges. 1352 proven. 1673 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:38:18,118 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:38:18,118 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-14 16:38:18,119 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-14 16:38:18,119 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-14 16:38:18,119 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=444, Invalid=3716, Unknown=0, NotChecked=0, Total=4160 [2018-10-14 16:38:18,119 INFO L87 Difference]: Start difference. First operand 469 states and 470 transitions. Second operand 65 states. [2018-10-14 16:38:26,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:38:26,929 INFO L93 Difference]: Finished difference Result 503 states and 504 transitions. [2018-10-14 16:38:26,929 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 105 states. [2018-10-14 16:38:26,929 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 468 [2018-10-14 16:38:26,929 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:38:26,931 INFO L225 Difference]: With dead ends: 503 [2018-10-14 16:38:26,931 INFO L226 Difference]: Without dead ends: 503 [2018-10-14 16:38:26,932 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 151 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6073 ImplicationChecksByTransitivity, 7.0s TimeCoverageRelationStatistics Valid=3945, Invalid=19311, Unknown=0, NotChecked=0, Total=23256 [2018-10-14 16:38:26,932 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 503 states. [2018-10-14 16:38:26,935 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 503 to 483. [2018-10-14 16:38:26,936 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 483 states. [2018-10-14 16:38:26,936 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 483 states to 483 states and 484 transitions. [2018-10-14 16:38:26,937 INFO L78 Accepts]: Start accepts. Automaton has 483 states and 484 transitions. Word has length 468 [2018-10-14 16:38:26,937 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:38:26,937 INFO L481 AbstractCegarLoop]: Abstraction has 483 states and 484 transitions. [2018-10-14 16:38:26,937 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-14 16:38:26,937 INFO L276 IsEmpty]: Start isEmpty. Operand 483 states and 484 transitions. [2018-10-14 16:38:26,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 483 [2018-10-14 16:38:26,940 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:38:26,940 INFO L375 BasicCegarLoop]: trace histogram [16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:38:26,941 INFO L424 AbstractCegarLoop]: === Iteration 32 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:38:26,941 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:38:26,941 INFO L82 PathProgramCache]: Analyzing trace with hash 143659688, now seen corresponding path program 29 times [2018-10-14 16:38:26,942 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:38:26,970 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:38:29,014 INFO L134 CoverageAnalysis]: Checked inductivity of 3225 backedges. 1347 proven. 1878 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:38:29,015 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:38:29,015 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [65] total 65 [2018-10-14 16:38:29,015 INFO L460 AbstractCegarLoop]: Interpolant automaton has 65 states [2018-10-14 16:38:29,016 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 65 interpolants. [2018-10-14 16:38:29,016 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=550, Invalid=3610, Unknown=0, NotChecked=0, Total=4160 [2018-10-14 16:38:29,016 INFO L87 Difference]: Start difference. First operand 483 states and 484 transitions. Second operand 65 states. [2018-10-14 16:38:32,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:38:32,704 INFO L93 Difference]: Finished difference Result 725 states and 726 transitions. [2018-10-14 16:38:32,704 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 95 states. [2018-10-14 16:38:32,704 INFO L78 Accepts]: Start accepts. Automaton has 65 states. Word has length 482 [2018-10-14 16:38:32,705 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:38:32,707 INFO L225 Difference]: With dead ends: 725 [2018-10-14 16:38:32,707 INFO L226 Difference]: Without dead ends: 513 [2018-10-14 16:38:32,708 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5334 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=3042, Invalid=16980, Unknown=0, NotChecked=0, Total=20022 [2018-10-14 16:38:32,709 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 513 states. [2018-10-14 16:38:32,712 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 513 to 499. [2018-10-14 16:38:32,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 499 states. [2018-10-14 16:38:32,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 499 states to 499 states and 500 transitions. [2018-10-14 16:38:32,714 INFO L78 Accepts]: Start accepts. Automaton has 499 states and 500 transitions. Word has length 482 [2018-10-14 16:38:32,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:38:32,714 INFO L481 AbstractCegarLoop]: Abstraction has 499 states and 500 transitions. [2018-10-14 16:38:32,714 INFO L482 AbstractCegarLoop]: Interpolant automaton has 65 states. [2018-10-14 16:38:32,714 INFO L276 IsEmpty]: Start isEmpty. Operand 499 states and 500 transitions. [2018-10-14 16:38:32,717 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 499 [2018-10-14 16:38:32,717 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:38:32,718 INFO L375 BasicCegarLoop]: trace histogram [16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:38:32,718 INFO L424 AbstractCegarLoop]: === Iteration 33 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:38:32,718 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:38:32,718 INFO L82 PathProgramCache]: Analyzing trace with hash 1796915616, now seen corresponding path program 30 times [2018-10-14 16:38:32,719 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:38:32,749 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:38:34,724 INFO L134 CoverageAnalysis]: Checked inductivity of 3466 backedges. 1568 proven. 1898 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:38:34,724 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:38:34,725 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-14 16:38:34,725 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-14 16:38:34,726 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-14 16:38:34,726 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=479, Invalid=4213, Unknown=0, NotChecked=0, Total=4692 [2018-10-14 16:38:34,726 INFO L87 Difference]: Start difference. First operand 499 states and 500 transitions. Second operand 69 states. [2018-10-14 16:38:45,041 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:38:45,041 INFO L93 Difference]: Finished difference Result 533 states and 534 transitions. [2018-10-14 16:38:45,042 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 111 states. [2018-10-14 16:38:45,042 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 498 [2018-10-14 16:38:45,042 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:38:45,044 INFO L225 Difference]: With dead ends: 533 [2018-10-14 16:38:45,044 INFO L226 Difference]: Without dead ends: 533 [2018-10-14 16:38:45,045 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 160 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6815 ImplicationChecksByTransitivity, 7.6s TimeCoverageRelationStatistics Valid=4283, Invalid=21799, Unknown=0, NotChecked=0, Total=26082 [2018-10-14 16:38:45,045 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 533 states. [2018-10-14 16:38:45,049 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 533 to 513. [2018-10-14 16:38:45,049 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 513 states. [2018-10-14 16:38:45,050 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 513 states to 513 states and 514 transitions. [2018-10-14 16:38:45,051 INFO L78 Accepts]: Start accepts. Automaton has 513 states and 514 transitions. Word has length 498 [2018-10-14 16:38:45,051 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:38:45,051 INFO L481 AbstractCegarLoop]: Abstraction has 513 states and 514 transitions. [2018-10-14 16:38:45,051 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-14 16:38:45,051 INFO L276 IsEmpty]: Start isEmpty. Operand 513 states and 514 transitions. [2018-10-14 16:38:45,054 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 513 [2018-10-14 16:38:45,054 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:38:45,055 INFO L375 BasicCegarLoop]: trace histogram [17, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:38:45,055 INFO L424 AbstractCegarLoop]: === Iteration 34 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:38:45,055 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:38:45,055 INFO L82 PathProgramCache]: Analyzing trace with hash -236111532, now seen corresponding path program 31 times [2018-10-14 16:38:45,056 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:38:45,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:38:46,867 INFO L134 CoverageAnalysis]: Checked inductivity of 3680 backedges. 1548 proven. 2132 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:38:46,868 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:38:46,868 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [69] total 69 [2018-10-14 16:38:46,868 INFO L460 AbstractCegarLoop]: Interpolant automaton has 69 states [2018-10-14 16:38:46,869 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 69 interpolants. [2018-10-14 16:38:46,869 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=618, Invalid=4074, Unknown=0, NotChecked=0, Total=4692 [2018-10-14 16:38:46,869 INFO L87 Difference]: Start difference. First operand 513 states and 514 transitions. Second operand 69 states. [2018-10-14 16:38:51,207 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:38:51,208 INFO L93 Difference]: Finished difference Result 769 states and 770 transitions. [2018-10-14 16:38:51,208 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 101 states. [2018-10-14 16:38:51,208 INFO L78 Accepts]: Start accepts. Automaton has 69 states. Word has length 512 [2018-10-14 16:38:51,209 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:38:51,212 INFO L225 Difference]: With dead ends: 769 [2018-10-14 16:38:51,212 INFO L226 Difference]: Without dead ends: 543 [2018-10-14 16:38:51,213 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 149 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6066 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=3435, Invalid=19215, Unknown=0, NotChecked=0, Total=22650 [2018-10-14 16:38:51,214 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 543 states. [2018-10-14 16:38:51,218 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 543 to 529. [2018-10-14 16:38:51,218 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 529 states. [2018-10-14 16:38:51,219 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 529 states to 529 states and 530 transitions. [2018-10-14 16:38:51,219 INFO L78 Accepts]: Start accepts. Automaton has 529 states and 530 transitions. Word has length 512 [2018-10-14 16:38:51,219 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:38:51,219 INFO L481 AbstractCegarLoop]: Abstraction has 529 states and 530 transitions. [2018-10-14 16:38:51,219 INFO L482 AbstractCegarLoop]: Interpolant automaton has 69 states. [2018-10-14 16:38:51,220 INFO L276 IsEmpty]: Start isEmpty. Operand 529 states and 530 transitions. [2018-10-14 16:38:51,223 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 529 [2018-10-14 16:38:51,223 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:38:51,223 INFO L375 BasicCegarLoop]: trace histogram [17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:38:51,223 INFO L424 AbstractCegarLoop]: === Iteration 35 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:38:51,224 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:38:51,224 INFO L82 PathProgramCache]: Analyzing trace with hash 1083532876, now seen corresponding path program 32 times [2018-10-14 16:38:51,225 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:38:51,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:38:54,202 INFO L134 CoverageAnalysis]: Checked inductivity of 3937 backedges. 1800 proven. 2137 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:38:54,202 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:38:54,202 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-14 16:38:54,203 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-14 16:38:54,203 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-14 16:38:54,203 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=516, Invalid=4740, Unknown=0, NotChecked=0, Total=5256 [2018-10-14 16:38:54,204 INFO L87 Difference]: Start difference. First operand 529 states and 530 transitions. Second operand 73 states. [2018-10-14 16:39:06,138 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:39:06,138 INFO L93 Difference]: Finished difference Result 563 states and 564 transitions. [2018-10-14 16:39:06,138 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 117 states. [2018-10-14 16:39:06,138 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 528 [2018-10-14 16:39:06,139 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:39:06,140 INFO L225 Difference]: With dead ends: 563 [2018-10-14 16:39:06,140 INFO L226 Difference]: Without dead ends: 563 [2018-10-14 16:39:06,141 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 175 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 169 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7598 ImplicationChecksByTransitivity, 9.2s TimeCoverageRelationStatistics Valid=4636, Invalid=24434, Unknown=0, NotChecked=0, Total=29070 [2018-10-14 16:39:06,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 563 states. [2018-10-14 16:39:06,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 563 to 543. [2018-10-14 16:39:06,145 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 543 states. [2018-10-14 16:39:06,146 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 543 states to 543 states and 544 transitions. [2018-10-14 16:39:06,146 INFO L78 Accepts]: Start accepts. Automaton has 543 states and 544 transitions. Word has length 528 [2018-10-14 16:39:06,147 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:39:06,147 INFO L481 AbstractCegarLoop]: Abstraction has 543 states and 544 transitions. [2018-10-14 16:39:06,147 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-14 16:39:06,147 INFO L276 IsEmpty]: Start isEmpty. Operand 543 states and 544 transitions. [2018-10-14 16:39:06,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 543 [2018-10-14 16:39:06,151 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:39:06,151 INFO L375 BasicCegarLoop]: trace histogram [18, 18, 18, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:39:06,151 INFO L424 AbstractCegarLoop]: === Iteration 36 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:39:06,151 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:39:06,152 INFO L82 PathProgramCache]: Analyzing trace with hash -1721483008, now seen corresponding path program 33 times [2018-10-14 16:39:06,152 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:39:06,185 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:39:09,044 INFO L134 CoverageAnalysis]: Checked inductivity of 4165 backedges. 1763 proven. 2402 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:39:09,045 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:39:09,045 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [73] total 73 [2018-10-14 16:39:09,045 INFO L460 AbstractCegarLoop]: Interpolant automaton has 73 states [2018-10-14 16:39:09,045 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 73 interpolants. [2018-10-14 16:39:09,046 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=690, Invalid=4566, Unknown=0, NotChecked=0, Total=5256 [2018-10-14 16:39:09,046 INFO L87 Difference]: Start difference. First operand 543 states and 544 transitions. Second operand 73 states. [2018-10-14 16:39:13,605 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:39:13,605 INFO L93 Difference]: Finished difference Result 813 states and 814 transitions. [2018-10-14 16:39:13,605 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 107 states. [2018-10-14 16:39:13,605 INFO L78 Accepts]: Start accepts. Automaton has 73 states. Word has length 542 [2018-10-14 16:39:13,606 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:39:13,608 INFO L225 Difference]: With dead ends: 813 [2018-10-14 16:39:13,608 INFO L226 Difference]: Without dead ends: 573 [2018-10-14 16:39:13,609 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 160 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 158 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6845 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=3852, Invalid=21588, Unknown=0, NotChecked=0, Total=25440 [2018-10-14 16:39:13,610 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 573 states. [2018-10-14 16:39:13,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 573 to 559. [2018-10-14 16:39:13,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 559 states. [2018-10-14 16:39:13,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 559 states to 559 states and 560 transitions. [2018-10-14 16:39:13,615 INFO L78 Accepts]: Start accepts. Automaton has 559 states and 560 transitions. Word has length 542 [2018-10-14 16:39:13,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:39:13,616 INFO L481 AbstractCegarLoop]: Abstraction has 559 states and 560 transitions. [2018-10-14 16:39:13,616 INFO L482 AbstractCegarLoop]: Interpolant automaton has 73 states. [2018-10-14 16:39:13,616 INFO L276 IsEmpty]: Start isEmpty. Operand 559 states and 560 transitions. [2018-10-14 16:39:13,619 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 559 [2018-10-14 16:39:13,620 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:39:13,620 INFO L375 BasicCegarLoop]: trace histogram [18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:39:13,620 INFO L424 AbstractCegarLoop]: === Iteration 37 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:39:13,620 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:39:13,621 INFO L82 PathProgramCache]: Analyzing trace with hash 368667640, now seen corresponding path program 34 times [2018-10-14 16:39:13,621 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:39:13,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:39:16,078 INFO L134 CoverageAnalysis]: Checked inductivity of 4438 backedges. 2048 proven. 2390 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:39:16,078 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:39:16,079 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-14 16:39:16,079 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-14 16:39:16,080 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-14 16:39:16,080 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=667, Invalid=5185, Unknown=0, NotChecked=0, Total=5852 [2018-10-14 16:39:16,080 INFO L87 Difference]: Start difference. First operand 559 states and 560 transitions. Second operand 77 states. [2018-10-14 16:39:27,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:39:27,782 INFO L93 Difference]: Finished difference Result 593 states and 594 transitions. [2018-10-14 16:39:27,783 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 128 states. [2018-10-14 16:39:27,783 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 558 [2018-10-14 16:39:27,783 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:39:27,785 INFO L225 Difference]: With dead ends: 593 [2018-10-14 16:39:27,785 INFO L226 Difference]: Without dead ends: 593 [2018-10-14 16:39:27,786 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 189 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 183 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9152 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=5956, Invalid=28084, Unknown=0, NotChecked=0, Total=34040 [2018-10-14 16:39:27,787 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 593 states. [2018-10-14 16:39:27,790 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 593 to 573. [2018-10-14 16:39:27,791 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 573 states. [2018-10-14 16:39:27,791 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 573 states to 573 states and 574 transitions. [2018-10-14 16:39:27,792 INFO L78 Accepts]: Start accepts. Automaton has 573 states and 574 transitions. Word has length 558 [2018-10-14 16:39:27,792 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:39:27,792 INFO L481 AbstractCegarLoop]: Abstraction has 573 states and 574 transitions. [2018-10-14 16:39:27,792 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-14 16:39:27,792 INFO L276 IsEmpty]: Start isEmpty. Operand 573 states and 574 transitions. [2018-10-14 16:39:27,796 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 573 [2018-10-14 16:39:27,796 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:39:27,796 INFO L375 BasicCegarLoop]: trace histogram [19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:39:27,797 INFO L424 AbstractCegarLoop]: === Iteration 38 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:39:27,797 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:39:27,797 INFO L82 PathProgramCache]: Analyzing trace with hash -666441300, now seen corresponding path program 35 times [2018-10-14 16:39:27,798 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:39:27,834 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:39:30,259 INFO L134 CoverageAnalysis]: Checked inductivity of 4680 backedges. 1992 proven. 2688 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:39:30,260 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:39:30,260 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [77] total 77 [2018-10-14 16:39:30,260 INFO L460 AbstractCegarLoop]: Interpolant automaton has 77 states [2018-10-14 16:39:30,261 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 77 interpolants. [2018-10-14 16:39:30,261 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=766, Invalid=5086, Unknown=0, NotChecked=0, Total=5852 [2018-10-14 16:39:30,262 INFO L87 Difference]: Start difference. First operand 573 states and 574 transitions. Second operand 77 states. [2018-10-14 16:39:35,356 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:39:35,357 INFO L93 Difference]: Finished difference Result 857 states and 858 transitions. [2018-10-14 16:39:35,357 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 113 states. [2018-10-14 16:39:35,357 INFO L78 Accepts]: Start accepts. Automaton has 77 states. Word has length 572 [2018-10-14 16:39:35,358 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:39:35,361 INFO L225 Difference]: With dead ends: 857 [2018-10-14 16:39:35,361 INFO L226 Difference]: Without dead ends: 603 [2018-10-14 16:39:35,362 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 167 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7671 ImplicationChecksByTransitivity, 4.7s TimeCoverageRelationStatistics Valid=4293, Invalid=24099, Unknown=0, NotChecked=0, Total=28392 [2018-10-14 16:39:35,363 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 603 states. [2018-10-14 16:39:35,367 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 603 to 589. [2018-10-14 16:39:35,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 589 states. [2018-10-14 16:39:35,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 589 states to 589 states and 590 transitions. [2018-10-14 16:39:35,368 INFO L78 Accepts]: Start accepts. Automaton has 589 states and 590 transitions. Word has length 572 [2018-10-14 16:39:35,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:39:35,369 INFO L481 AbstractCegarLoop]: Abstraction has 589 states and 590 transitions. [2018-10-14 16:39:35,369 INFO L482 AbstractCegarLoop]: Interpolant automaton has 77 states. [2018-10-14 16:39:35,369 INFO L276 IsEmpty]: Start isEmpty. Operand 589 states and 590 transitions. [2018-10-14 16:39:35,373 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 589 [2018-10-14 16:39:35,373 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:39:35,373 INFO L375 BasicCegarLoop]: trace histogram [19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:39:35,374 INFO L424 AbstractCegarLoop]: === Iteration 39 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:39:35,374 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:39:35,374 INFO L82 PathProgramCache]: Analyzing trace with hash 1417188004, now seen corresponding path program 36 times [2018-10-14 16:39:35,375 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:39:35,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:39:38,087 INFO L134 CoverageAnalysis]: Checked inductivity of 4969 backedges. 2312 proven. 2657 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:39:38,088 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:39:38,088 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-14 16:39:38,088 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-14 16:39:38,089 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-14 16:39:38,089 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=708, Invalid=5772, Unknown=0, NotChecked=0, Total=6480 [2018-10-14 16:39:38,089 INFO L87 Difference]: Start difference. First operand 589 states and 590 transitions. Second operand 81 states. [2018-10-14 16:39:51,733 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:39:51,733 INFO L93 Difference]: Finished difference Result 623 states and 624 transitions. [2018-10-14 16:39:51,733 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 133 states. [2018-10-14 16:39:51,733 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 588 [2018-10-14 16:39:51,734 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:39:51,735 INFO L225 Difference]: With dead ends: 623 [2018-10-14 16:39:51,735 INFO L226 Difference]: Without dead ends: 623 [2018-10-14 16:39:51,736 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 191 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9935 ImplicationChecksByTransitivity, 10.1s TimeCoverageRelationStatistics Valid=6323, Invalid=30733, Unknown=0, NotChecked=0, Total=37056 [2018-10-14 16:39:51,737 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 623 states. [2018-10-14 16:39:51,740 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 623 to 603. [2018-10-14 16:39:51,740 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 603 states. [2018-10-14 16:39:51,741 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 603 states to 603 states and 604 transitions. [2018-10-14 16:39:51,741 INFO L78 Accepts]: Start accepts. Automaton has 603 states and 604 transitions. Word has length 588 [2018-10-14 16:39:51,741 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:39:51,742 INFO L481 AbstractCegarLoop]: Abstraction has 603 states and 604 transitions. [2018-10-14 16:39:51,742 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-14 16:39:51,742 INFO L276 IsEmpty]: Start isEmpty. Operand 603 states and 604 transitions. [2018-10-14 16:39:51,744 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 603 [2018-10-14 16:39:51,744 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:39:51,745 INFO L375 BasicCegarLoop]: trace histogram [20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:39:51,745 INFO L424 AbstractCegarLoop]: === Iteration 40 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:39:51,745 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:39:51,745 INFO L82 PathProgramCache]: Analyzing trace with hash 1035400024, now seen corresponding path program 37 times [2018-10-14 16:39:51,746 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:39:51,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:39:54,124 INFO L134 CoverageAnalysis]: Checked inductivity of 5225 backedges. 2235 proven. 2990 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:39:54,125 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:39:54,125 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [81] total 81 [2018-10-14 16:39:54,125 INFO L460 AbstractCegarLoop]: Interpolant automaton has 81 states [2018-10-14 16:39:54,126 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 81 interpolants. [2018-10-14 16:39:54,126 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=846, Invalid=5634, Unknown=0, NotChecked=0, Total=6480 [2018-10-14 16:39:54,126 INFO L87 Difference]: Start difference. First operand 603 states and 604 transitions. Second operand 81 states. [2018-10-14 16:39:59,921 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:39:59,921 INFO L93 Difference]: Finished difference Result 901 states and 902 transitions. [2018-10-14 16:39:59,922 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 119 states. [2018-10-14 16:39:59,922 INFO L78 Accepts]: Start accepts. Automaton has 81 states. Word has length 602 [2018-10-14 16:39:59,923 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:39:59,924 INFO L225 Difference]: With dead ends: 901 [2018-10-14 16:39:59,924 INFO L226 Difference]: Without dead ends: 633 [2018-10-14 16:39:59,926 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 176 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8544 ImplicationChecksByTransitivity, 5.0s TimeCoverageRelationStatistics Valid=4758, Invalid=26748, Unknown=0, NotChecked=0, Total=31506 [2018-10-14 16:39:59,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 633 states. [2018-10-14 16:39:59,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 633 to 619. [2018-10-14 16:39:59,929 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 619 states. [2018-10-14 16:39:59,930 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 619 states to 619 states and 620 transitions. [2018-10-14 16:39:59,930 INFO L78 Accepts]: Start accepts. Automaton has 619 states and 620 transitions. Word has length 602 [2018-10-14 16:39:59,931 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:39:59,931 INFO L481 AbstractCegarLoop]: Abstraction has 619 states and 620 transitions. [2018-10-14 16:39:59,931 INFO L482 AbstractCegarLoop]: Interpolant automaton has 81 states. [2018-10-14 16:39:59,931 INFO L276 IsEmpty]: Start isEmpty. Operand 619 states and 620 transitions. [2018-10-14 16:39:59,934 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 619 [2018-10-14 16:39:59,935 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:39:59,935 INFO L375 BasicCegarLoop]: trace histogram [20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:39:59,935 INFO L424 AbstractCegarLoop]: === Iteration 41 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:39:59,935 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:39:59,936 INFO L82 PathProgramCache]: Analyzing trace with hash 320117328, now seen corresponding path program 38 times [2018-10-14 16:39:59,936 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:39:59,975 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:40:03,041 INFO L134 CoverageAnalysis]: Checked inductivity of 5530 backedges. 2592 proven. 2938 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:40:03,041 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:40:03,041 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-14 16:40:03,042 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-14 16:40:03,042 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-14 16:40:03,042 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=751, Invalid=6389, Unknown=0, NotChecked=0, Total=7140 [2018-10-14 16:40:03,042 INFO L87 Difference]: Start difference. First operand 619 states and 620 transitions. Second operand 85 states. [2018-10-14 16:40:18,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:40:18,101 INFO L93 Difference]: Finished difference Result 653 states and 654 transitions. [2018-10-14 16:40:18,101 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 139 states. [2018-10-14 16:40:18,101 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 618 [2018-10-14 16:40:18,102 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:40:18,103 INFO L225 Difference]: With dead ends: 653 [2018-10-14 16:40:18,104 INFO L226 Difference]: Without dead ends: 653 [2018-10-14 16:40:18,105 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 206 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 200 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10877 ImplicationChecksByTransitivity, 11.6s TimeCoverageRelationStatistics Valid=6749, Invalid=33853, Unknown=0, NotChecked=0, Total=40602 [2018-10-14 16:40:18,105 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 653 states. [2018-10-14 16:40:18,108 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 653 to 633. [2018-10-14 16:40:18,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 633 states. [2018-10-14 16:40:18,109 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 633 states to 633 states and 634 transitions. [2018-10-14 16:40:18,109 INFO L78 Accepts]: Start accepts. Automaton has 633 states and 634 transitions. Word has length 618 [2018-10-14 16:40:18,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:40:18,110 INFO L481 AbstractCegarLoop]: Abstraction has 633 states and 634 transitions. [2018-10-14 16:40:18,110 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-14 16:40:18,110 INFO L276 IsEmpty]: Start isEmpty. Operand 633 states and 634 transitions. [2018-10-14 16:40:18,113 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 633 [2018-10-14 16:40:18,113 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:40:18,113 INFO L375 BasicCegarLoop]: trace histogram [21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:40:18,114 INFO L424 AbstractCegarLoop]: === Iteration 42 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:40:18,114 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:40:18,114 INFO L82 PathProgramCache]: Analyzing trace with hash -1700389372, now seen corresponding path program 39 times [2018-10-14 16:40:18,115 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:40:18,148 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:40:20,968 INFO L134 CoverageAnalysis]: Checked inductivity of 5800 backedges. 2492 proven. 3308 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:40:20,969 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:40:20,969 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [85] total 85 [2018-10-14 16:40:20,969 INFO L460 AbstractCegarLoop]: Interpolant automaton has 85 states [2018-10-14 16:40:20,970 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 85 interpolants. [2018-10-14 16:40:20,970 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=930, Invalid=6210, Unknown=0, NotChecked=0, Total=7140 [2018-10-14 16:40:20,970 INFO L87 Difference]: Start difference. First operand 633 states and 634 transitions. Second operand 85 states. [2018-10-14 16:40:27,129 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:40:27,130 INFO L93 Difference]: Finished difference Result 945 states and 946 transitions. [2018-10-14 16:40:27,130 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 125 states. [2018-10-14 16:40:27,130 INFO L78 Accepts]: Start accepts. Automaton has 85 states. Word has length 632 [2018-10-14 16:40:27,131 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:40:27,133 INFO L225 Difference]: With dead ends: 945 [2018-10-14 16:40:27,133 INFO L226 Difference]: Without dead ends: 663 [2018-10-14 16:40:27,134 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9464 ImplicationChecksByTransitivity, 5.6s TimeCoverageRelationStatistics Valid=5247, Invalid=29535, Unknown=0, NotChecked=0, Total=34782 [2018-10-14 16:40:27,134 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 663 states. [2018-10-14 16:40:27,137 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 663 to 649. [2018-10-14 16:40:27,138 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 649 states. [2018-10-14 16:40:27,138 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 649 states to 649 states and 650 transitions. [2018-10-14 16:40:27,138 INFO L78 Accepts]: Start accepts. Automaton has 649 states and 650 transitions. Word has length 632 [2018-10-14 16:40:27,139 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:40:27,139 INFO L481 AbstractCegarLoop]: Abstraction has 649 states and 650 transitions. [2018-10-14 16:40:27,139 INFO L482 AbstractCegarLoop]: Interpolant automaton has 85 states. [2018-10-14 16:40:27,139 INFO L276 IsEmpty]: Start isEmpty. Operand 649 states and 650 transitions. [2018-10-14 16:40:27,143 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 649 [2018-10-14 16:40:27,143 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:40:27,143 INFO L375 BasicCegarLoop]: trace histogram [21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:40:27,144 INFO L424 AbstractCegarLoop]: === Iteration 43 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:40:27,144 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:40:27,144 INFO L82 PathProgramCache]: Analyzing trace with hash -1566620932, now seen corresponding path program 40 times [2018-10-14 16:40:27,145 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:40:27,183 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:40:30,479 INFO L134 CoverageAnalysis]: Checked inductivity of 6121 backedges. 2888 proven. 3233 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:40:30,480 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:40:30,480 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-14 16:40:30,481 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-14 16:40:30,481 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-14 16:40:30,481 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=684, Invalid=7148, Unknown=0, NotChecked=0, Total=7832 [2018-10-14 16:40:30,482 INFO L87 Difference]: Start difference. First operand 649 states and 650 transitions. Second operand 89 states. [2018-10-14 16:40:42,332 WARN L179 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-14 16:40:42,517 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-14 16:40:42,678 WARN L179 SmtUtils]: Spent 100.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 35 [2018-10-14 16:40:43,027 WARN L179 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-14 16:40:43,200 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-14 16:40:43,614 WARN L179 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-14 16:40:43,801 WARN L179 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 43 [2018-10-14 16:40:44,216 WARN L179 SmtUtils]: Spent 110.00 ms on a formula simplification. DAG size of input: 99 DAG size of output: 42 [2018-10-14 16:40:44,405 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 43 [2018-10-14 16:40:44,837 WARN L179 SmtUtils]: Spent 106.00 ms on a formula simplification. DAG size of input: 94 DAG size of output: 42 [2018-10-14 16:40:45,029 WARN L179 SmtUtils]: Spent 104.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 42 [2018-10-14 16:40:45,563 WARN L179 SmtUtils]: Spent 116.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 41 [2018-10-14 16:40:48,339 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:40:48,339 INFO L93 Difference]: Finished difference Result 683 states and 684 transitions. [2018-10-14 16:40:48,339 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 141 states. [2018-10-14 16:40:48,339 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 648 [2018-10-14 16:40:48,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:40:48,342 INFO L225 Difference]: With dead ends: 683 [2018-10-14 16:40:48,342 INFO L226 Difference]: Without dead ends: 683 [2018-10-14 16:40:48,344 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 205 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11140 ImplicationChecksByTransitivity, 12.5s TimeCoverageRelationStatistics Valid=6198, Invalid=36444, Unknown=0, NotChecked=0, Total=42642 [2018-10-14 16:40:48,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 683 states. [2018-10-14 16:40:48,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 683 to 663. [2018-10-14 16:40:48,348 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 663 states. [2018-10-14 16:40:48,349 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 663 states to 663 states and 664 transitions. [2018-10-14 16:40:48,349 INFO L78 Accepts]: Start accepts. Automaton has 663 states and 664 transitions. Word has length 648 [2018-10-14 16:40:48,350 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:40:48,350 INFO L481 AbstractCegarLoop]: Abstraction has 663 states and 664 transitions. [2018-10-14 16:40:48,350 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-14 16:40:48,350 INFO L276 IsEmpty]: Start isEmpty. Operand 663 states and 664 transitions. [2018-10-14 16:40:48,353 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 663 [2018-10-14 16:40:48,353 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:40:48,354 INFO L375 BasicCegarLoop]: trace histogram [22, 22, 22, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:40:48,354 INFO L424 AbstractCegarLoop]: === Iteration 44 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:40:48,354 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:40:48,354 INFO L82 PathProgramCache]: Analyzing trace with hash -1915344464, now seen corresponding path program 41 times [2018-10-14 16:40:48,355 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:40:48,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:40:51,296 INFO L134 CoverageAnalysis]: Checked inductivity of 6405 backedges. 2763 proven. 3642 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:40:51,296 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:40:51,296 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [89] total 89 [2018-10-14 16:40:51,297 INFO L460 AbstractCegarLoop]: Interpolant automaton has 89 states [2018-10-14 16:40:51,297 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 89 interpolants. [2018-10-14 16:40:51,298 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1018, Invalid=6814, Unknown=0, NotChecked=0, Total=7832 [2018-10-14 16:40:51,298 INFO L87 Difference]: Start difference. First operand 663 states and 664 transitions. Second operand 89 states. [2018-10-14 16:40:57,703 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:40:57,704 INFO L93 Difference]: Finished difference Result 989 states and 990 transitions. [2018-10-14 16:40:57,704 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 131 states. [2018-10-14 16:40:57,704 INFO L78 Accepts]: Start accepts. Automaton has 89 states. Word has length 662 [2018-10-14 16:40:57,705 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:40:57,707 INFO L225 Difference]: With dead ends: 989 [2018-10-14 16:40:57,707 INFO L226 Difference]: Without dead ends: 693 [2018-10-14 16:40:57,708 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 196 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 194 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10431 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=5760, Invalid=32460, Unknown=0, NotChecked=0, Total=38220 [2018-10-14 16:40:57,708 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 693 states. [2018-10-14 16:40:57,713 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 693 to 679. [2018-10-14 16:40:57,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 679 states. [2018-10-14 16:40:57,714 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 679 states to 679 states and 680 transitions. [2018-10-14 16:40:57,714 INFO L78 Accepts]: Start accepts. Automaton has 679 states and 680 transitions. Word has length 662 [2018-10-14 16:40:57,714 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:40:57,714 INFO L481 AbstractCegarLoop]: Abstraction has 679 states and 680 transitions. [2018-10-14 16:40:57,715 INFO L482 AbstractCegarLoop]: Interpolant automaton has 89 states. [2018-10-14 16:40:57,715 INFO L276 IsEmpty]: Start isEmpty. Operand 679 states and 680 transitions. [2018-10-14 16:40:57,718 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 679 [2018-10-14 16:40:57,718 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:40:57,718 INFO L375 BasicCegarLoop]: trace histogram [22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:40:57,718 INFO L424 AbstractCegarLoop]: === Iteration 45 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:40:57,718 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:40:57,719 INFO L82 PathProgramCache]: Analyzing trace with hash 431639720, now seen corresponding path program 42 times [2018-10-14 16:40:57,719 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:40:57,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:41:01,345 INFO L134 CoverageAnalysis]: Checked inductivity of 6742 backedges. 3200 proven. 3542 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:41:01,346 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:41:01,346 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-14 16:41:01,346 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-14 16:41:01,347 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-14 16:41:01,347 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=987, Invalid=7569, Unknown=0, NotChecked=0, Total=8556 [2018-10-14 16:41:01,347 INFO L87 Difference]: Start difference. First operand 679 states and 680 transitions. Second operand 93 states. [2018-10-14 16:41:13,559 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:41:13,560 INFO L93 Difference]: Finished difference Result 713 states and 714 transitions. [2018-10-14 16:41:13,560 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 156 states. [2018-10-14 16:41:13,560 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 678 [2018-10-14 16:41:13,560 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:41:13,562 INFO L225 Difference]: With dead ends: 713 [2018-10-14 16:41:13,562 INFO L226 Difference]: Without dead ends: 713 [2018-10-14 16:41:13,564 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 229 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 223 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13786 ImplicationChecksByTransitivity, 12.4s TimeCoverageRelationStatistics Valid=8814, Invalid=41586, Unknown=0, NotChecked=0, Total=50400 [2018-10-14 16:41:13,564 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 713 states. [2018-10-14 16:41:13,568 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 713 to 693. [2018-10-14 16:41:13,568 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 693 states. [2018-10-14 16:41:13,569 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 693 states to 693 states and 694 transitions. [2018-10-14 16:41:13,569 INFO L78 Accepts]: Start accepts. Automaton has 693 states and 694 transitions. Word has length 678 [2018-10-14 16:41:13,569 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:41:13,569 INFO L481 AbstractCegarLoop]: Abstraction has 693 states and 694 transitions. [2018-10-14 16:41:13,569 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-14 16:41:13,569 INFO L276 IsEmpty]: Start isEmpty. Operand 693 states and 694 transitions. [2018-10-14 16:41:13,572 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 693 [2018-10-14 16:41:13,573 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:41:13,573 INFO L375 BasicCegarLoop]: trace histogram [23, 23, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:41:13,573 INFO L424 AbstractCegarLoop]: === Iteration 46 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:41:13,573 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:41:13,573 INFO L82 PathProgramCache]: Analyzing trace with hash 265868892, now seen corresponding path program 43 times [2018-10-14 16:41:13,574 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:41:13,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:41:16,324 INFO L134 CoverageAnalysis]: Checked inductivity of 7040 backedges. 3048 proven. 3992 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:41:16,325 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:41:16,325 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [93] total 93 [2018-10-14 16:41:16,326 INFO L460 AbstractCegarLoop]: Interpolant automaton has 93 states [2018-10-14 16:41:16,326 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 93 interpolants. [2018-10-14 16:41:16,326 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1110, Invalid=7446, Unknown=0, NotChecked=0, Total=8556 [2018-10-14 16:41:16,326 INFO L87 Difference]: Start difference. First operand 693 states and 694 transitions. Second operand 93 states. [2018-10-14 16:41:23,544 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:41:23,545 INFO L93 Difference]: Finished difference Result 1033 states and 1034 transitions. [2018-10-14 16:41:23,545 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 137 states. [2018-10-14 16:41:23,545 INFO L78 Accepts]: Start accepts. Automaton has 93 states. Word has length 692 [2018-10-14 16:41:23,546 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:41:23,548 INFO L225 Difference]: With dead ends: 1033 [2018-10-14 16:41:23,548 INFO L226 Difference]: Without dead ends: 723 [2018-10-14 16:41:23,550 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 203 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11445 ImplicationChecksByTransitivity, 6.1s TimeCoverageRelationStatistics Valid=6297, Invalid=35523, Unknown=0, NotChecked=0, Total=41820 [2018-10-14 16:41:23,550 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 723 states. [2018-10-14 16:41:23,553 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 723 to 709. [2018-10-14 16:41:23,554 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 709 states. [2018-10-14 16:41:23,554 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 709 states to 709 states and 710 transitions. [2018-10-14 16:41:23,555 INFO L78 Accepts]: Start accepts. Automaton has 709 states and 710 transitions. Word has length 692 [2018-10-14 16:41:23,555 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:41:23,555 INFO L481 AbstractCegarLoop]: Abstraction has 709 states and 710 transitions. [2018-10-14 16:41:23,555 INFO L482 AbstractCegarLoop]: Interpolant automaton has 93 states. [2018-10-14 16:41:23,555 INFO L276 IsEmpty]: Start isEmpty. Operand 709 states and 710 transitions. [2018-10-14 16:41:23,558 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 709 [2018-10-14 16:41:23,558 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:41:23,559 INFO L375 BasicCegarLoop]: trace histogram [23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:41:23,559 INFO L424 AbstractCegarLoop]: === Iteration 47 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:41:23,559 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:41:23,559 INFO L82 PathProgramCache]: Analyzing trace with hash -522750124, now seen corresponding path program 44 times [2018-10-14 16:41:23,560 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:41:23,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:41:27,741 INFO L134 CoverageAnalysis]: Checked inductivity of 7393 backedges. 3528 proven. 3865 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:41:27,742 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:41:27,742 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-14 16:41:27,742 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-14 16:41:27,743 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-14 16:41:27,743 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1036, Invalid=8276, Unknown=0, NotChecked=0, Total=9312 [2018-10-14 16:41:27,743 INFO L87 Difference]: Start difference. First operand 709 states and 710 transitions. Second operand 97 states. [2018-10-14 16:41:46,045 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:41:46,045 INFO L93 Difference]: Finished difference Result 743 states and 744 transitions. [2018-10-14 16:41:46,045 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-14 16:41:46,045 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 708 [2018-10-14 16:41:46,046 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:41:46,048 INFO L225 Difference]: With dead ends: 743 [2018-10-14 16:41:46,048 INFO L226 Difference]: Without dead ends: 743 [2018-10-14 16:41:46,049 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 237 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 231 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14741 ImplicationChecksByTransitivity, 14.0s TimeCoverageRelationStatistics Valid=9261, Invalid=44795, Unknown=0, NotChecked=0, Total=54056 [2018-10-14 16:41:46,050 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 743 states. [2018-10-14 16:41:46,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 743 to 723. [2018-10-14 16:41:46,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 723 states. [2018-10-14 16:41:46,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 723 states to 723 states and 724 transitions. [2018-10-14 16:41:46,056 INFO L78 Accepts]: Start accepts. Automaton has 723 states and 724 transitions. Word has length 708 [2018-10-14 16:41:46,057 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:41:46,057 INFO L481 AbstractCegarLoop]: Abstraction has 723 states and 724 transitions. [2018-10-14 16:41:46,057 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-14 16:41:46,057 INFO L276 IsEmpty]: Start isEmpty. Operand 723 states and 724 transitions. [2018-10-14 16:41:46,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 723 [2018-10-14 16:41:46,061 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:41:46,061 INFO L375 BasicCegarLoop]: trace histogram [24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:41:46,061 INFO L424 AbstractCegarLoop]: === Iteration 48 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:41:46,061 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:41:46,062 INFO L82 PathProgramCache]: Analyzing trace with hash -15735800, now seen corresponding path program 45 times [2018-10-14 16:41:46,062 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:41:46,097 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:41:49,251 INFO L134 CoverageAnalysis]: Checked inductivity of 7705 backedges. 3347 proven. 4358 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:41:49,251 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:41:49,251 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [97] total 97 [2018-10-14 16:41:49,252 INFO L460 AbstractCegarLoop]: Interpolant automaton has 97 states [2018-10-14 16:41:49,252 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 97 interpolants. [2018-10-14 16:41:49,252 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1206, Invalid=8106, Unknown=0, NotChecked=0, Total=9312 [2018-10-14 16:41:49,253 INFO L87 Difference]: Start difference. First operand 723 states and 724 transitions. Second operand 97 states. [2018-10-14 16:41:57,336 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:41:57,336 INFO L93 Difference]: Finished difference Result 1077 states and 1078 transitions. [2018-10-14 16:41:57,336 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 143 states. [2018-10-14 16:41:57,336 INFO L78 Accepts]: Start accepts. Automaton has 97 states. Word has length 722 [2018-10-14 16:41:57,337 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:41:57,340 INFO L225 Difference]: With dead ends: 1077 [2018-10-14 16:41:57,340 INFO L226 Difference]: Without dead ends: 753 [2018-10-14 16:41:57,341 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 214 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 212 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12506 ImplicationChecksByTransitivity, 6.9s TimeCoverageRelationStatistics Valid=6858, Invalid=38724, Unknown=0, NotChecked=0, Total=45582 [2018-10-14 16:41:57,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 753 states. [2018-10-14 16:41:57,345 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 753 to 739. [2018-10-14 16:41:57,345 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 739 states. [2018-10-14 16:41:57,346 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 739 states to 739 states and 740 transitions. [2018-10-14 16:41:57,346 INFO L78 Accepts]: Start accepts. Automaton has 739 states and 740 transitions. Word has length 722 [2018-10-14 16:41:57,347 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:41:57,347 INFO L481 AbstractCegarLoop]: Abstraction has 739 states and 740 transitions. [2018-10-14 16:41:57,347 INFO L482 AbstractCegarLoop]: Interpolant automaton has 97 states. [2018-10-14 16:41:57,347 INFO L276 IsEmpty]: Start isEmpty. Operand 739 states and 740 transitions. [2018-10-14 16:41:57,350 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 739 [2018-10-14 16:41:57,351 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:41:57,351 INFO L375 BasicCegarLoop]: trace histogram [24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:41:57,351 INFO L424 AbstractCegarLoop]: === Iteration 49 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:41:57,351 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:41:57,351 INFO L82 PathProgramCache]: Analyzing trace with hash 1043890944, now seen corresponding path program 46 times [2018-10-14 16:41:57,352 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:41:57,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:42:01,352 INFO L134 CoverageAnalysis]: Checked inductivity of 8074 backedges. 3872 proven. 4202 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:42:01,352 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:42:01,352 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-14 16:42:01,353 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-14 16:42:01,353 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-14 16:42:01,353 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1087, Invalid=9013, Unknown=0, NotChecked=0, Total=10100 [2018-10-14 16:42:01,353 INFO L87 Difference]: Start difference. First operand 739 states and 740 transitions. Second operand 101 states. [2018-10-14 16:42:14,079 WARN L179 SmtUtils]: Spent 103.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 42 [2018-10-14 16:42:17,161 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:42:17,161 INFO L93 Difference]: Finished difference Result 773 states and 774 transitions. [2018-10-14 16:42:17,162 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-14 16:42:17,162 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 738 [2018-10-14 16:42:17,162 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:42:17,164 INFO L225 Difference]: With dead ends: 773 [2018-10-14 16:42:17,164 INFO L226 Difference]: Without dead ends: 773 [2018-10-14 16:42:17,167 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 246 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 240 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15883 ImplicationChecksByTransitivity, 15.3s TimeCoverageRelationStatistics Valid=9775, Invalid=48547, Unknown=0, NotChecked=0, Total=58322 [2018-10-14 16:42:17,168 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 773 states. [2018-10-14 16:42:17,172 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 773 to 753. [2018-10-14 16:42:17,173 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 753 states. [2018-10-14 16:42:17,174 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 753 states to 753 states and 754 transitions. [2018-10-14 16:42:17,174 INFO L78 Accepts]: Start accepts. Automaton has 753 states and 754 transitions. Word has length 738 [2018-10-14 16:42:17,175 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:42:17,175 INFO L481 AbstractCegarLoop]: Abstraction has 753 states and 754 transitions. [2018-10-14 16:42:17,175 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-14 16:42:17,175 INFO L276 IsEmpty]: Start isEmpty. Operand 753 states and 754 transitions. [2018-10-14 16:42:17,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 753 [2018-10-14 16:42:17,179 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:42:17,179 INFO L375 BasicCegarLoop]: trace histogram [25, 25, 25, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:42:17,180 INFO L424 AbstractCegarLoop]: === Iteration 50 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:42:17,180 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:42:17,180 INFO L82 PathProgramCache]: Analyzing trace with hash -1414720844, now seen corresponding path program 47 times [2018-10-14 16:42:17,180 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:42:17,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:42:20,660 INFO L134 CoverageAnalysis]: Checked inductivity of 8400 backedges. 3660 proven. 4740 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:42:20,661 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:42:20,661 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [101] total 101 [2018-10-14 16:42:20,662 INFO L460 AbstractCegarLoop]: Interpolant automaton has 101 states [2018-10-14 16:42:20,662 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 101 interpolants. [2018-10-14 16:42:20,662 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1306, Invalid=8794, Unknown=0, NotChecked=0, Total=10100 [2018-10-14 16:42:20,663 INFO L87 Difference]: Start difference. First operand 753 states and 754 transitions. Second operand 101 states. [2018-10-14 16:42:29,412 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:42:29,412 INFO L93 Difference]: Finished difference Result 1121 states and 1122 transitions. [2018-10-14 16:42:29,412 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 149 states. [2018-10-14 16:42:29,412 INFO L78 Accepts]: Start accepts. Automaton has 101 states. Word has length 752 [2018-10-14 16:42:29,413 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:42:29,416 INFO L225 Difference]: With dead ends: 1121 [2018-10-14 16:42:29,416 INFO L226 Difference]: Without dead ends: 783 [2018-10-14 16:42:29,418 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 223 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 221 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13614 ImplicationChecksByTransitivity, 7.5s TimeCoverageRelationStatistics Valid=7443, Invalid=42063, Unknown=0, NotChecked=0, Total=49506 [2018-10-14 16:42:29,419 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 783 states. [2018-10-14 16:42:29,424 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 783 to 769. [2018-10-14 16:42:29,424 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 769 states. [2018-10-14 16:42:29,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 769 states to 769 states and 770 transitions. [2018-10-14 16:42:29,425 INFO L78 Accepts]: Start accepts. Automaton has 769 states and 770 transitions. Word has length 752 [2018-10-14 16:42:29,426 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:42:29,426 INFO L481 AbstractCegarLoop]: Abstraction has 769 states and 770 transitions. [2018-10-14 16:42:29,426 INFO L482 AbstractCegarLoop]: Interpolant automaton has 101 states. [2018-10-14 16:42:29,426 INFO L276 IsEmpty]: Start isEmpty. Operand 769 states and 770 transitions. [2018-10-14 16:42:29,430 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 769 [2018-10-14 16:42:29,430 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:42:29,430 INFO L375 BasicCegarLoop]: trace histogram [25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:42:29,430 INFO L424 AbstractCegarLoop]: === Iteration 51 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:42:29,430 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:42:29,431 INFO L82 PathProgramCache]: Analyzing trace with hash -504418388, now seen corresponding path program 48 times [2018-10-14 16:42:29,431 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:42:29,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:42:33,709 INFO L134 CoverageAnalysis]: Checked inductivity of 8785 backedges. 4232 proven. 4553 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:42:33,710 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:42:33,710 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-14 16:42:33,710 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-14 16:42:33,711 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-14 16:42:33,711 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1140, Invalid=9780, Unknown=0, NotChecked=0, Total=10920 [2018-10-14 16:42:33,711 INFO L87 Difference]: Start difference. First operand 769 states and 770 transitions. Second operand 105 states. [2018-10-14 16:42:49,372 WARN L179 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 42 [2018-10-14 16:42:52,300 WARN L179 SmtUtils]: Spent 101.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 42 [2018-10-14 16:42:55,477 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:42:55,477 INFO L93 Difference]: Finished difference Result 803 states and 804 transitions. [2018-10-14 16:42:55,477 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 173 states. [2018-10-14 16:42:55,477 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 768 [2018-10-14 16:42:55,478 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:42:55,480 INFO L225 Difference]: With dead ends: 803 [2018-10-14 16:42:55,480 INFO L226 Difference]: Without dead ends: 803 [2018-10-14 16:42:55,482 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 255 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 249 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17066 ImplicationChecksByTransitivity, 16.3s TimeCoverageRelationStatistics Valid=10304, Invalid=52446, Unknown=0, NotChecked=0, Total=62750 [2018-10-14 16:42:55,483 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 803 states. [2018-10-14 16:42:55,487 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 803 to 783. [2018-10-14 16:42:55,487 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 783 states. [2018-10-14 16:42:55,488 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 783 states to 783 states and 784 transitions. [2018-10-14 16:42:55,488 INFO L78 Accepts]: Start accepts. Automaton has 783 states and 784 transitions. Word has length 768 [2018-10-14 16:42:55,488 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:42:55,488 INFO L481 AbstractCegarLoop]: Abstraction has 783 states and 784 transitions. [2018-10-14 16:42:55,488 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-14 16:42:55,489 INFO L276 IsEmpty]: Start isEmpty. Operand 783 states and 784 transitions. [2018-10-14 16:42:55,493 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 783 [2018-10-14 16:42:55,493 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:42:55,493 INFO L375 BasicCegarLoop]: trace histogram [26, 26, 26, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:42:55,494 INFO L424 AbstractCegarLoop]: === Iteration 52 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:42:55,494 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:42:55,494 INFO L82 PathProgramCache]: Analyzing trace with hash 1672618592, now seen corresponding path program 49 times [2018-10-14 16:42:55,494 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:42:55,540 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:42:58,881 INFO L134 CoverageAnalysis]: Checked inductivity of 9125 backedges. 3987 proven. 5138 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:42:58,881 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:42:58,882 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [105] total 105 [2018-10-14 16:42:58,882 INFO L460 AbstractCegarLoop]: Interpolant automaton has 105 states [2018-10-14 16:42:58,882 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 105 interpolants. [2018-10-14 16:42:58,883 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1410, Invalid=9510, Unknown=0, NotChecked=0, Total=10920 [2018-10-14 16:42:58,883 INFO L87 Difference]: Start difference. First operand 783 states and 784 transitions. Second operand 105 states. [2018-10-14 16:43:07,871 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:43:07,872 INFO L93 Difference]: Finished difference Result 1165 states and 1166 transitions. [2018-10-14 16:43:07,872 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 155 states. [2018-10-14 16:43:07,872 INFO L78 Accepts]: Start accepts. Automaton has 105 states. Word has length 782 [2018-10-14 16:43:07,873 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:43:07,875 INFO L225 Difference]: With dead ends: 1165 [2018-10-14 16:43:07,875 INFO L226 Difference]: Without dead ends: 813 [2018-10-14 16:43:07,877 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 232 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 230 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14769 ImplicationChecksByTransitivity, 7.5s TimeCoverageRelationStatistics Valid=8052, Invalid=45540, Unknown=0, NotChecked=0, Total=53592 [2018-10-14 16:43:07,877 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 813 states. [2018-10-14 16:43:07,882 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 813 to 799. [2018-10-14 16:43:07,882 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 799 states. [2018-10-14 16:43:07,882 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 799 states to 799 states and 800 transitions. [2018-10-14 16:43:07,883 INFO L78 Accepts]: Start accepts. Automaton has 799 states and 800 transitions. Word has length 782 [2018-10-14 16:43:07,883 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:43:07,883 INFO L481 AbstractCegarLoop]: Abstraction has 799 states and 800 transitions. [2018-10-14 16:43:07,883 INFO L482 AbstractCegarLoop]: Interpolant automaton has 105 states. [2018-10-14 16:43:07,883 INFO L276 IsEmpty]: Start isEmpty. Operand 799 states and 800 transitions. [2018-10-14 16:43:07,887 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 799 [2018-10-14 16:43:07,887 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:43:07,888 INFO L375 BasicCegarLoop]: trace histogram [26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:43:07,888 INFO L424 AbstractCegarLoop]: === Iteration 53 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:43:07,888 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:43:07,888 INFO L82 PathProgramCache]: Analyzing trace with hash 1910324568, now seen corresponding path program 50 times [2018-10-14 16:43:07,889 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:43:07,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:43:12,614 INFO L134 CoverageAnalysis]: Checked inductivity of 9526 backedges. 4608 proven. 4918 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:43:12,615 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:43:12,615 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-14 16:43:12,616 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-14 16:43:12,616 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-14 16:43:12,616 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1371, Invalid=10401, Unknown=0, NotChecked=0, Total=11772 [2018-10-14 16:43:12,616 INFO L87 Difference]: Start difference. First operand 799 states and 800 transitions. Second operand 109 states. [2018-10-14 16:43:30,259 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:43:30,259 INFO L93 Difference]: Finished difference Result 833 states and 834 transitions. [2018-10-14 16:43:30,260 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 184 states. [2018-10-14 16:43:30,260 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 798 [2018-10-14 16:43:30,260 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:43:30,262 INFO L225 Difference]: With dead ends: 833 [2018-10-14 16:43:30,262 INFO L226 Difference]: Without dead ends: 833 [2018-10-14 16:43:30,264 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 269 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 263 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19364 ImplicationChecksByTransitivity, 16.4s TimeCoverageRelationStatistics Valid=12232, Invalid=57728, Unknown=0, NotChecked=0, Total=69960 [2018-10-14 16:43:30,264 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 833 states. [2018-10-14 16:43:30,268 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 833 to 813. [2018-10-14 16:43:30,269 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 813 states. [2018-10-14 16:43:30,269 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 813 states to 813 states and 814 transitions. [2018-10-14 16:43:30,269 INFO L78 Accepts]: Start accepts. Automaton has 813 states and 814 transitions. Word has length 798 [2018-10-14 16:43:30,270 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:43:30,270 INFO L481 AbstractCegarLoop]: Abstraction has 813 states and 814 transitions. [2018-10-14 16:43:30,270 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-14 16:43:30,270 INFO L276 IsEmpty]: Start isEmpty. Operand 813 states and 814 transitions. [2018-10-14 16:43:30,274 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 813 [2018-10-14 16:43:30,274 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:43:30,275 INFO L375 BasicCegarLoop]: trace histogram [27, 27, 27, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:43:30,275 INFO L424 AbstractCegarLoop]: === Iteration 54 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:43:30,275 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:43:30,275 INFO L82 PathProgramCache]: Analyzing trace with hash -17771764, now seen corresponding path program 51 times [2018-10-14 16:43:30,276 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:43:30,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:43:34,209 INFO L134 CoverageAnalysis]: Checked inductivity of 9880 backedges. 4328 proven. 5552 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:43:34,209 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:43:34,210 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [109] total 109 [2018-10-14 16:43:34,210 INFO L460 AbstractCegarLoop]: Interpolant automaton has 109 states [2018-10-14 16:43:34,210 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 109 interpolants. [2018-10-14 16:43:34,211 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1518, Invalid=10254, Unknown=0, NotChecked=0, Total=11772 [2018-10-14 16:43:34,211 INFO L87 Difference]: Start difference. First operand 813 states and 814 transitions. Second operand 109 states. [2018-10-14 16:43:44,158 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:43:44,158 INFO L93 Difference]: Finished difference Result 1209 states and 1210 transitions. [2018-10-14 16:43:44,159 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 161 states. [2018-10-14 16:43:44,159 INFO L78 Accepts]: Start accepts. Automaton has 109 states. Word has length 812 [2018-10-14 16:43:44,160 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:43:44,162 INFO L225 Difference]: With dead ends: 1209 [2018-10-14 16:43:44,162 INFO L226 Difference]: Without dead ends: 843 [2018-10-14 16:43:44,163 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 239 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15971 ImplicationChecksByTransitivity, 8.3s TimeCoverageRelationStatistics Valid=8685, Invalid=49155, Unknown=0, NotChecked=0, Total=57840 [2018-10-14 16:43:44,164 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 843 states. [2018-10-14 16:43:44,168 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 843 to 829. [2018-10-14 16:43:44,168 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 829 states. [2018-10-14 16:43:44,168 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 829 states to 829 states and 830 transitions. [2018-10-14 16:43:44,169 INFO L78 Accepts]: Start accepts. Automaton has 829 states and 830 transitions. Word has length 812 [2018-10-14 16:43:44,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:43:44,169 INFO L481 AbstractCegarLoop]: Abstraction has 829 states and 830 transitions. [2018-10-14 16:43:44,169 INFO L482 AbstractCegarLoop]: Interpolant automaton has 109 states. [2018-10-14 16:43:44,169 INFO L276 IsEmpty]: Start isEmpty. Operand 829 states and 830 transitions. [2018-10-14 16:43:44,173 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 829 [2018-10-14 16:43:44,173 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:43:44,174 INFO L375 BasicCegarLoop]: trace histogram [27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:43:44,174 INFO L424 AbstractCegarLoop]: === Iteration 55 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:43:44,174 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:43:44,174 INFO L82 PathProgramCache]: Analyzing trace with hash 364145668, now seen corresponding path program 52 times [2018-10-14 16:43:44,175 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:43:44,219 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:43:49,260 INFO L134 CoverageAnalysis]: Checked inductivity of 10297 backedges. 5000 proven. 5297 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:43:49,261 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:43:49,261 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-14 16:43:49,261 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-14 16:43:49,262 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-14 16:43:49,262 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1428, Invalid=11228, Unknown=0, NotChecked=0, Total=12656 [2018-10-14 16:43:49,262 INFO L87 Difference]: Start difference. First operand 829 states and 830 transitions. Second operand 113 states. [2018-10-14 16:44:13,487 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:44:13,488 INFO L93 Difference]: Finished difference Result 863 states and 864 transitions. [2018-10-14 16:44:13,488 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 189 states. [2018-10-14 16:44:13,488 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 828 [2018-10-14 16:44:13,489 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:44:13,491 INFO L225 Difference]: With dead ends: 863 [2018-10-14 16:44:13,491 INFO L226 Difference]: Without dead ends: 863 [2018-10-14 16:44:13,493 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 277 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 271 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20491 ImplicationChecksByTransitivity, 18.1s TimeCoverageRelationStatistics Valid=12759, Invalid=61497, Unknown=0, NotChecked=0, Total=74256 [2018-10-14 16:44:13,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 863 states. [2018-10-14 16:44:13,497 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 863 to 843. [2018-10-14 16:44:13,497 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 843 states. [2018-10-14 16:44:13,498 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 843 states to 843 states and 844 transitions. [2018-10-14 16:44:13,498 INFO L78 Accepts]: Start accepts. Automaton has 843 states and 844 transitions. Word has length 828 [2018-10-14 16:44:13,499 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:44:13,499 INFO L481 AbstractCegarLoop]: Abstraction has 843 states and 844 transitions. [2018-10-14 16:44:13,499 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-14 16:44:13,499 INFO L276 IsEmpty]: Start isEmpty. Operand 843 states and 844 transitions. [2018-10-14 16:44:13,503 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 843 [2018-10-14 16:44:13,503 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:44:13,504 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 28, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:44:13,504 INFO L424 AbstractCegarLoop]: === Iteration 56 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:44:13,504 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:44:13,504 INFO L82 PathProgramCache]: Analyzing trace with hash 1795876024, now seen corresponding path program 53 times [2018-10-14 16:44:13,505 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:44:13,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:44:17,685 INFO L134 CoverageAnalysis]: Checked inductivity of 10665 backedges. 4683 proven. 5982 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:44:17,686 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:44:17,686 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [113] total 113 [2018-10-14 16:44:17,686 INFO L460 AbstractCegarLoop]: Interpolant automaton has 113 states [2018-10-14 16:44:17,687 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 113 interpolants. [2018-10-14 16:44:17,687 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1630, Invalid=11026, Unknown=0, NotChecked=0, Total=12656 [2018-10-14 16:44:17,688 INFO L87 Difference]: Start difference. First operand 843 states and 844 transitions. Second operand 113 states. [2018-10-14 16:44:28,107 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:44:28,107 INFO L93 Difference]: Finished difference Result 1253 states and 1254 transitions. [2018-10-14 16:44:28,108 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 167 states. [2018-10-14 16:44:28,108 INFO L78 Accepts]: Start accepts. Automaton has 113 states. Word has length 842 [2018-10-14 16:44:28,109 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:44:28,111 INFO L225 Difference]: With dead ends: 1253 [2018-10-14 16:44:28,111 INFO L226 Difference]: Without dead ends: 873 [2018-10-14 16:44:28,113 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 248 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17220 ImplicationChecksByTransitivity, 8.7s TimeCoverageRelationStatistics Valid=9342, Invalid=52908, Unknown=0, NotChecked=0, Total=62250 [2018-10-14 16:44:28,114 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 873 states. [2018-10-14 16:44:28,118 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 873 to 859. [2018-10-14 16:44:28,118 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 859 states. [2018-10-14 16:44:28,119 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 859 states to 859 states and 860 transitions. [2018-10-14 16:44:28,119 INFO L78 Accepts]: Start accepts. Automaton has 859 states and 860 transitions. Word has length 842 [2018-10-14 16:44:28,119 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:44:28,119 INFO L481 AbstractCegarLoop]: Abstraction has 859 states and 860 transitions. [2018-10-14 16:44:28,119 INFO L482 AbstractCegarLoop]: Interpolant automaton has 113 states. [2018-10-14 16:44:28,120 INFO L276 IsEmpty]: Start isEmpty. Operand 859 states and 860 transitions. [2018-10-14 16:44:28,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 859 [2018-10-14 16:44:28,124 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:44:28,125 INFO L375 BasicCegarLoop]: trace histogram [28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:44:28,125 INFO L424 AbstractCegarLoop]: === Iteration 57 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:44:28,125 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:44:28,125 INFO L82 PathProgramCache]: Analyzing trace with hash 49707952, now seen corresponding path program 54 times [2018-10-14 16:44:28,126 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:44:28,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-10-14 16:44:34,013 INFO L134 CoverageAnalysis]: Checked inductivity of 11098 backedges. 5408 proven. 5690 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-10-14 16:44:34,013 INFO L312 seRefinementStrategy]: Constructing automaton from 0 perfect and 1 imperfect interpolant sequences. [2018-10-14 16:44:34,014 INFO L327 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [117] total 117 [2018-10-14 16:44:34,014 INFO L460 AbstractCegarLoop]: Interpolant automaton has 117 states [2018-10-14 16:44:34,014 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 117 interpolants. [2018-10-14 16:44:34,015 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=1487, Invalid=12085, Unknown=0, NotChecked=0, Total=13572 [2018-10-14 16:44:34,015 INFO L87 Difference]: Start difference. First operand 859 states and 860 transitions. Second operand 117 states. [2018-10-14 16:45:00,510 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-10-14 16:45:00,510 INFO L93 Difference]: Finished difference Result 893 states and 894 transitions. [2018-10-14 16:45:00,510 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 195 states. [2018-10-14 16:45:00,511 INFO L78 Accepts]: Start accepts. Automaton has 117 states. Word has length 858 [2018-10-14 16:45:00,511 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-10-14 16:45:00,513 INFO L225 Difference]: With dead ends: 893 [2018-10-14 16:45:00,513 INFO L226 Difference]: Without dead ends: 893 [2018-10-14 16:45:00,515 INFO L605 BasicCegarLoop]: 0 DeclaredPredicates, 286 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 280 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21833 ImplicationChecksByTransitivity, 20.2s TimeCoverageRelationStatistics Valid=13361, Invalid=65881, Unknown=0, NotChecked=0, Total=79242 [2018-10-14 16:45:00,516 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 893 states. [2018-10-14 16:45:00,520 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 893 to 873. [2018-10-14 16:45:00,520 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 873 states. [2018-10-14 16:45:00,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 873 states to 873 states and 874 transitions. [2018-10-14 16:45:00,521 INFO L78 Accepts]: Start accepts. Automaton has 873 states and 874 transitions. Word has length 858 [2018-10-14 16:45:00,521 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-10-14 16:45:00,521 INFO L481 AbstractCegarLoop]: Abstraction has 873 states and 874 transitions. [2018-10-14 16:45:00,521 INFO L482 AbstractCegarLoop]: Interpolant automaton has 117 states. [2018-10-14 16:45:00,522 INFO L276 IsEmpty]: Start isEmpty. Operand 873 states and 874 transitions. [2018-10-14 16:45:00,526 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 873 [2018-10-14 16:45:00,526 INFO L367 BasicCegarLoop]: Found error trace [2018-10-14 16:45:00,527 INFO L375 BasicCegarLoop]: trace histogram [29, 29, 29, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-10-14 16:45:00,527 INFO L424 AbstractCegarLoop]: === Iteration 58 === [ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2018-10-14 16:45:00,527 INFO L141 PredicateUnifier]: Initialized classic predicate unifier [2018-10-14 16:45:00,527 INFO L82 PathProgramCache]: Analyzing trace with hash 930223972, now seen corresponding path program 55 times [2018-10-14 16:45:00,528 INFO L69 tionRefinementEngine]: Using refinement strategy FixedRefinementStrategy [2018-10-14 16:45:00,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat