State complexity of Kleene-star operations on regulat tree languages
The concatenation of trees can be defined either as a sequential or a parallel operation, and the corresponding iterated operation gives an extension of Kleene-star to tree languages. Since the sequential tree concatenation is not associative, we get two essentially different iterated sequential con...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2015
|
| Sorozat: | Acta cybernetica
22 No. 2 |
| Kulcsszavak: | Matematikai nyelvészet |
| Tárgyszavak: | |
| doi: | 10.14232/actacyb.22.2.2015.11 |
| Online Access: | http://acta.bibl.u-szeged.hu/36211 |
| Tartalmi kivonat: | The concatenation of trees can be defined either as a sequential or a parallel operation, and the corresponding iterated operation gives an extension of Kleene-star to tree languages. Since the sequential tree concatenation is not associative, we get two essentially different iterated sequential concatenation operations that we call the bottom-up star and top-down star operation, respectively. We establish that the worst-case state complexity of bottom-up star is (n + 3/2) · 2 n−1. The bound differs by an order of magnitude from the corresponding result for string languages. The state complexity of top-down star is similar as in the string case. We consider also the state complexity of the star of the concatenation of a regular tree language with the set of all trees. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 403-422 |
| ISSN: | 0324-721X |