TONY TAN2020-05-042020-05-04200910436871https://scholars.lib.ntu.edu.tw/handle/123456789/490132https://www.scopus.com/inward/record.uri?eid=2-s2.0-70350610961&doi=10.1109%2fLICS.2009.23&partnerID=40&md5=76f400aa83eca33121f032aea70f394fWe study the graph reachability problem as a language over an infinite alphabet. Namely, we view a word of even length a0b0 · · · anbn over an infinite alphabet as a directed graph with the symbols that appear in a0b0 ... anbn as the vertices and (a0, b0), . . . , (an, bn) as the edges. We prove that for any positive integer k, k pebbles are sufficient for recognizing the existence of a path of length 2k - 1 from the vertex a0 to the vertex bn, but are not sufficient for recognizing the existence of a path of length 2k+1-2 from the vertex a0 to the vertex bn. Based on this result, we establish a number of relations among some classes of languages over infinite alphabets. © 2009 IEEE.Graph reachability; Infinite alphabets; Pebble automataDirected graphs; Graph reachability; Infinite alphabets; Pebble automata; Positive integers; Reachability; Reachability problem; Computer science; Linguistics; Query languages; Robots; Translation (languages); Graph theoryconference paper10.1109/LICS.2009.232-s2.0-70350610961https://doi.org/10.1109/LICS.2009.23