{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:24:03Z","timestamp":1770963843551,"version":"3.50.1"},"reference-count":43,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>Input-driven pushdown automata ([Formula: see text]) are pushdown automata where the next action on the pushdown store (push, pop, nothing) is solely governed by the current input symbol. Here, we introduce sweeping input-driven pushdown automata that process the input in multiple passes (also sweeps). That is, a sweeping input-driven pushdown automaton is a two-way device that may change the input head direction only at the endmarkers. First we show that, given an arbitrary [Formula: see text], an equivalent [Formula: see text] that halts on any input can effectively be constructed. From this result further properties follow. Then we address the determinization of [Formula: see text]s and its descriptional complexity. Furthermore, the computational capacity of [Formula: see text]s is studied. To this end, we compare the family [Formula: see text] with other well-known language families. In particular, we are interested in families that have strong relations to some kind of pushdown machines. Finally, we explore several decidability problems and show that emptiness and several other problems are non-semidecidable by reductions of non-semidecidable problems of deterministic, linearly space bounded, one-tape, one-head Turing machines.<\/jats:p>","DOI":"10.1142\/s0129054125410072","type":"journal-article","created":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T03:39:06Z","timestamp":1749613146000},"page":"167-191","source":"Crossref","is-referenced-by-count":1,"title":["Sweeping Input-Driven Pushdown Automata"],"prefix":"10.1142","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9564-2625","authenticated-orcid":false,"given":"Martin","family":"Kutrib","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstr.\u00a02, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2025,6,11]]},"reference":[{"key":"S0129054125410072BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)91087-5"},{"key":"S0129054125410072BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007390"},{"key":"S0129054125410072BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"S0129054125410072BIB004","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054120420022"},{"key":"S0129054125410072BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33475-7_3"},{"key":"S0129054125410072BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(71)80025-9"},{"key":"S0129054125410072BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289076"},{"key":"S0129054125410072BIB008","unstructured":"G. Buntrock, Wachsende kontextsensitive Sprachen, Habilitationsschrift, Fakult\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t W\u00fcrzburg (1996) (in German)."},{"key":"S0129054125410072BIB009","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2681"},{"key":"S0129054125410072BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.08.012"},{"key":"S0129054125410072BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/11779148_12"},{"key":"S0129054125410072BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74456-6_14"},{"key":"S0129054125410072BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.12.006"},{"key":"S0129054125410072BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90062-0"},{"key":"S0129054125410072BIB015","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2935315"},{"key":"S0129054125410072BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90148-2"},{"key":"S0129054125410072BIB017","doi-asserted-by":"publisher","DOI":"10.1145\/321371.321385"},{"key":"S0129054125410072BIB018","first-page":"29","volume":"3","author":"Gladkii A. V.","year":"1964","journal-title":"Algebra i Logika. Sem."},{"key":"S0129054125410072BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786988"},{"key":"S0129054125410072BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189852"},{"key":"S0129054125410072BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90369-5"},{"key":"S0129054125410072BIB022","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90023-0"},{"key":"S0129054125410072BIB023","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054122410064"},{"key":"S0129054125410072BIB024","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054125410072BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-40247-0_14"},{"key":"S0129054125410072BIB026","volume":"55","author":"Kutrib M.","year":"2021","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"S0129054125410072BIB027","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.01.012"},{"key":"S0129054125410072BIB028","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30000-9_12"},{"key":"S0129054125410072BIB029","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2016016"},{"key":"S0129054125410072BIB030","first-page":"59","volume":"155","author":"Kutrib M.","year":"2017","journal-title":"Fund. Inform."},{"key":"S0129054125410072BIB031","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.01.032"},{"key":"S0129054125410072BIB032","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-07469-1_11"},{"key":"S0129054125410072BIB033","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.9"},{"key":"S0129054125410072BIB034","unstructured":"S. La Torre, M. Napoli and G. Parlato, On multi-stack visibly pushdown languages Preprint, (2013)."},{"key":"S0129054125410072BIB035","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054116400074"},{"key":"S0129054125410072BIB036","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1783"},{"key":"S0129054125410072BIB037","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926419"},{"key":"S0129054125410072BIB038","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.04.007"},{"key":"S0129054125410072BIB039","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10003-2_89"},{"key":"S0129054125410072BIB040","doi-asserted-by":"publisher","DOI":"10.1145\/2636805.2636821"},{"key":"S0129054125410072BIB041","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1965.11"},{"key":"S0129054125410072BIB042","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322083"},{"key":"S0129054125410072BIB043","series-title":"Mathematics Studies","first-page":"1","volume-title":"Topics in the Theory of Computation","volume":"102","author":"von Braunm\u00fchl B.","year":"1985"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054125410072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:37:03Z","timestamp":1770961023000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125410072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,11]]},"references-count":43,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1142\/S0129054125410072"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125410072","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,11]]}}}