Graph reachability and pebble automata over infinite alphabets

DOI10.1145/2499937.2499940MaRDI QIDQ2946705zbMATHOpenAlexFDO

Authors Tony Tan

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.2776

zbMATH Keywords

graph reachabilityinfinite alphabetspebble automata

Mathematics Subject Classification ID

Applications of graph theory (05C90) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Abstract: 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.

Recommendations

• A note on two-pebble automata over infinite alphabets
• Finite state machines for strings over infinite alphabets
• scientific article; zbMATH DE number 1834677
• An infinite pebble game and applications
• scientific article; zbMATH DE number 1886325

Cited in

(6)

• On temporal logics with data variable quantifications: decidability and complexity
• On Pebble Automata for Data Languages with Decidable Emptiness Problem
• Two-way pebble transducers for partial functions and their composition
• A note on two-pebble automata over infinite alphabets
• Subsequence versus substring constraints in sequence pattern languages
• On pebble automata for data languages with decidable emptiness problem

This page was built for publication: Graph reachability and pebble automata over infinite alphabets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946705)