The monadic second-order logic of graphs VIII: Orientations

Annals of Pure and Applied Logic 72 (2):103-143 (1995)
  Copy   BIBTEX

Abstract

In every undirected graph or, more generally, in every undirected hypergraph of bounded rank, one can specify an orientation of the edges or hyperedges by monadic second-order formulas using quantifications on sets of edges or hyperedges. The proof uses an extension to hypergraphs of the classical notion of a depth-first spanning tree. Applications are given to the characterization of the classes of graphs and hypergraphs having decidable monadic theories

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(95)94698-v

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,592

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Graph structure and monadic second-order logic: a language-theoretic approach.B. Courcelle - 2012 - New York: Cambridge University Press. Edited by Joost Engelfriet.
Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second‐Order Logic.Iain A. Stewart - 1997 - Mathematical Logic Quarterly 43 (1):1-21.
Random graphs in the monadic theory of order.Shmuel Lifsches & Saharon Shelah - 1999 - Archive for Mathematical Logic 38 (4-5):273-312.
Reachability is harder for directed than for undirected finite graphs.Miklos Ajtai & Ronald Fagin - 1990 - Journal of Symbolic Logic 55 (1):113-150.
Interpreting second-order logic in the monadic theory of order.Yuri Gurevich & Saharon Shelah - 1983 - Journal of Symbolic Logic 48 (3):816-828.
On countable chains having decidable monadic theory.Alexis Bés & Alexander Rabinovich - 2012 - Journal of Symbolic Logic 77 (2):593-608.
Relations in monadic third-order logic.A. P. Hazen - 1997 - Journal of Philosophical Logic 26 (6):619-628.
Peano arithmetic may not be interpretable in the monadic theory of linear orders.Shmuel Lifsches & Saharon Shelah - 1997 - Journal of Symbolic Logic 62 (3):848-872.
Monadic second-order logic, graph coverings and unfoldings of transition systems.Bruno Courcelle & Igor Walukiewicz - 1998 - Annals of Pure and Applied Logic 92 (1):35-62.
Towards a characterization of order-invariant queries over tame graphs.Michael A. Benedikt & Luc Segoufin - 2009 - Journal of Symbolic Logic 74 (1):168-186.
Reviewed Work(s): Graph structure and monadic second-order logic. Encyclopedia of Mathematics and Its Applications, vol. 138 by Bruno Courcelle; Joost Engelfriet.Review by: Achim Blumensath - 2013 - Bulletin of Symbolic Logic 19 (3):394-396,.
Simple monadic theories and indiscernibles.Achim Blumensath - 2011 - Mathematical Logic Quarterly 57 (1):65-86.
Embeddings between the elementary ontology with an atom and the monadic second-order predicate logic.Mitio Takano - 1987 - Studia Logica 46 (3):247 - 253.
On spectra of sentences of monadic second order logic with counting.E. Fischer & J. A. Makowsky - 2004 - Journal of Symbolic Logic 69 (3):617-640.

Analytics

Added to PP
2014-01-16

Downloads
15 (#940,347)

6 months
4 (#779,041)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1-6):66-92.
The structure of the models of decidable monadic theories of graphs.D. Seese - 1991 - Annals of Pure and Applied Logic 53 (2):169-195.

Add more references