Graph Reachability and Pebble Automata over Infinite Alphabets

Let D denote an infinite alphabet - a set that consists of infinitely many symbols. A word w = a(0)b(0)a(1)b(1) ... a(n)b(n) of even length over D can be viewed as a directed graph G(w) whose vertices are the symbols that appear in w, and the edges are (a(0), b(0)), (a(1), b(1)), ... , (a(n), b(n)). For a positive integer m, define a language R-m such that a word w = a(0)b(0) ... a(n)b(n) is an element of R-m if and only if there is a path in the graph G(w) of length <= m from the vertex a(0) to the vertex b(n). 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 article: (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.