Graph Reachability and Pebble Automata over Infinite Alphabets
Graph Reachability and Pebble Automata over Infinite Alphabets
复制标题
DOI：
10.1145/2499937.2499940
复制
发表时间：
2009-08
期刊：
影响因子：
--
通讯作者：
Tony Tan
中科院分区：
文献类型：
--
作者：
Tony Tan
我们研究了无限字母上的图可达性问题。也就是说，我们看一个偶数长度的单词，长度为0。无限字母上的b_n作为有向图，其符号出现在a0 b0中…n为顶点，（a0, b0），…，（an, bn）作为边。我们证明了对于任意正整数k， k卵石足以识别从顶点a0到顶点bn的长度为2^k-1的路径的存在性，但不足以识别从顶点a0到顶点bn的长度为2^{k+1} - 2的路径的存在性。在此基础上，我们建立了若干类语言在无限字母上的关系。
We study the graph reachability problem as a language over an infinite alphabet. Namely, we view a word of even lengtha0 b0 ... an b_n over an infinite alphabet as a directed graph with the symbols that appear in a0 b0 ... an bn 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 2^k-1 from the vertex a0 to the vertex bn, but are not sufficient for recognizing the existence of a path of length 2^{k+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.