Wojciech Czerwiński ; Piotr Hofman ; SŁawomir Lasota - Reachability Problem for Weak Multi-Pushdown Automata

lmcs:857 - Logical Methods in Computer Science, September 11, 2013, Volume 9, Issue 3 - https://doi.org/10.2168/LMCS-9(3:13)2013
Reachability Problem for Weak Multi-Pushdown Automata

Authors: Wojciech Czerwiński ; Piotr Hofman ORCID-iD; SŁawomir Lasota

    This paper is about reachability analysis in a restricted subclass of multi-pushdown automata. We assume that the control states of an automaton are partially ordered, and all transitions of an automaton go downwards with respect to the order. We prove decidability of the reachability problem, and computability of the backward reachability set. As the main contribution, we identify relevant subclasses where the reachability problem becomes NP-complete. This matches the complexity of the same problem for communication-free vector addition systems, a special case of stateless multi-pushdown automata.


    Volume: Volume 9, Issue 3
    Published on: September 11, 2013
    Accepted on: June 25, 2015
    Submitted on: January 14, 2013
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory

    3 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 367 times.
    This article's PDF has been downloaded 377 times.