  We address the verification problem of ordered multi-pushdown automata: A
multi-stack extension of pushdown automata that comes with a constraint on
stack transitions such that a pop can only be performed on the first non-empty
stack. First, we show that the emptiness problem for ordered multi-pushdown
automata is in 2ETIME. Then, we prove that, for an ordered multi-pushdown
automata, the set of all predecessors of a regular set of configurations is an
effectively constructible regular set. We exploit this result to solve the
global model-checking which consists in computing the set of all configurations
of an ordered multi-pushdown automaton that satisfy a given w-regular property
(expressible in linear-time temporal logics or the linear-time \mu-calculus).
As an immediate consequence, we obtain an 2ETIME upper bound for the
model-checking problem of w-regular properties for ordered multi-pushdown
automata (matching its lower-bound).
