Abstract
We introduce subtree-free regular tree languages that are closely related to 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.
| Original language | English |
|---|---|
| Pages (from-to) | 705-724 |
| Number of pages | 20 |
| Journal | International Journal of Foundations of Computer Science |
| Volume | 27 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 2016 Sept 1 |
Bibliographical note
Publisher Copyright:© 2016 World Scientific Publishing Company.
All Science Journal Classification (ASJC) codes
- Computer Science (miscellaneous)