State complexity of subtree-free regular tree languages

DOI10.1007/978-3-642-39310-5_8MaRDI QIDQ2843085zbMATH OpenOpenAlexFDO

Authors Hae-Sung Eom, Yo-Sub Han, Sang-Ki Ko

Publication date 9 August 2013

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-39310-5_8

zbMATH Keywords

state complexitybasic operationsdeterministic ranked tree automatasubtree-free regular tree language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Operational state complexity of subtree-free regular tree languages
• State complexity of the concatenation of regular tree languages
• State complexity of regular tree languages for tree matching
• State complexity of regular tree languages for tree pattern matching
• State complexity of Kleene-star operations on regular tree languages

Cited in

(8)

• State complexity of projection and quotient on unranked trees
• On state complexity of finite word and tree languages
• State complexity of \(k\)-parallel tree concatenation
• Bounded repairability for regular tree languages
• State complexity of regular tree languages for tree matching
• State complexity of regular tree languages for tree pattern matching
• Operational state complexity of subtree-free regular tree languages
• State complexity of Kleene-star operations on regular tree languages

This page was built for publication: State complexity of subtree-free regular tree languages

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