Limitations of lower bound methods for deterministic nested word automata
From MaRDI portal
Publication:553328
DOI10.1016/j.ic.2010.11.021zbMath1230.68136MaRDI QIDQ553328
Publication date: 27 July 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2010.11.021
68Q45: Formal languages and automata
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Descriptional complexity of unambiguous input-driven pushdown automata, Additive number theory via automata theory, State complexity of operations on input-driven pushdown automata, Descriptional Complexity of Input-Driven Pushdown Automata, Sums of Palindromes: an Approach via Automata
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- State complexity of basic language operations combined with reversal
- Lower bounds for the transition complexity of NFAs
- Streaming tree automata
- Efficient inclusion checking for deterministic tree automata and XML schemas
- Intersection and union of regular languages and state complexity
- State complexity of some operations on binary regular languages
- Nondeterministic state complexity of nested word automata
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Operational state complexity of nested word automata
- Transformations Between Different Models of Unranked Bottom-Up Tree Automata
- Adding nesting structure to words
- Minimizing Variants of Visibly Pushdown Automata
- A Second Course in Formal Languages and Automata Theory
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Adding Nesting Structure to Words
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Descriptional and Computational Complexity of Finite Automata
- State Complexity of Nested Word Automata
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
- On the State Minimization of Nondeterministic Finite Automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Automata, Languages and Programming
- Minimization, Learning, and Conformance Testing of Boolean Programs
