Lower bounds for the size of deterministic unranked tree automata

DOI10.1016/J.TCS.2012.03.043MaRDI QIDQ714828zbMATHOpenAlexFDO

Authors 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 automatadeterminizationstate complexitytree languagesunranked trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State trade-offs in unranked tree automata
• Fundamentals of Computation Theory
• Transformations between different models of unranked bottom-up tree automata
• scientific article; zbMATH DE number 7315100
• scientific article; zbMATH DE number 7315101

Cites work

• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A Second Course in Formal Languages and Automata Theory
• A lower bound technique for the size of nondeterministic finite automata
• Automata for XML -- a survey
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity of machines with limited resources
• Estimation of state complexity of combined operations
• Fundamentals of Computation Theory
• Intersection and union of regular languages and state complexity
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• On the minimization of XML schemas and tree automata for unranked trees
• State complexity of Kleene-star operations on trees
• State trade-offs in unranked tree automata
• Transformations between different models of unranked bottom-up tree automata
• Typechecking for XML transformers
• Unambiguous finite automata over a unary alphabet
• Undecidability of the state complexity of composed regular operations

Cited in

(6)

• Unranked Tree Automata with Sibling Equalities and Disequalities
• Transformations between different models of unranked bottom-up tree automata
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 7362732 (Why is no real title available?)
• State trade-offs in unranked tree automata
• scientific article; zbMATH DE number 7315100 (Why is no real title available?)

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

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