  We examine different generalizations of checking stack automata by allowing
multiple input heads and multiple stacks, and characterize their computing
power in terms of two-way multi-head finite automata and space-bounded Turing
machines. For various models, we obtain hierarchies in terms of their computing
power. Our characterizations and hierarchies expand or tighten some previously
known results. We also discuss some decidability questions and the space/time
complexity of the models.
