{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:21Z","timestamp":1753894401501,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study the expressiveness and succinctness of history-deterministic\npushdown automata (HD-PDA) over finite words, that is, pushdown automata whose\nnondeterminism can be resolved based on the run constructed so far, but\nindependently of the remainder of the input word. These are also known as\ngood-for-games pushdown automata. We prove that HD-PDA recognise more languages\nthan deterministic PDA (DPDA) but not all context-free languages (CFL). This\nclass is orthogonal to unambiguous CFL. We further show that HD-PDA can be\nexponentially more succinct than DPDA, while PDA can be double-exponentially\nmore succinct than HD-PDA. We also study HDness in visibly pushdown automata\n(VPA), which enjoy better closure properties than PDA, and for which we show\nthat deciding HDness is ExpTime-complete. HD-VPA can be exponentially more\nsuccinct than deterministic VPA, while VPA can be exponentially more succinct\nthan HD-VPA. Both of these lower bounds are tight. We then compare HD-PDA with\nPDA for which composition with games is well-behaved, i.e. good-for-games\nautomata. We show that these two notions coincide, but only if we consider\npotentially infinitely branching games. Finally, we study the complexity of\nresolving nondeterminism in HD-PDA. Every HDPDA has a positional resolver, a\nfunction that resolves nondeterminism and that is only dependant on the current\nconfiguration. Pushdown transducers are sufficient to implement the resolvers\nof HD-VPA, but not those of HD-PDA. HD-PDA with finite-state resolvers are\ndeterminisable.<\/jats:p>","DOI":"10.46298\/lmcs-20(1:3)2024","type":"journal-article","created":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T19:15:09Z","timestamp":1705000509000},"source":"Crossref","is-referenced-by-count":1,"title":["A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct"],"prefix":"10.46298","volume":"Volume 20, Issue 1","author":[{"given":"Shibashis","family":"Guha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Isma\u00ebl","family":"Jecker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karoliina","family":"Lehtinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Zimmermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2024,1,11]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/12860\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/12860\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T19:15:20Z","timestamp":1705000520000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/10156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(1:3)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2105.02611v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2105.02611v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2105.02611","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2105.02611","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2024,1,11]]},"article-number":"10156"}}