2026-07-23T01:18:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4369 2024-03-06T10:35:00Z ddc:004 open_access

On Infinite Words Determined by Stack Automata Smith, Tim stack automaton infinite word pumping lemma prefix language multihead finite automaton We characterize the infinite words determined by one-way stack automata. An infinite language L determines an infinite word alpha if every string in L is a prefix of alpha. If L is regular or context-free, it is known that alpha must be ultimately periodic. We extend this result to the class of languages recognized by one-way nondeterministic checking stack automata (1-NCSA). We then consider stronger classes of stack automata and show that they determine a class of infinite words which we call multilinear. We show that every multilinear word can be written in a form which is amenable to parsing. Finally, we consider the class of one-way multihead deterministic finite automata (1:multi-DFA). We show that every multilinear word can be determined by some 1:multi-DFA, but that there exist infinite words determined by 1:multi-DFA which are not multilinear. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tim Smith 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.413 urn:nbn:de:0030-drops-43692 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.413 eng https://creativecommons.org/licenses/by/3.0/legalcode