Operational state complexity of nested word automata

DOI10.1016/j.tcs.2009.05.002zbMath1176.68108OpenAlexW1996644214MaRDI QIDQ2271464

Kai Salomaa, Xiaoxue Piao

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.05.002

zbMATH Keywords

finite automatastate complexitynested wordslanguage operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (17)

Descriptional Complexity of Input-Driven Pushdown Automata ⋮ State complexity of operations on input-driven pushdown automata ⋮ State complexity of the concatenation of regular tree languages ⋮ 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 Trade-Offs in Unranked Tree 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 ⋮ State complexity of union and intersection on graph-walking 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the state complexity of reversals of regular languages
• A lower bound technique for the size of nondeterministic finite automata
• Automata for XML -- a survey
• On the minimization of XML schemas and tree automata for unranked trees
• Streaming tree automata
• Intersection and union of regular languages and state complexity
• Typechecking for XML transformers
• Nondeterministic state complexity of nested word automata
• Operational state complexity of nested word automata
• Adding nesting structure to words
• Marrying Words and Trees
• Deterministic Caterpillar Expressions
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• Adding Nesting Structure to Words
• State Complexity of Nested Word Automata
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Regularity Problems for Visibly Pushdown Languages
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Automata, Languages and Programming

This page was built for publication: Operational state complexity of nested word automata