{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T13:19:01Z","timestamp":1774271941000,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T00:00:00Z","timestamp":1771891200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T00:00:00Z","timestamp":1771891200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Justus-Liebig-Universit\u00e4t Gie\u00dfen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We introduce and investigate tree-walking-storage automata, which are finite-state devices equipped with a tree-like storage. The automata are generalized stack automata, where the linear stack storage is replaced by a non-linear tree-like stack. Therefore, tree-walking-storage automata have the ability to explore the interior of the tree storage without altering the contents, where the possible moves of the tree pointer correspond to those of tree-walking automata. In addition, a tree-walking-storage automaton can append (push) non-existent descendants to a tree node and remove (pop) leaves from the tree. As for classical stack automata, we also consider non-erasing and checking variants. As a first step to investigate these models we consider the computational capacities of deterministic one-way variants. In particular, a primary focus lies on comparing the different variants of tree-walking-storage automata as well as with classical stack automata, enabling us to draw a complete picture. Basic closure properties of the induced families of languages are shown. In particular, we consider Boolean operations and several AFL operations.<\/jats:p>","DOI":"10.1007\/s00236-026-00522-5","type":"journal-article","created":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T07:43:34Z","timestamp":1771919014000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic tree-walking-storage automata"],"prefix":"10.1007","volume":"63","author":[{"given":"Martin","family":"Kutrib","sequence":"first","affiliation":[]},{"given":"Uwe","family":"Meyer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,24]]},"reference":[{"issue":"5","key":"522_CR1","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0019-9958(71)90706-6","volume":"19","author":"AV Aho","year":"1971","unstructured":"Aho, A.V., Ullman, J.D.: Translations on a context-free grammar. Information and Control 19(5), 439\u2013475 (1971). https:\/\/doi.org\/10.1016\/S0019-9958(71)90706-6","journal-title":"Information and Control"},{"key":"522_CR2","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1142\/S0129054117400081","volume":"28","author":"S Bensch","year":"2017","unstructured":"Bensch, S., Bj\u00f6rklund, J., Kutrib, M.: Deterministic stack transducers. Int. J. Found. Comput. Sci. 28, 583\u2013601 (2017). https:\/\/doi.org\/10.1142\/S0129054117400081","journal-title":"Int. J. Found. Comput. Sci."},{"key":"522_CR3","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.tcs.2005.10.031","volume":"350","author":"M Boja\u0144czyk","year":"2006","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree-walking automata cannot be determinized. Theor. Comput. Sci. 350, 164\u2013173 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2005.10.031","journal-title":"Theor. Comput. Sci."},{"key":"522_CR4","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1137\/050645427","volume":"38","author":"M Boja\u0144czyk","year":"2008","unstructured":"Boja\u0144czyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. SIAM J. Comput. 38, 658\u2013701 (2008). https:\/\/doi.org\/10.1137\/050645427","journal-title":"SIAM J. Comput."},{"key":"522_CR5","doi-asserted-by":"crossref","unstructured":"Chomsky, N., Sch\u00fctzenberger, M.P.: The algebraic theory of context-free languages. In: Computer Programming and Formal Systems. Studies in Logic and the Foundations of Mathematics, pp. 118\u2013161. North-Holland, (1963)","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"522_CR6","doi-asserted-by":"publisher","unstructured":"Denkinger, T.: An automata characterisation for multiple context-free languages. In: Brlek, S., Reutenauer, C. (eds.) Developments in Language Theory (DLT 2016). LNCS, vol. 9840, pp. 138\u2013150. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-662-53132-7_12","DOI":"10.1007\/978-3-662-53132-7_12"},{"key":"522_CR7","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1145\/321371.321385","volume":"14","author":"S Ginsburg","year":"1967","unstructured":"Ginsburg, S., Greibach, S.A., Harrison, M.A.: Stack automata and compiling. J. ACM 14, 172\u2013201 (1967). https:\/\/doi.org\/10.1145\/321371.321385","journal-title":"J. ACM"},{"key":"522_CR8","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1145\/321386.321403","volume":"14","author":"S Ginsburg","year":"1967","unstructured":"Ginsburg, S., Greibach, S.A., Harrison, M.A.: One-way stack automata. J. ACM 14, 389\u2013418 (1967). https:\/\/doi.org\/10.1145\/321386.321403","journal-title":"J. ACM"},{"key":"522_CR9","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/BF01201277","volume":"29","author":"W Golubski","year":"1996","unstructured":"Golubski, W., Lippe, W.: Tree-stack automata. Math. Systems Theory 29, 227\u2013244 (1996). https:\/\/doi.org\/10.1007\/BF01201277","journal-title":"Math. Systems Theory"},{"key":"522_CR10","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/S0022-0000(69)80012-7","volume":"3","author":"SA Greibach","year":"1969","unstructured":"Greibach, S.A.: Checking automata and one-way stack languages. Journal of Computer and System Sciences 3, 196\u2013217 (1969). https:\/\/doi.org\/10.1016\/S0022-0000(69)80012-7","journal-title":"Journal of Computer and System Sciences"},{"key":"522_CR11","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0304-3975(78)90035-X","volume":"6","author":"SA Greibach","year":"1978","unstructured":"Greibach, S.A.: One way finite visit automata. Theor. Comput. Sci. 6, 175\u2013221 (1978). https:\/\/doi.org\/10.1016\/0304-3975(78)90035-X","journal-title":"Theor. Comput. Sci."},{"key":"522_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF01744582","volume":"16","author":"I Guessarian","year":"1983","unstructured":"Guessarian, I.: Pushdown tree automata. Math. Systems Theory 16, 237\u2013263 (1983). https:\/\/doi.org\/10.1007\/BF01744582","journal-title":"Math. Systems Theory"},{"key":"522_CR13","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01786980","volume":"15","author":"EM Gurari","year":"1982","unstructured":"Gurari, E.M., Ibarra, O.H.: (semi)alternating stack automata. Math. Systems Theory 15, 211\u2013224 (1982). https:\/\/doi.org\/10.1007\/BF01786980","journal-title":"Math. Systems Theory"},{"key":"522_CR14","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1145\/321637.321639","volume":"18","author":"MA Harrison","year":"1971","unstructured":"Harrison, M.A., Schkolnick, M.: A grammatical characterization of one-way nondeterministic stack languages. J. ACM 18, 148\u2013172 (1971). https:\/\/doi.org\/10.1145\/321637.321639","journal-title":"J. ACM"},{"key":"522_CR15","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/S0019-9958(67)90513-X","volume":"11","author":"TN Hibbard","year":"1967","unstructured":"Hibbard, T.N.: A generalization of context-free determinism. Inform. Control 11, 196\u2013238 (1967). https:\/\/doi.org\/10.1016\/S0019-9958(67)90513-X","journal-title":"Inform. Control"},{"key":"522_CR16","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/S0019-9958(68)90722-5","volume":"13","author":"JE Hopcroft","year":"1968","unstructured":"Hopcroft, J.E., Ullman, J.D.: Sets accepted by one-way stack automata are context sensitive. Information and Control 13, 114\u2013133 (1968). https:\/\/doi.org\/10.1016\/S0019-9958(68)90722-5","journal-title":"Information and Control"},{"key":"522_CR17","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/S0022-0000(67)80013-8","volume":"1","author":"JE Hopcroft","year":"1967","unstructured":"Hopcroft, J.E., Ullman, J.D.: Nonerasing stack automata. Journal of Computer and System Sciences 1, 166\u2013186 (1967). https:\/\/doi.org\/10.1016\/S0022-0000(67)80013-8","journal-title":"Journal of Computer and System Sciences"},{"key":"522_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0022-0000(68)80003-0","volume":"2","author":"JE Hopcroft","year":"1968","unstructured":"Hopcroft, J.E., Ullman, J.D.: Deterministic stack automata and the quotient operator. Journal of Computer and System Sciences 2, 1\u201312 (1968). https:\/\/doi.org\/10.1016\/S0022-0000(68)80003-0","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"522_CR19","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/S0022-0000(71)80029-6","volume":"5","author":"OH Ibarra","year":"1971","unstructured":"Ibarra, O.H.: Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata. Journal of Computer and System Sciences 5(2), 88\u2013117 (1971). https:\/\/doi.org\/10.1016\/S0022-0000(71)80029-6","journal-title":"Journal of Computer and System Sciences"},{"key":"522_CR20","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1142\/S0129054121410045","volume":"32","author":"OH Ibarra","year":"2021","unstructured":"Ibarra, O.H., McQuillan, I.: Generalizations of checking stack automata: Characterizations and hierarchies. Int. J. Found. Comput. Sci. 32, 481\u2013508 (2021). https:\/\/doi.org\/10.1142\/S0129054121410045","journal-title":"Int. J. Found. Comput. Sci."},{"key":"522_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2018.04.024","volume":"738","author":"OH Ibarra","year":"2018","unstructured":"Ibarra, O.H., McQuillan, I.: Variations of checking stack automata: Obtaining unexpected decidability properties. Theoretical Computer Science 738, 1\u201312 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.04.024","journal-title":"Theoretical Computer Science"},{"key":"522_CR22","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1142\/S0129054121420090","volume":"32","author":"OH Ibarra","year":"2021","unstructured":"Ibarra, O.H., Jir\u00e1sek, J., McQuillan, I., Prigioniero, L.: Space complexity of stack automata models. Int. J. Found. Comput. Sci. 32, 801\u2013823 (2021). https:\/\/doi.org\/10.1142\/S0129054121420090","journal-title":"Int. J. Found. Comput. Sci."},{"key":"522_CR23","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/S0022-0000(74)80005-X","volume":"9","author":"SR Kosaraju","year":"1974","unstructured":"Kosaraju, S.R.: 1-way stack automaton with jumps. J. Comput. Syst. Sci. 9, 164\u2013176 (1974). https:\/\/doi.org\/10.1016\/S0022-0000(74)80005-X","journal-title":"J. Comput. Syst. Sci."},{"key":"522_CR24","doi-asserted-by":"publisher","first-page":"59","DOI":"10.3233\/FI-2017-1576","volume":"155","author":"M Kutrib","year":"2017","unstructured":"Kutrib, M., Malcher, A., Wendlandt, M.: Tinput-driven pushdown, counter, and stack automata. Fund. Inform. 155, 59\u201388 (2017). https:\/\/doi.org\/10.3233\/FI-2017-1576","journal-title":"Fund. Inform."},{"key":"522_CR25","doi-asserted-by":"publisher","unstructured":"Kutrib, M., Wendlandt, M.: On simulation costs of unary limited automata. In: Shallit, J., Okhotin, A. (eds.) Descriptional Complexity of Formal Systems (DCFS 2015). LNCS, vol. 9118, pp. 153\u2013164. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-319-19225-3_13","DOI":"10.1007\/978-3-319-19225-3_13"},{"key":"522_CR26","doi-asserted-by":"publisher","unstructured":"Kutrib, M., Wendlandt, M.: Reversible limited automata. In: Durand-Lose, J., Nagy, B. (eds.) Machines, Computations, and Universality (MCU 2015). LNCS, vol. 9288, pp. 113\u2013128. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-319-23111-2_8","DOI":"10.1007\/978-3-319-23111-2_8"},{"key":"522_CR27","doi-asserted-by":"publisher","unstructured":"Kutrib, M., Meyer, U.: Tree-walking-storage automata. In: Drewes, F., Volkov, M. (eds.) Developments in Language Theory (DLT 2023). LNCS, vol. 13911, pp. 182\u2013194. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-33264-7_15","DOI":"10.1007\/978-3-031-33264-7_15"},{"key":"522_CR28","doi-asserted-by":"publisher","first-page":"795","DOI":"10.3217\/jucs-016-05-0795","volume":"16","author":"K Lange","year":"2010","unstructured":"Lange, K.: A note on the P-completeness of deterministic one-way stack language. J. UCS 16, 795\u2013799 (2010). https:\/\/doi.org\/10.3217\/jucs-016-05-0795","journal-title":"J. UCS"},{"key":"522_CR29","doi-asserted-by":"publisher","unstructured":"Ogden, W.F.: Intercalation theorems for stack languages. In: Proceedings of the First Annual ACM Symposium on Theory of Computing (STOC 1969), pp. 31\u201342. ACM Press, New York (1969). https:\/\/doi.org\/10.1145\/800169.805419","DOI":"10.1145\/800169.805419"},{"key":"522_CR30","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1142\/S0129054114400140","volume":"25","author":"G Pighizzini","year":"2014","unstructured":"Pighizzini, G., Pisoni, A.: Limited automata and regular languages. Int. J. Found. Comput. Sci. 25, 897\u2013916 (2014). https:\/\/doi.org\/10.1142\/S0129054114400140","journal-title":"Int. J. Found. Comput. Sci."},{"key":"522_CR31","doi-asserted-by":"publisher","first-page":"157","DOI":"10.3233\/FI-2015-1148","volume":"136","author":"G Pighizzini","year":"2015","unstructured":"Pighizzini, G., Pisoni, A.: Limited automata and context-free languages. Fundamenta Informaticae 136, 157\u2013176 (2015). https:\/\/doi.org\/10.3233\/FI-2015-1148","journal-title":"Fundamenta Informaticae"},{"key":"522_CR32","doi-asserted-by":"publisher","unstructured":"Shamir, E., Beeri, C.: Checking stacks and context-free programmed grammars accept P-complete languages. In: Loeckx, J. (ed.) International Colloquium on Automata, Languages and Programming (ICALP 1974). LNCS, vol. 14, pp. 27\u201333. Springer (1974). https:\/\/doi.org\/10.1007\/3-540-06841-4_50","DOI":"10.1007\/3-540-06841-4_50"},{"key":"522_CR33","volume-title":"Computational Complexity","author":"K Wagner","year":"1986","unstructured":"Wagner, K., Wechsung, G.: Computational Complexity. Reidel, Dordrecht (1986)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00522-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-026-00522-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-026-00522-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T12:25:45Z","timestamp":1774268745000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-026-00522-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,24]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["522"],"URL":"https:\/\/doi.org\/10.1007\/s00236-026-00522-5","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,24]]},"assertion":[{"value":"3 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"9"}}