Nondeterministic state complexity of nested word automata
From MaRDI portal
Publication:2271435
DOI10.1016/j.tcs.2009.01.004zbMath1173.68034OpenAlexW2061265323MaRDI QIDQ2271435
Publication date: 7 August 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.01.004
Related Items
Descriptional Complexity of Input-Driven Pushdown Automata ⋮ State complexity of operations on input-driven pushdown automata ⋮ When input-driven pushdown automata meet reversiblity ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ Additive number theory via automata theory ⋮ Further closure properties of input-driven pushdown automata ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ Operational state complexity of nested word automata ⋮ State Complexity of the Quotient Operation on Input-Driven Pushdown Automata ⋮ State Complexity of Nested Word Automata ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties ⋮ Sums of Palindromes: an Approach via Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound technique for the size of nondeterministic finite automata
- Lower bounds for the transition complexity of NFAs
- Intersection and union of regular languages and state complexity
- State complexity of some operations on binary regular languages
- Communication complexity method for measuring nondeterminism in finite automata
- Adding nesting structure to words
- Adding Nesting Structure to Words
- Descriptional Complexity of Nondeterministic Finite Automata
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Automata, Languages and Programming
- Minimization, Learning, and Conformance Testing of Boolean Programs