Input-Driven Pushdown Automata on Well-Nested Infinite Strings
| Autor: | Victor L. Selivanov, Alexander Okhotin |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Discrete mathematics
Computer Science::Logic in Computer Science String (computer science) Topological classification Pushdown automaton Characterization (mathematics) Nonlinear Sciences::Cellular Automata and Lattice Gases Computer Science::Formal Languages and Automata Theory Mathematics Automaton |
| Zdroj: | Computer Science – Theory and Applications ISBN: 9783030794156 CSR |
| DOI: | 10.1007/978-3-030-79416-3_21 |
| Popis: | Automata operating on strings of nested brackets, known as input-driven pushdown automata, and also as visibly pushdown automata, have been studied since the 1980s. They were extended to the case of infinite strings by Alur and Madhusudan (“Visibly pushdown languages”, STOC 2004). This paper investigates the properties of these automata under the assumption that a given infinite string is always well-nested. This restriction enables a complete characterization of the corresponding \(\omega \)-languages in terms of classical \(\omega \)-regular languages and input-driven pushdown automata on finite strings. This characterization leads to a determinization construction for these automata, as well as to the first results on their topological classification. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|