Removing nondeterminism in constant height pushdown automata
| Autor: | Beatrice Palano, Carlo Mereghetti, Zuzana Bednárová, Viliam Geffert |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Nested word Deterministic context-free language Deterministic context-free grammar Context-free language Pushdown automaton Nonlinear Sciences::Cellular Automata and Lattice Gases Embedded pushdown automaton Computer Science Applications Theoretical Computer Science Deterministic pushdown automaton Combinatorics Computational Theory and Mathematics Computer Science::Logic in Computer Science Two-way deterministic finite automaton Computer Science::Formal Languages and Automata Theory Information Systems Mathematics |
| Zdroj: | Information and Computation. 237:257-267 |
| ISSN: | 0890-5401 |
| DOI: | 10.1016/j.ic.2014.03.002 |
| Popis: | We study the descriptional cost of removing nondeterminism in constant height pushdown automata-i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constant height nondeterministic pushdown automaton into an equivalent deterministic device. Moreover, we prove that such a double-exponential blow-up cannot be avoided by certifying its optimality. As a direct consequence, we get that eliminating nondeterminism in classical finite state automata is single-exponential even with the help of a constant height pushdown store. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect