{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,26]],"date-time":"2025-04-26T04:01:13Z","timestamp":1745640073369,"version":"3.40.4"},"reference-count":25,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2022-05092"],"award-info":[{"award-number":["2022-05092"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:p> We study one-way nondeterministic pushdown automata ([Formula: see text]), optionally with reversal-bounded counters. Finite-turn pushdown automata are pushdown automata with a bound on the number of switches between pushing and popping. We give new characterizations for finite-turn pushdown automata, and for finite-turn pushdown automata augmented with reversal-bounded counters. The first is in terms of multi-tape nondeterministic finite automata ([Formula: see text]), and the second is in terms of multi-tape [Formula: see text] with reversal-bounded counters. We then use the characterizations to determine the complexity of the languages defined by these automata. In particular, we show that languages accepted by finite-turn [Formula: see text] augmented with reversal-bounded counters are in [Formula: see text]. For the non-finite-turn case, the languages are in [Formula: see text] and in [Formula: see text]. We also look at the space complexity of languages accepted by two-way machines. In particular, we show that every language accepted by a two-way [Formula: see text] with reversal-bounded counters that makes a polynomial (resp., exponential) number of input head reversals is in [Formula: see text] (resp., [Formula: see text]). This remains true if the pushdown can flip its contents a bounded number of times. <\/jats:p>","DOI":"10.1142\/s0129054124430044","type":"journal-article","created":{"date-parts":[[2024,10,11]],"date-time":"2024-10-11T06:24:56Z","timestamp":1728627896000},"page":"345-370","source":"Crossref","is-referenced-by-count":0,"title":["Language Acceptors with a Pushdown: Characterizations and Complexity"],"prefix":"10.1142","volume":"36","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7998-4430","authenticated-orcid":false,"given":"Ian","family":"McQuillan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Saskatchewan, Saskatoon, SK S7N 5C9, Canada"}]}],"member":"219","published-online":{"date-parts":[[2024,10,10]]},"reference":[{"key":"S0129054124430044BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)91087-5"},{"key":"S0129054124430044BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80027-9"},{"key":"S0129054124430044BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30829-1_12"},{"key":"S0129054124430044BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802468"},{"key":"S0129054124430044BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90008-6"},{"key":"S0129054124430044BIB006","doi-asserted-by":"publisher","DOI":"10.1145\/321623.321625"},{"key":"S0129054124430044BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00282-1"},{"key":"S0129054124430044BIB008","doi-asserted-by":"publisher","DOI":"10.1137\/0304034"},{"key":"S0129054124430044BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90028-3"},{"key":"S0129054124430044BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_60"},{"key":"S0129054124430044BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)90901-7"},{"key":"S0129054124430044BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45007-6_29"},{"key":"S0129054124430044BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_40"},{"volume-title":"Formal Languages and Their Relation to Automata","year":"1969","author":"Hopcroft J. E.","key":"S0129054124430044BIB014"},{"volume-title":"Introduction to Automata Theory, Languages, and Computation","year":"1979","author":"Hopcroft J. E.","key":"S0129054124430044BIB015"},{"key":"S0129054124430044BIB016","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322058"},{"key":"S0129054124430044BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.06.035"},{"key":"S0129054124430044BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.03.003"},{"key":"S0129054124430044BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2023.105080"},{"key":"S0129054124430044BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90068-2"},{"key":"S0129054124430044BIB021","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1965.14"},{"key":"S0129054124430044BIB022","doi-asserted-by":"publisher","DOI":"10.1080\/0020716022000005564"},{"key":"S0129054124430044BIB023","first-page":"107","volume":"14","author":"Pighizzini G.","year":"2009","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0129054124430044BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80006-8"},{"key":"S0129054124430044BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80014-6"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054124430044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T03:17:31Z","timestamp":1745551051000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054124430044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,10]]},"references-count":25,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["10.1142\/S0129054124430044"],"URL":"https:\/\/doi.org\/10.1142\/s0129054124430044","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2024,10,10]]}}}