{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:35Z","timestamp":1759638755346,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2013,9,11]],"date-time":"2013-09-11T00:00:00Z","timestamp":1378857600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>This paper is about reachability analysis in a restricted subclass of\nmulti-pushdown automata. We assume that the control states of an automaton are\npartially ordered, and all transitions of an automaton go downwards with\nrespect to the order. We prove decidability of the reachability problem, and\ncomputability of the backward reachability set. As the main contribution, we\nidentify relevant subclasses where the reachability problem becomes\nNP-complete. This matches the complexity of the same problem for\ncommunication-free vector addition systems, a special case of stateless\nmulti-pushdown automata.<\/jats:p>","DOI":"10.2168\/lmcs-9(3:13)2013","type":"journal-article","created":{"date-parts":[[2013,11,29]],"date-time":"2013-11-29T13:44:29Z","timestamp":1385732669000},"source":"Crossref","is-referenced-by-count":2,"title":["Reachability Problem for Weak Multi-Pushdown Automata"],"prefix":"10.46298","volume":"Volume 9, Issue 3","author":[{"given":"Wojciech","family":"Czerwi\u0144ski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9866-3723","authenticated-orcid":false,"given":"Piotr","family":"Hofman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u0141awomir","family":"Lasota","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2013,9,11]]},"reference":[{"key":"833:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/857\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/857\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:57:42Z","timestamp":1681243062000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/857"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,11]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-9(3:13)2013","relation":{"is-same-as":[{"id-type":"arxiv","id":"1308.3996","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1308.3996","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2013,9,11]]},"article-number":"857"}}