Graph reachability and pebble automata over infinite alphabets

DOI10.1145/2499937.2499940zbMATH Open1353.68172arXiv1110.2776OpenAlexW2164433662MaRDI QIDQ2946705FDOQ2946705

Authors: Tony Tan 

Publication date: 17 September 2015

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

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.

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

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

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)

Cited In (6)

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