{"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":1771952235573,"version":"3.50.1"},"reference-count":21,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100002790","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2016-06172"],"award-info":[{"award-number":["2016-06172"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1117708"],"award-info":[{"award-number":["CCF-1117708"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p> We examine different generalizations of checking stack automata by allowing multiple input heads and multiple stacks, and characterize their computing power in terms of two-way multi-head finite automata and space-bounded Turing machines. For various models, we obtain hierarchies in terms of their computing power. Our characterizations and hierarchies expand or tighten some previously known results. We also discuss some decidability questions and the space\/time complexity of the models. <\/jats:p>","DOI":"10.1142\/s0129054121410045","type":"journal-article","created":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T07:46:01Z","timestamp":1619423161000},"page":"481-508","source":"Crossref","is-referenced-by-count":6,"title":["Generalizations of Checking Stack Automata: Characterizations and Hierarchies"],"prefix":"10.1142","volume":"32","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, CA 93106, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2021,4,23]]},"reference":[{"key":"S0129054121410045BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80004-6"},{"key":"S0129054121410045BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/321623.321625"},{"key":"S0129054121410045BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90015-1"},{"key":"S0129054121410045BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321403"},{"key":"S0129054121410045BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/321371.321385"},{"key":"S0129054121410045BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691341"},{"key":"S0129054121410045BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(69)80012-7"},{"key":"S0129054121410045BIB008","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S0129054121410045BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(71)80029-6"},{"key":"S0129054121410045BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321727"},{"key":"S0129054121410045BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80048-0"},{"key":"S0129054121410045BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-48516-0_11"},{"key":"S0129054121410045BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98654-8_34"},{"key":"S0129054121410045BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.04.024"},{"key":"S0129054121410045BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90010-7"},{"key":"S0129054121410045BIB016","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"S0129054121410045BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263746"},{"key":"S0129054121410045BIB018","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1980140100671"},{"key":"S0129054121410045BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80042-1"},{"key":"S0129054121410045BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21545-6_3"},{"key":"S0129054121410045BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90142-2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121410045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T01:44:29Z","timestamp":1628732669000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121410045"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,23]]},"references-count":21,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1142\/S0129054121410045"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121410045","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,23]]}}}