Descriptional complexity of unambiguous input-driven pushdown automata
From MaRDI portal
Publication:484313
DOI10.1016/j.tcs.2014.11.015zbMath1318.68111OpenAlexW2079567772MaRDI QIDQ484313
Kai Salomaa, Alexander Okhotin
Publication date: 6 January 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.11.015
nondeterminismdescriptional complexityunambiguityinput-driven pushdown automatanested word automatavisibly pushdown automata
Related Items
State complexity of operations on input-driven pushdown automata, A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct, Further closure properties of input-driven pushdown automata, State Complexity of the Quotient Operation on Input-Driven Pushdown Automata, Edit distance neighbourhoods of input-driven pushdown automata, Edit distance neighbourhoods of input-driven pushdown automata, Unambiguity in Automata Theory, Input-driven pushdown automata on well-nested infinite strings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unambiguous finite automata over a unary alphabet
- Descriptional and computational complexity of finite automata -- a survey
- Limitations of lower bound methods for deterministic nested word automata
- Streaming tree automata
- An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages
- On the relation between ambiguity and nondeterminism in finite automata
- Intersection and union of regular languages and state complexity
- State complexity of some operations on binary regular languages
- Communication complexity method for measuring nondeterminism in finite automata
- Nondeterministic state complexity of nested word automata
- Operational state complexity of nested word automata
- Complementing two-way finite automata
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages
- State Complexity of Operations on Input-Driven Pushdown Automata
- Descriptional Complexity of Input-Driven Pushdown Automata
- Adding nesting structure to words
- Minimizing Variants of Visibly Pushdown Automata
- A Second Course in Formal Languages and Automata Theory
- Visibly pushdown languages
- On the Expressive Power of 2-Stack Visibly Pushdown Automata
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
- Mathematical Foundations of Computer Science 2005
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Automata, Languages and Programming
