{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T16:57:15Z","timestamp":1771952235589,"version":"3.50.1"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p> This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept every word in the language of the automaton (weak measure), the maximum stack size used in any accepting computation on any accepted word (accept measure), and the maximum stack size used in any computation (strong measure). We give a detailed characterization of the accept and strong space complexity measures for checking stack automata. Exactly one of three cases can occur: the complexity is either bounded by a constant, behaves like a linear function, or it can not be bounded by any function of the length of the input word (and it is decidable which case occurs). However, this result does not hold for non-erasing stack automata; we provide an example where the space complexity grows proportionally to the square root of the length of the input. Furthermore, we study the complexity bounds of machines which accept a given language, and decidability of space complexity properties. <\/jats:p>","DOI":"10.1142\/s0129054121420090","type":"journal-article","created":{"date-parts":[[2021,9,21]],"date-time":"2021-09-21T00:48:40Z","timestamp":1632185320000},"page":"801-823","source":"Crossref","is-referenced-by-count":5,"title":["Space Complexity of Stack Automata Models"],"prefix":"10.1142","volume":"32","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, California 93106, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"Jr.","given":"Jozef","family":"Jir\u00e1sek","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Saskatchewan, Saskatoon, Saskatchewan S7N 5A9, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian","family":"McQuillan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Saskatchewan, Saskatoon, Saskatchewan S7N 5A9, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Prigioniero","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Milano, Via Celoria, 18 \u2013 Milan, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"S0129054121420090BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007390"},{"key":"S0129054121420090BIB002","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054117400081"},{"key":"S0129054121420090BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90015-1"},{"key":"S0129054121420090BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(69)80012-7"},{"key":"S0129054121420090BIB005","volume-title":"Introduction to Formal Language Theory","author":"Harrison M.","year":"1978"},{"key":"S0129054121420090BIB006","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/019\/0235938"},{"key":"S0129054121420090BIB007","doi-asserted-by":"publisher","DOI":"10.1145\/214037.214040"},{"key":"S0129054121420090BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(68)90722-5"},{"key":"S0129054121420090BIB009","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J.","year":"1979"},{"key":"S0129054121420090BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.05.036"},{"key":"S0129054121420090BIB011","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054121410045"},{"key":"S0129054121420090BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_47"},{"key":"S0129054121420090BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90010-7"},{"key":"S0129054121420090BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23247-4_20"},{"key":"S0129054121420090BIB015","first-page":"107","volume":"14","author":"Pighizzini G.","year":"2009","journal-title":"J. Automata, Languages and Combinatorics"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121420090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T05:36:33Z","timestamp":1633066593000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121420090"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":15,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["10.1142\/S0129054121420090"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121420090","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9]]}}}