Reachability Problem for Weak Multi-Pushdown Automata

This paper is about reachability analysis in a restricted subclass ofmulti-pushdown automata. We assume that the control states of an automaton arepartially ordered, and all transitions of an automaton go downwards withrespect to the order. We prove decidability of the reachability problem, andcomputability of the backward reachability set. As the main contribution, weidentify relevant subclasses where the reachability problem becomesNP-complete. This matches the complexity of the same problem forcommunication-free vector addition systems, a special case of statelessmulti-pushdown automata