Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/14816

Title: Graph Reachability and Pebble Automata over Infinite Alphabets
Authors: Tan, Tony
Issue Date: 2013
Citation: ACM Transactions on Computational Logic, 14 (3), (Art. N° 19)
Abstract: Let D denote an infinite alphabet – a set that consists of infinitely many symbols. A word w = a0b0a1b1 · · ·anbn of even length over D can be viewed as a directed graph Gw whose vertices are the symbols that appear in w, and the edges are (a0, b0), (a1, b1), . . . , (an, bn). For a positive integer m, define a language Rm such that a word w = a0b0 · · ·anbn ∈ Rm if and only if there is a path in the graph Gw of length ≤ m from the vertex a0 to the vertex bn. We establish the following hierarchy theorem for pebble automata over infinite alphabet. For every positive integer k, (i) there exists a k-pebble automaton that accepts the language R2k−1 ; (ii) there is no k-pebble automaton that accepts the language R2k+1−2 . Using this fact, we establish the following main results in this paper: (a) a strict hierarchy of the pebble automata languages based on the number of pebbles; (b) the separation of monadic second order logic from the pebble automata languages; (c) the separation of one-way deterministic register automata languages from pebble automata languages.
Notes: Reprint Address: Tan, T (reprint author) - Hasselt Univ, Diepenbeek, Belgium. E-mail Addresses:ptony.tan@gmail.com
URI: http://hdl.handle.net/1942/14816
DOI: 10.1145/2499937.2499940
ISI #: 000323892900003
ISSN: 1529-3785
Category: A1
Type: Journal Contribution
Validation: ecoom, 2014
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
published version326.74 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.