Reachability is harder for directed than for undirected finite graphs

Journal of Symbolic Logic 55 (1):113-150 (1990)
Abstract
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
Options
 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: 26,173
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.
The Monadic Second-Order Logic of Graphs VIII: Orientations.Bruno Courcelle - 1995 - Annals of Pure and Applied Logic 72 (2):103-143.

View all 6 citations / Add more citations

Similar books and articles

Monthly downloads

Added to index

2009-01-28

Total downloads

11 ( #395,383 of 2,152,644 )

Recent downloads (6 months)

1 ( #399,611 of 2,152,644 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums