Muzamel Loránd: Pebble alternating tree-walking automata and their recognizing power. In: Acta cybernetica, (18) 3. pp. 427-450. (2008)
Előnézet |
Cikk, tanulmány, mű
Muzamel_2008_ActaCybernetica.pdf Letöltés (238kB) | Előnézet |
Absztrakt (kivonat)
Pebble tree-walking automata with alternation were first investigated by Milo, Suciu and Vianu (2003), who showed that tree languages recognized by these devices are exactly the regular tree languages. We strengthen this by proving the same result for pebble automata with "strong pebble handling" which means that pebbles can be lifted independently of the position of the reading head and without moving the reading head. Then we make a comparison among some restricted versions of these automata. We will show that the deterministic and non-looping pebble alternating tree-walking automata are strictly less powerful than their nondeterministic counterparts, i.e., they do not recognize all the regular tree languages. Moreover, there is a proper hierarchy of recognizing capacity of deterministic and non-looping n-pebble alternating tree-walking automata with respect to the number of pebbles, i.e., for each n ≥ 0, deterministic and non-looping (n+1)-pebble alternating tree-walking automata are more powerful than their n-pebble counterparts.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 2008 |
| Kötet: | 18 |
| Szám: | 3 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 427-450 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Konferencia neve: | Conference for PhD Students in Computer Science (5.) (2006) (Szeged) |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/38525/ |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Megjegyzések: | Bibliogr.: p. 448-450. ; összefoglalás angol nyelven |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.02. Számítás- és információtudomány |
| Feltöltés dátuma: | 2016. okt. 15. 12:25 |
| Utolsó módosítás: | 2022. jún. 16. 15:22 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/12828 |
 |
Tétel nézet |
