Operational state complexity of nested word automata

DOI10.1016/J.TCS.2009.05.002MaRDI QIDQ2271464zbMATH OpenOpenAlexFDO

Authors Xiaoxue Piao, 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.05.002

zbMATH Keywords

finite automatastate complexitynested wordslanguage operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State Complexity of Nested Word Automata
• Nondeterministic state complexity of nested word automata
• scientific article; zbMATH DE number 1962776
• State complexity of partial word finite automata
• State complexity of unambiguous operations on finite automata
• State complexity of operations on input-driven pushdown automata
• State complexity of operations on input-driven pushdown automata
• Operational state complexity of unary NFAs with finite nondeterminism
• scientific article; zbMATH DE number 7315100
• State complexity of unambiguous operations on deterministic finite automata

Cites work

• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 2068876 (Why is no real title available?)
• scientific article; zbMATH DE number 2182451 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A lower bound technique for the size of nondeterministic finite automata
• Adding Nesting Structure to Words
• Adding nesting structure to words
• Automata for XML -- a survey
• Automata, Languages and Programming
• Descriptional complexity of machines with limited resources
• Deterministic Caterpillar Expressions
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Intersection and union of regular languages and state complexity
• Marrying Words and Trees
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• Nondeterministic state complexity of nested word automata
• On the minimization of XML schemas and tree automata for unranked trees
• On the state complexity of reversals of regular languages
• Operational state complexity of nested word automata
• Regularity Problems for Visibly Pushdown Languages
• State Complexity of Nested Word Automata
• State complexity of regular languages
• Streaming tree automata
• Typechecking for XML transformers

Cited in

(19)

• Additive number theory via automata theory
• Nondeterministic state complexity of nested word automata
• When input-driven pushdown automata meet reversiblity
• State complexity of the concatenation of regular tree languages
• Edit distance neighbourhoods of input-driven pushdown automata
• State complexity of the quotient operation on input-driven pushdown automata
• Edit distance neighbourhoods of input-driven pushdown 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 unambiguous nested word automata
• State trade-offs in unranked tree automata
• Operational state complexity of nested word automata
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Descriptional complexity of input-driven pushdown automata
• Limitations of lower bound methods for deterministic nested word automata
• State Complexity of Nested Word Automata
• Further closure properties of input-driven pushdown automata
• State complexity of union and intersection on graph-walking automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2271464)