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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 47,283
Through your library

References found in this work BETA

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.

View all 6 references / Add more references

Citations of this work BETA

Generalized Quantifiers.Dag Westerståhl - 2008 - Stanford Encyclopedia of Philosophy.
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 9 citations / Add more citations

Similar books and articles


Added to PP index

Total views
20 ( #470,474 of 2,290,783 )

Recent downloads (6 months)
4 ( #305,329 of 2,290,783 )

How can I increase my downloads?


My notes

Sign in to use this feature