  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 in 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 R_{2^k-1}; (ii) there is no k-pebble
automaton that accepts the language R_{2^{k+1} - 2}. Based on this result, we
establish a number of previously unknown relations among some classes of
languages over infinite alphabets.
