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
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 29,492
Through your library
References found in this work BETA
∑11-Formulae on Finite Structures.M. Ajtai - 1983 - Annals of Pure and Applied Logic 24 (1):1-48.
Monadic Generalized Spectra.Ronald Fagin - 1975 - Mathematical Logic Quarterly 21 (1):89-96.
Second-Order and Inductive Definability on Finite Structures.Michel De Rougemont - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (1):47-63.

Add more references

Citations of this work BETA
On Winning Ehrenfeucht Games and Monadic NP.Thomas Schwentick - 1996 - Annals of Pure and Applied Logic 79 (1):61-92.
Arity and Alternation in Second-Order Logic.J. A. Makowsky & Y. B. Pnueli - 1996 - Annals of Pure and Applied Logic 78 (1-3):189-202.

View all 6 citations / Add more citations

Similar books and articles
Added to PP index

Total downloads
11 ( #409,249 of 2,180,625 )

Recent downloads (6 months)
1 ( #302,011 of 2,180,625 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature

There  are no threads in this forum
Nothing in this forum yet.

Other forums