Han Yo-Sub; Ko Sang-Ki; Piao Xiaoxue; Salomaa Kai: State complexity of Kleene-star operations on regulat tree languages. In: Acta cybernetica, (22) 2. pp. 403-422. (2015)
Előnézet |
Cikk, tanulmány, mű
actacyb_22_2_2015_11.pdf Letöltés (472kB) | Előnézet |
Absztrakt (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.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 2015 |
| Kötet: | 22 |
| Szám: | 2 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 403-422 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/38540/ |
| DOI: | 10.14232/actacyb.22.2.2015.11 |
| Kulcsszavak: | Matematikai nyelvészet |
| Megjegyzések: | Bibliogr.: p. 421-422. ; összefoglalás angol nyelven |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.01. Matematika |
| Feltöltés dátuma: | 2016. okt. 17. 10:36 |
| Utolsó módosítás: | 2022. jún. 20. 10:23 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/36211 |
 |
Tétel nézet |
