Lower bounds for the size of deterministic unranked tree automata

DOI10.1016/j.tcs.2012.03.043zbMath1257.68099OpenAlexW2081745941MaRDI QIDQ714828

Xiaoxue Piao, Kai Salomaa

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.043

zbMATH Keywords

lower boundstree automatastate complexitytree languagesdeterminizationunranked trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• 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
• Intersection and union of regular languages and state complexity
• Typechecking for XML transformers
• Estimation of state complexity of combined operations
• State Complexity of Kleene-Star Operations on Trees
• Undecidability of the State Complexity of Composed Regular Operations
• 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
• Unambiguous Finite Automata over a Unary Alphabet
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• State Trade-Offs in Unranked Tree Automata
• Fundamentals of Computation Theory
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY

This page was built for publication: Lower bounds for the size of deterministic unranked tree automata