Graph Reachability and Pebble Automata over Infinite Alphabets

Details Graph Reachability and Pebble Automata over Infinite Alphabets Graph Reachability and Pebble Automata over Infinite Alphabets

2011-10-12

arxiv.org/abs/1110.2776v2

Computer Science

Formal Languages and Automata Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Graph Reachability and Pebble Automata over Infinite Alphabets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph Reachability and Pebble Automata over Infinite Alphabets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Reachability and Pebble Automata over Infinite Alphabets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-634920