Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Graph reachability and pebble automata over infinite alphabets
Tan T. ACM Transactions on Computational Logic14 (3):1-31,2013.Type:Article
Date Reviewed: Nov 7 2013

It is known that a sentence of first-order logic of quantifier rank k can only express reachability in a directed graph of diameter at most 2k. Thus, general directed graph reachability is not expressible in first-order logic. The author of this paper considers the formalism of two-way alternating automata with k pebbles over an infinite alphabet, which is more expressive than first-order logic over an appropriate signature.

Tan proves a similar bound for this model, showing that general directed graph reachability cannot be modeled using pebble automata. The paper also establishes a strict hierarchy depending on the number of pebbles. A hierarchy of pebble automata on binary trees is considered in an earlier paper [1], but Tan does not refer to it.

Reviewer:  K. Lodaya Review #: CR141710 (1401-0084)
1) Bojańczyk, M.; Samuelides, M.; Schwentick, T.; Segoufin, L. Automata, languages and programming (LNCS 4051). Springer, , 2006.
Bookmark and Share
 
Automata (F.1.1 ... )
 
 
Computational Logic (F.4.1 ... )
 
 
Graph Theory (G.2.2 )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Automata": Date
The congruence theory of closure properties of regular tree languages
Tirri S. Theoretical Computer Science 76(2-3): 261-271, 2001. Type: Article
Jun 1 1991
Distribution and synchronized automata
Petit A. Theoretical Computer Science 76(2-3): 285-308, 2001. Type: Article
Feb 1 1992
Efficient simulation of finite automata by neural nets
Alon N., Dewdney A., Ott T. Journal of the ACM 38(2): 495-514, 1991. Type: Article
Dec 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy