Descriptional Complexity of Input-Driven Pushdown Automata
From MaRDI portal
Publication:3166952
DOI10.1007/978-3-642-31644-9_13zbMath1367.68176OpenAlexW3756466MaRDI QIDQ3166952
Xiaoxue Piao, Kai Salomaa, Alexander Okhotin
Publication date: 1 November 2012
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-31644-9_13
Related Items (3)
State complexity of operations on input-driven pushdown automata ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ On the determinization of event-clock input-driven pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Descriptional and computational complexity of finite automata -- a survey
- Limitations of lower bound methods for deterministic nested word automata
- A lower bound technique for the size of nondeterministic finite automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- Streaming tree automata
- An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages
- Finite automata and unary languages
- Tree transducers, L systems, and two-way machines
- Succinct representation of regular languages by Boolean automata
- Intersection and union of regular languages and state complexity
- The state complexities of some basic operations on regular languages
- Simulating finite automata with context-free grammars.
- Nondeterministic state complexity of nested word automata
- Operational state complexity of nested word automata
- Optimal Simulations between Unary Automata
- Descriptional Complexity of Unambiguous Nested Word Automata
- Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages
- State Complexity of Operations on Input-Driven Pushdown Automata
- Adding nesting structure to words
- Height-Deterministic Pushdown Automata
- Minimizing Variants of Visibly Pushdown Automata
- On the State Complexity of Operations on Two-Way Finite Automata
- A Second Course in Formal Languages and Automata Theory
- Visibly pushdown languages
- Unambiguous Finite Automata over a Unary Alphabet
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- On the Expressive Power of 2-Stack Visibly Pushdown Automata
- On the Succinctness of Different Representations of Languages
- Parallel and two-way automata on directed ordered acyclic graphs
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet
- The tree width of auxiliary storage
- 2-Visibly Pushdown Automata
- 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
This page was built for publication: Descriptional Complexity of Input-Driven Pushdown Automata
