State Complexity of Kleene-Star Operations on Trees

DOI10.1007/978-3-642-27654-5_30zbMath1353.68171OpenAlexW2098375093MaRDI QIDQ2891328

Xiaoxue Piao, Kai Salomaa

Publication date: 15 June 2012

Published in: Computation, Physics and Beyond (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-27654-5_30

zbMATH Keywords

tree automatastate complexityiterated concatenation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

State complexity of the concatenation of regular tree languages ⋮ Lower bounds for the size of deterministic unranked tree automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Finite state complexity
• Automata for XML -- a survey
• On the minimization of XML schemas and tree automata for unranked trees
• State complexity of power
• General varieties of tree languages
• The state complexities of some basic operations on regular languages
• State complexity of combined operations
• STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY
• Undecidability of the State Complexity of Composed Regular Operations
• Nondeterminism Is Essential in Small 2FAs with Few Reversals
• Transformations Between Different Models of Unranked Bottom-Up Tree Automata
• Transition Complexity of Incomplete DFAs
• On the State Complexity of Operations on Two-Way Finite Automata
• A Second Course in Formal Languages and Automata Theory
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal
• State Trade-Offs in Unranked Tree Automata
• Fundamentals of Computation Theory

This page was built for publication: State Complexity of Kleene-Star Operations on Trees