LIPIcs.FSTTCS.2013.413.pdf
- Filesize: 450 kB
- 12 pages
Document
On Infinite Words Determined by Stack Automata
Author
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2013-12-10
Cite As Get BibTex
Tim Smith. On Infinite Words Determined by Stack Automata. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 413-424, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.FSTTCS.2013.413
Abstract
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.
Subject Classification
Keywords
- stack automaton
- infinite word
- pumping lemma
- prefix language
- multihead finite automaton
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads