{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:10:40Z","timestamp":1771024240979,"version":"3.50.1"},"reference-count":7,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2016,2]]},"abstract":"<jats:p>We study the formal language theory of multistack pushdown automata (MPA) restricted to computations where a symbol can be popped from a stack S only if it was pushed within a bounded number of contexts of S (scoped MPA). We show that scoped MPA are indeed a robust model of computation, by focusing on the corresponding theory of visibly MPA (MVPA). We prove the equivalence of the deterministic and nondeterministic versions and show that scope-bounded computations of an n-stack MVPA can be simulated, rearranging the input word, by using only one stack. These results have some interesting consequences, such as, the closure under complement, the decidability of universality, inclusion and equality, and the effective semilinearity of the Parikh image (Parikh's theorem). As a further contribution, we give a logical characterization and compare the expressiveness of the scope-bounded restriction with other MVPA classes from the literature. To the best of our knowledge, scoped MVPA languages form the largest class of formal languages accepted by MPA that enjoys all the above nice properties.<\/jats:p>","DOI":"10.1142\/s0129054116400074","type":"journal-article","created":{"date-parts":[[2016,5,4]],"date-time":"2016-05-04T08:25:46Z","timestamp":1462350346000},"page":"215-233","source":"Crossref","is-referenced-by-count":18,"title":["Scope-Bounded Pushdown Languages"],"prefix":"10.1142","volume":"27","author":[{"given":"Salvatore La","family":"Torre","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Salerno Via Giovanni Paolo II 132, 84084 Fisciano, Italy"}]},{"given":"Margherita","family":"Napoli","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Salerno Via Giovanni Paolo II 132, 84084 Fisciano, Italy"}]},{"given":"Gennaro","family":"Parlato","sequence":"additional","affiliation":[{"name":"School of Electronics &amp; Computer Science, University of Southampton Highfield, Southampton S0171BJ, UK"}]}],"member":"219","published-online":{"date-parts":[[2016,5,4]]},"reference":[{"key":"p_1","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/1007352.1007390","author":"Alur R.","year":"2004","journal-title":"STOC"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-009-0078-9"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000191"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-014-0207-y"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054114400255"},{"key":"p_37","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321364"},{"key":"p_38","first-page":"389","volume":"3","author":"Thomas W.","journal-title":"Handbook of Formal Languages"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054116400074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,17]],"date-time":"2023-08-17T22:08:44Z","timestamp":1692310124000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116400074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2]]},"references-count":7,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2016,5,4]]},"published-print":{"date-parts":[[2016,2]]}},"alternative-id":["10.1142\/S0129054116400074"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116400074","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2]]}}}