{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:55Z","timestamp":1760202595906,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2008,12,24]],"date-time":"2008-12-24T00:00:00Z","timestamp":1230076800000},"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>Visibly pushdown automata are input-driven pushdown automata that recognize\nsome non-regular context-free languages while preserving the nice closure and\ndecidability properties of finite automata. Visibly pushdown automata with\nmultiple stacks have been considered recently by La Torre, Madhusudan, and\nParlato, who exploit the concept of visibility further to obtain a rich\nautomata class that can even express properties beyond the class of\ncontext-free languages. At the same time, their automata are closed under\nboolean operations, have a decidable emptiness and inclusion problem, and enjoy\na logical characterization in terms of a monadic second-order logic over words\nwith an additional nesting structure. These results require a restricted\nversion of visibly pushdown automata with multiple stacks whose behavior can be\nsplit up into a fixed number of phases. In this paper, we consider 2-stack\nvisibly pushdown automata (i.e., visibly pushdown automata with two stacks) in\ntheir unrestricted form. We show that they are expressively equivalent to the\nexistential fragment of monadic second-order logic. Furthermore, it turns out\nthat monadic second-order quantifier alternation forms an infinite hierarchy\nwrt words with multiple nestings. Combining these results, we conclude that\n2-stack visibly pushdown automata are not closed under complementation.\nFinally, we discuss the expressive power of B\\\"{u}chi 2-stack visibly pushdown\nautomata running on infinite (nested) words. Extending the logic by an infinity\nquantifier, we can likewise establish equivalence to existential monadic\nsecond-order logic.<\/jats:p>","DOI":"10.2168\/lmcs-4(4:16)2008","type":"journal-article","created":{"date-parts":[[2009,1,9]],"date-time":"2009-01-09T10:25:38Z","timestamp":1231496738000},"source":"Crossref","is-referenced-by-count":4,"title":["On the Expressive Power of 2-Stack Visibly Pushdown Automata"],"prefix":"10.46298","volume":"Volume 4, Issue 4","author":[{"given":"Benedikt","family":"Bollig","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2008,12,24]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1101\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1101\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:03:29Z","timestamp":1681243409000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,24]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-4(4:16)2008","relation":{"is-same-as":[{"id-type":"arxiv","id":"0812.2423","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.0812.2423","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2008,12,24]]},"article-number":"1101"}}