Limitations of lower bound methods for deterministic nested word automata
From MaRDI portal
Publication:553328
Recommendations
Cites work
- scientific article; zbMATH DE number 1011685 (Why is no real title available?)
- scientific article; zbMATH DE number 2050931 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- A Second Course in Formal Languages and Automata Theory
- Adding Nesting Structure to Words
- Adding nesting structure to words
- Automata, Languages and Programming
- Descriptional and Computational Complexity of Finite Automata
- Efficient inclusion checking for deterministic tree automata and XML schemas
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Intersection and union of regular languages and state complexity
- Lower bounds for the transition complexity of NFAs
- Minimization, Learning, and Conformance Testing of Boolean Programs
- 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
- On the State Minimization of Nondeterministic Finite 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
- Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
- State Complexity of Nested Word Automata
- State complexity of basic language operations combined with reversal
- State complexity of some operations on binary regular languages
- Streaming tree automata
- Transformations between different models of unranked bottom-up tree automata
Cited in
(9)- A Nontrivial Lower Bound for an NP Problem on Automata
- On limitations of structured (deterministic) DNNFs
- Nondeterministic state complexity of nested word automata
- Descriptional complexity of input-driven pushdown automata
- State Complexity of Nested Word Automata
- Additive number theory via automata theory
- Sums of Palindromes: an Approach via Automata
- State complexity of operations on input-driven pushdown automata
- Descriptional complexity of unambiguous input-driven pushdown automata
This page was built for publication: Limitations of lower bound methods for deterministic nested word automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q553328)
