Please use this identifier to cite or link to this item:
Title: Graph Reachability and Pebble Automata over Infinite Alphabets
Authors: TAN, Tony 
Issue Date: 2013
Source: 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
Keywords: Pebble automata; graph reachability; infinite alphabets
Document URI:
ISSN: 1529-3785
e-ISSN: 1557-945X
DOI: 10.1145/2499937.2499940
ISI #: 000323892900003
Category: A1
Type: Journal Contribution
Validations: ecoom 2014
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
tan_graph.pdfpublished version326.74 kBAdobe PDFView/Open
Show full item record


checked on Sep 3, 2020


checked on May 21, 2022

Page view(s)

checked on May 26, 2022


checked on May 26, 2022

Google ScholarTM



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