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)|
References found in this work BETA
Second‐Order and Inductive Definability on Finite Structures.Michel De Rougemont - 1987 - Mathematical Logic Quarterly 33 (1):47-63.
Second-Order and Inductive Definability on Finite Structures.Michel De Rougemont - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (1):47-63.
Citations of this work BETA
Generalized Quantifiers and Pebble Games on Finite Structures.Phokion G. Kolaitis & Jouko A. Väänänen - 1995 - Annals of Pure and Applied Logic 74 (1):23-75.
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.
Easy Solutions for a Hard Problem? The Computational Complexity of Reciprocals with Quantificational Antecedents.Fabian Schlotterbeck & Oliver Bott - 2013 - Journal of Logic, Language and Information 22 (4):363-390.
The Monadic Second-Order Logic of Graphs VIII: Orientations.Bruno Courcelle - 1995 - Annals of Pure and Applied Logic 72 (2):103-143.
Similar books and articles
Forbidden Subgraphs and Forbidden Substructures.Gregory Cherlin & Niandong Shi - 2001 - Journal of Symbolic Logic 66 (3):1342-1352.
On the Expressiveness of Frame Satisfiability and Fragments of Second-Order Logic.Thomas Eiter & Georg Gottlob - 1998 - Journal of Symbolic Logic 63 (1):73-82.
Hereditary Undecidability of Some Theories of Finite Structures.Ross Willard - 1994 - Journal of Symbolic Logic 59 (4):1254-1262.
Canonical Simplification of Finite Objects, Well Quasi-Ordered by Tree Embedding.Thomas C. Brown - 1979 - Dept. Of Computer Science, University of Illinois at Urbana-Champaign.
A Transformational Characterization of Markov Equivalence for Directed Maximal Ancestral Graphs.Jiji Zhang & Peter Spirtes - unknown
Game-Theoretical Semantics for Peirce's Existential Graphs.Robert W. Burch - 1994 - Synthese 99 (3):361 - 375.
Finitely Constrained Classes of Homogeneous Directed Graphs.Brenda J. Latka - 1994 - Journal of Symbolic Logic 59 (1):124-139.
Added to index2009-01-28
Total downloads11 ( #395,383 of 2,152,644 )
Recent downloads (6 months)1 ( #399,611 of 2,152,644 )
How can I increase my downloads?