  We propose several heuristics for mitigating one of the main causes of
combinatorial explosion in rank-based complementation of B\"{u}chi automata
(BAs): unnecessarily high bounds on the ranks of states. First, we identify
elevator automata, which is a large class of BAs (generalizing
semi-deterministic BAs), occurring often in practice, where ranks of states are
bounded according to the structure of strongly connected components. The bounds
for elevator automata also carry over to general BAs that contain elevator
automata as a sub-structure. Second, we introduce two techniques for refining
bounds on the ranks of BA states using data-flow analysis of the automaton. We
implement out techniques as an extension of the tool Ranker for BA
complementation and show that they indeed greatly prune the generated state
space, obtaining significantly better results and outperforming other
state-of-the-art tools on a large set of benchmarks.
