{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:10:06Z","timestamp":1750162206527,"version":"3.41.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T00:00:00Z","timestamp":1746230400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T00:00:00Z","timestamp":1746230400000},"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":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We study deterministic tree-walking-storage automata, which are finite-state devices equipped with a tree-like storage. These 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, with the possible moves of the tree pointer corresponding 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. Here we are particularly considering the capacities of deterministic tree-walking-storage automata working in real time. It is shown that even the non-erasing variant can accept rather complicated unary languages as, for example, the language of words whose lengths are powers of two, or the language of words whose lengths are double Fibonacci numbers. Comparing the computational capacities with automata from the classical automata hierarchy, we derive that the family of languages accepted by real-time deterministic (non-erasing) tree-walking-storage automata is located between the regular and the deterministic context-sensitive languages. Moreover, the families are incomparable with the families of context-free and growing context-sensitive languages. It turns out that the devices under consideration accept unary languages in non-erasing mode that cannot be accepted by any classical stack automaton, even in erasing mode and arbitrary time. Basic closure properties of the induced families of languages are shown. In particular, we consider Boolean operations and AFL operations. It turns out that the two families in question have the same properties and, in particular, share all but one of these closure properties with the important family of deterministic context-free languages. Then, we consider the computational capacity of the counterpart to counter- and stack-counter automata, where the set of stack symbols is a singleton. Finally, we explore several decidability problems and show, that even for devices with a single tree symbol, the problems are all non-semidecidable by reductions of non-semidecidable problems of Turing machines.<\/jats:p>","DOI":"10.1007\/s00236-025-00488-w","type":"journal-article","created":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T03:54:14Z","timestamp":1746244454000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic real-time tree-walking-storage automata"],"prefix":"10.1007","volume":"62","author":[{"given":"Martin","family":"Kutrib","sequence":"first","affiliation":[]},{"given":"Uwe","family":"Meyer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,3]]},"reference":[{"key":"488_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. Inform. Control 19, 439\u2013475 (1971). https:\/\/doi.org\/10.1016\/S0019-9958(71)90706-6","journal-title":"Inform. Control"},{"key":"488_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":"488_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":"488_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":"488_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/BF01706072","volume":"6","author":"RV Book","year":"1972","unstructured":"Book, R.V., Ginsburg, S.: Multi-stack-counter languages. Math. Systems Theory 6, 37\u201348 (1972). https:\/\/doi.org\/10.1007\/BF01706072","journal-title":"Math. Systems Theory"},{"key":"488_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/INCO.1997.2681","volume":"141","author":"G Buntrock","year":"1998","unstructured":"Buntrock, G., Otto, F.: Growing context-sensitive languages and Church-Rosser languages. Inform. Comput. 141, 1\u201336 (1998). https:\/\/doi.org\/10.1006\/INCO.1997.2681","journal-title":"Inform. Comput."},{"key":"488_CR7","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/0022-0000(86)90062-0","volume":"33","author":"E Dahlhaus","year":"1986","unstructured":"Dahlhaus, E., Warmuth, M.K.: Membership for growing context-sensitive grammars is polynomial. J. Comput. Syst. Sci. 33, 456\u2013472 (1986). https:\/\/doi.org\/10.1016\/0022-0000(86)90062-0","journal-title":"J. Comput. Syst. Sci."},{"key":"488_CR8","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":"488_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01694011","volume":"2","author":"PC Fischer","year":"1968","unstructured":"Fischer, P.C., Meyer, A.R., Rosenberg, A.L.: Counter machines and counter languages. Math. Systems Theory 2, 265\u2013283 (1968). https:\/\/doi.org\/10.1007\/BF01694011","journal-title":"Math. Systems Theory"},{"key":"488_CR10","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0022-0000(74)80058-9","volume":"8","author":"S Ginsburg","year":"1974","unstructured":"Ginsburg, S., Rose, G.F.: The equivalence of stack counter acceptors and quasi-realtime acceptors. J. Comput. Syst. Sci. 8, 243\u2013269 (1974). https:\/\/doi.org\/10.1016\/S0022-0000(74)80058-9","journal-title":"J. Comput. Syst. Sci."},{"key":"488_CR11","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":"488_CR12","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":"488_CR13","first-page":"29","volume":"3","author":"AV Gladkii","year":"1964","unstructured":"Gladkii, A.V.: On complexity of inference in phase-structure grammars. Algebra I Logika. Sem. 3, 29\u201344 (1964). (in Russian)","journal-title":"Algebra I Logika. Sem."},{"key":"488_CR14","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. Syst. Theory 29, 227\u2013244 (1996). https:\/\/doi.org\/10.1007\/BF01201277","journal-title":"Math. Syst. Theory"},{"key":"488_CR15","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. J. Comput. Syst. Sci. 3, 196\u2013217 (1969). https:\/\/doi.org\/10.1016\/S0022-0000(69)80012-7","journal-title":"J. Comput. Syst. Sci."},{"key":"488_CR16","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":"488_CR17","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":"488_CR18","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 285\u2013306 (1965). https:\/\/doi.org\/10.1090\/S0002-9947-1965-0170805-7","journal-title":"Trans. Amer. Math. Soc."},{"key":"488_CR19","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. J. Comput. Syst. Sci. 1, 166\u2013186 (1967). https:\/\/doi.org\/10.1016\/S0022-0000(67)80013-8","journal-title":"J. Comput. Syst. Sci."},{"key":"488_CR20","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. J. Comput. Syst. Sci. 2, 1\u201312 (1968). https:\/\/doi.org\/10.1016\/S0022-0000(68)80003-0","journal-title":"J. Comput. Syst. Sci."},{"key":"488_CR21","volume-title":"Introduction to automata theory, languages, and computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley, Boston (1979)"},{"key":"488_CR22","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. J. Comput. Syst. Sci. 5, 88\u2013117 (1971). https:\/\/doi.org\/10.1016\/S0022-0000(71)80029-6","journal-title":"J. Comput. Syst. Sci."},{"key":"488_CR23","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. Theor. Comput. Sci. 738, 1\u201312 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.04.024","journal-title":"Theor. Comput. Sci."},{"key":"488_CR24","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":"488_CR25","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":"488_CR26","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":"488_CR27","doi-asserted-by":"publisher","unstructured":"Kutrib, M., Meyer, U.: Deterministic real-time tree-walking-storage automata. In: Nagy, B., Freund, R. (eds.) Non-classical models of automata and applications (NCMA 2023). EPTCS, vol. 388, pp. 48\u201362 (2023) https:\/\/doi.org\/10.4204\/EPTCS.388.7","DOI":"10.4204\/EPTCS.388.7"},{"key":"488_CR28","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":"488_CR29","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":"488_CR30","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":"488_CR31","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/42282.42284","volume":"35","author":"R McNaughton","year":"1988","unstructured":"McNaughton, R., Narendran, P., Otto, F.: Church-Rosser Thue systems and formal languages. J. ACM 35, 324\u2013344 (1988). https:\/\/doi.org\/10.1145\/42282.42284","journal-title":"J. ACM"},{"key":"488_CR32","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"ML Minsky","year":"1961","unstructured":"Minsky, M.L.: Recursive unsolvability of Post\u2019s problem of \u2018tag\u2019 and other topics in the theory of Turing machines. Ann. Math. 74, 437\u2013455 (1961)","journal-title":"Ann. Math."},{"key":"488_CR33","volume-title":"Computation: finite and infinite machines","author":"ML Minsky","year":"1967","unstructured":"Minsky, M.L.: Computation: finite and infinite machines. Prentice-Hall, Upper Saddle River (1967)"},{"key":"488_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/J.IC.2004.09.003","volume":"197","author":"G Niemann","year":"2005","unstructured":"Niemann, G., Otto, F.: The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Inform. Comput. 197, 1\u201321 (2005). https:\/\/doi.org\/10.1016\/J.IC.2004.09.003","journal-title":"Inform. Comput."},{"key":"488_CR35","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 (1969). https:\/\/doi.org\/10.1145\/800169.805419","DOI":"10.1145\/800169.805419"},{"key":"488_CR36","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF02759719","volume":"1","author":"MO Rabin","year":"1963","unstructured":"Rabin, M.O.: Real time computation. Israel J. Math. 1, 203\u2013211 (1963). https:\/\/doi.org\/10.1007\/BF02759719","journal-title":"Israel J. Math."},{"key":"488_CR37","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":"488_CR38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139871495","volume-title":"Catalan numbers","author":"RP Stanley","year":"2015","unstructured":"Stanley, R.P.: Catalan numbers. Cambridge University Press, Cambridge (2015). https:\/\/doi.org\/10.1017\/CBO9781139871495"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00488-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00488-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00488-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T11:42:35Z","timestamp":1750160555000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00488-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,3]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["488"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00488-w","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2025,5,3]]},"assertion":[{"value":"24 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2025","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 they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"21"}}