Limitations of lower bound methods for deterministic nested word automata
From MaRDI portal
Publication:553328
DOI10.1016/J.IC.2010.11.021zbMATH Open1230.68136OpenAlexW2066278264MaRDI QIDQ553328FDOQ553328
Authors: Kai Salomaa 
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
Recommendations
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Adding nesting structure to words
- Streaming tree automata
- A Second Course in Formal Languages and Automata Theory
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Title not available (Why is that?)
- Transformations between different models of unranked bottom-up tree automata
- Efficient inclusion checking for deterministic tree automata and XML schemas
- State complexity of some operations on binary regular languages
- State complexity of basic language operations combined with reversal
- On the State Minimization of Nondeterministic Finite Automata
- Intersection and union of regular languages and state complexity
- 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
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Nondeterministic state complexity of nested word automata
- Minimizing Variants of Visibly Pushdown Automata
- Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
- Automata, Languages and Programming
- Descriptional and Computational Complexity of Finite Automata
- Adding Nesting Structure to Words
- State Complexity of Nested Word Automata
- Title not available (Why is that?)
- Minimization, Learning, and Conformance Testing of Boolean Programs
- Lower bounds for the transition complexity of NFAs
Cited In (9)
- A Nontrivial Lower Bound for an NP Problem on Automata
- Additive number theory via automata theory
- Nondeterministic state complexity of nested word automata
- Sums of Palindromes: an Approach via Automata
- Descriptional complexity of unambiguous input-driven pushdown automata
- State complexity of operations on input-driven pushdown automata
- Descriptional complexity of input-driven pushdown automata
- On limitations of structured (deterministic) DNNFs
- State Complexity of Nested Word Automata
Uses Software
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)
