Nondeterministic state complexity of nested word automata

DOI10.1016/j.tcs.2009.01.004zbMath1173.68034OpenAlexW2061265323MaRDI QIDQ2271435

Yo-Sub Han, Kai Salomaa

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

zbMATH Keywords

nondeterminismstate complexitylanguage operationsfinite automata on nested words

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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