Pebble alternating tree-walking automata and their recognizing power

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

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

Download (238kB)

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
Event Title: Conference for PhD Students in Computer Science, 5., 2006, Szeged
Journal or Publication Title: Acta cybernetica
Date: 2008
Volume: 18
Number: 3
Page Range: pp. 427-450
ISSN: 0324-721X
Language: angol
Uncontrolled Keywords: Természettudomány, Informatika
Additional Information: Bibliogr.: p. 448-450.; Abstract
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2018. Jun. 05. 14:33
URI: http://acta.bibl.u-szeged.hu/id/eprint/12828

Actions (login required)

View Item View Item