Reachability is harder for directed than for undirected finite graphs

Journal of Symbolic Logic 55 (1):113-150 (1990)
Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain "built-in" relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2274958
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 24,453
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
M. Ajtai (1983). ∑11-Formulae on Finite Structures. Annals of Pure and Applied Logic 24 (1):1-48.
Ronald Fagin (1975). Monadic Generalized Spectra. Mathematical Logic Quarterly 21 (1):89-96.
Michel De Rougemont (1987). Second-Order and Inductive Definability on Finite Structures. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (1):47-63.

Add more references

Citations of this work BETA
Thomas Schwentick (1996). On Winning Ehrenfeucht Games and Monadic NP. Annals of Pure and Applied Logic 79 (1):61-92.

View all 6 citations / Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

10 ( #409,174 of 1,925,262 )

Recent downloads (6 months)

1 ( #418,201 of 1,925,262 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.