State Trade-Offs in Unranked Tree Automata

DOI10.1007/978-3-642-22600-7_21zbMath1341.68106OpenAlexW124609046MaRDI QIDQ5200097

Kai Salomaa, Xiaoxue Piao

Publication date: 29 July 2011

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22600-7_21

zbMATH Keywords

tree automatastate complexityunranked treesdeterminism and nondeterminism

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

State Complexity of Kleene-Star Operations on Trees ⋮ State complexity of the concatenation of regular tree languages ⋮ Lower bounds for the size of deterministic unranked tree automata

Cites Work

• Unnamed Item
• Automata for XML -- a survey
• On the minimization of XML schemas and tree automata for unranked trees
• Operational state complexity of nested word automata
• Descriptional Complexity of Unambiguous Nested Word Automata
• Transformations Between Different Models of Unranked Bottom-Up Tree Automata
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• A Second Course in Formal Languages and Automata Theory
• Descriptional and Computational Complexity of Finite Automata
• Maximizing the Product of Summands; Minimizing the Sum of Factors
• Fundamentals of Computation Theory
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Rewriting Techniques and Applications

This page was built for publication: State Trade-Offs in Unranked Tree Automata