Pebble alternating tree-walking automata and their recognizing power

Muzamel Loránd: Pebble alternating tree-walking automata and their recognizing power. In: Acta cybernetica, (18) 3. pp. 427-450. (2008)

[thumbnail of Muzamel_2008_ActaCybernetica.pdf]
Cikk, tanulmány, mű

Download (238kB) | Preview


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:
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

Actions (login required)

View Item View Item