@inproceedings{3464c8553e2b4d0dbff9016cf97e0ec9,
title = "State complexity of subtree-free regular tree languages",
abstract = "We introduce subtree-free regular tree languages that often appear in XML schemas and investigate the state complexity of basic operations on subtree-free regular tree languages. The state complexity of an operation for regular tree languages is the number of states that are sufficient and necessary in the worst-case for the minimal deterministic ranked tree automaton that accepts the tree language obtained from the operation. We establish the precise state complexity of (sequential, parallel) concatenation, (bottom-up, top-down) star, intersection and union for subtree-free regular tree languages.",
keywords = "basic operations, deterministic ranked tree automata, state complexity, subtree-free regular tree language",
author = "Eom, {Hae Sung} and Han, {Yo Sub} and Ko, {Sang Ki}",
year = "2013",
doi = "10.1007/978-3-642-39310-5_8",
language = "English",
isbn = "9783642393099",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "66--77",
booktitle = "Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings",
note = "15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013 ; Conference date: 22-07-2013 Through 25-07-2013",
}