Muzamel Loránd: Pebble alternating tree-walking automata and their recognizing power. In: Acta cybernetica, (18) 3. pp. 427-450. (2008)
Preview |
Cikk, tanulmány, mű
Muzamel_2008_ActaCybernetica.pdf Download (238kB) | Preview |
Abstract
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.
| Item Type: | Article |
|---|---|
| Journal or Publication Title: | Acta cybernetica |
| Date: | 2008 |
| Volume: | 18 |
| Number: | 3 |
| ISSN: | 0324-721X |
| Page Range: | pp. 427-450 |
| Language: | English |
| Place of Publication: | Szeged |
| Event Title: | Conference for PhD Students in Computer Science (5.) (2006) (Szeged) |
| Related URLs: | http://acta.bibl.u-szeged.hu/38525/ |
| Uncontrolled Keywords: | Számítástechnika, Kibernetika |
| Additional Information: | Bibliogr.: p. 448-450. ; összefoglalás angol nyelven |
| Subjects: | 01. Natural sciences 01. Natural sciences > 01.02. Computer and information sciences |
| Date Deposited: | 2016. Oct. 15. 12:25 |
| Last Modified: | 2022. Jun. 16. 15:22 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/12828 |
Actions (login required)
 |
View Item |
