2011/10/12 by Tony Tan, Tan, Tony
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #F.1.1 #F.4.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Machine Learning and Algorithms #cs.FL #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1110.2776
openalex publication_date 2011/10/12 · arxiv created 2012/04/10 · arxiv updated 2012/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let D denote an infinite alphabet -- a set that consists of infinitely many symbols. A word w = a0 b0 a1 b1 ... an bn 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 = a0 b0 ... an bn is in 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. Based on this result, we establish a number of previously unknown relations among some classes of languages over infinite alphabets.