Graph Reachability and Pebble Automata over Infinite Alphabets

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.