State Complexity of Nested Word Automata

DOI10.1007/978-3-642-00982-2_5zbMath1234.68238OpenAlexW1547232601MaRDI QIDQ3618567

Kai Salomaa

Publication date: 2 April 2009

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00982-2_5

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Limitations of lower bound methods for deterministic nested word automata ⋮ Operational state complexity of nested word automata

Uses Software

• VPAlib

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Streaming tree automata
• Intersection and union of regular languages and state complexity
• General varieties of tree languages
• State complexity of some operations on binary regular languages
• Nondeterministic state complexity of nested word automata
• Operational state complexity of nested word automata
• Transition complexity of language operations
• Marrying Words and Trees
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• Minimizing Variants of Visibly Pushdown Automata
• Adding Nesting Structure to Words
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• First-Order and Temporal Logics for Nested Words
• 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

This page was built for publication: State Complexity of Nested Word Automata