State complexity of the concatenation of regular tree languages

DOI10.1016/J.TCS.2011.12.048zbMath1238.68079OpenAlexW2063737596MaRDI QIDQ418803

Kai Salomaa, Xiaoxue Piao

Publication date: 30 May 2012

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

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

zbMATH Keywords

lower boundstree automatastate complexitysequential and parallel concatenation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

Operational State Complexity of Subtree-Free Regular Tree Languages ⋮ State Complexity of Regular Tree Languages for Tree Matching ⋮ Operational Accepting State Complexity: The Unary and Finite Case

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Automata for XML -- a survey
• On the minimization of XML schemas and tree automata for unranked trees
• State complexity of basic language operations combined with reversal
• Decimations of languages and state complexity
• The state complexities of some basic operations on regular languages
• Typechecking for XML transformers
• State complexity of some operations on binary regular languages
• Estimation of state complexity of combined operations
• Operational state complexity of nested word automata
• State Complexity of Kleene-Star Operations on Trees
• Undecidability of the State Complexity of Composed Regular Operations
• State Complexity of Operations on Input-Driven Pushdown Automata
• Transformations Between Different Models of Unranked Bottom-Up Tree Automata
• Transition Complexity of Incomplete DFAs
• Adding nesting structure to words
• A Second Course in Formal Languages and Automata Theory
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• State Trade-Offs in Unranked Tree Automata

This page was built for publication: State complexity of the concatenation of regular tree languages