Descriptional complexity of input-driven pushdown automata
From MaRDI portal
Recommendations
- Descriptional complexity of unambiguous input-driven pushdown automata
- Towards exact state complexity bounds for input-driven pushdown automata
- Input-Driven Pushdown Automata with Limited Nondeterminism
- State complexity of operations on input-driven pushdown automata
- State complexity of operations on input-driven pushdown automata
Cites work
- scientific article; zbMATH DE number 3885334 (Why is no real title available?)
- scientific article; zbMATH DE number 3876636 (Why is no real title available?)
- scientific article; zbMATH DE number 3696500 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3353192 (Why is no real title available?)
- 2-Visibly Pushdown Automata
- A Second Course in Formal Languages and Automata Theory
- A lower bound technique for the size of nondeterministic finite automata
- Adding nesting structure to words
- An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages
- Automata, Languages and Programming
- Comparing linear conjunctive languages to subfamilies of the context-free languages
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- Descriptional and computational complexity of finite automata -- a survey
- Descriptional complexity of unambiguous nested word automata
- Finite automata and unary languages
- Height-Deterministic Pushdown Automata
- Intersection and union of regular languages and state complexity
- Limitations of lower bound methods for deterministic nested word automata
- Mathematical Foundations of Computer Science 2005
- Minimizing Variants of Visibly Pushdown Automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Nondeterministic state complexity of nested word automata
- Nonterminal complexity of some operations on context-free languages
- On the Expressive Power of 2-Stack Visibly Pushdown Automata
- On the State Complexity of Operations on Two-Way Finite Automata
- On the Succinctness of Different Representations of Languages
- Operational state complexity of nested word automata
- Optimal simulations between unary automata
- Parallel and two-way automata on directed ordered acyclic graphs
- Partial orders on words, minimal elements of regular languages, and state complexity
- Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
- Simulating finite automata with context-free grammars.
- State complexity of operations on input-driven pushdown automata
- State complexity of operations on two-way deterministic finite automata over a unary alphabet
- Streaming tree automata
- Succinct representation of regular languages by Boolean automata
- The state complexities of some basic operations on regular languages
- The tree width of auxiliary storage
- Tree transducers, L systems, and two-way machines
- Unambiguous finite automata over a unary alphabet
- Visibly pushdown languages
Cited in
(13)- Towards exact state complexity bounds for input-driven pushdown automata
- Input-Driven Pushdown Automata with Limited Nondeterminism
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- Descriptional complexity of unambiguous input-driven pushdown automata
- State complexity of operations on input-driven pushdown automata
- On the determinization of event-clock input-driven pushdown automata
- Descriptional complexity of unambiguous nested word automata
- Input-driven stack automata
- State complexity of operations on input-driven pushdown automata
- Descriptional Complexity of Operations on Alternating and Boolean Automata
- Improved upper bounds for determinizing NIDPDAs with limited nondeterminism
- Limited nondeterminism of input-driven pushdown automata: decidability and complexity
- Exact descriptional complexity of determinization of input-driven pushdown automata
This page was built for publication: Descriptional complexity of input-driven pushdown automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3166952)
