Monadic second-order logic, graph coverings and unfoldings of transition systems

&
Annals of Pure and Applied Logic 92 (1):35-62 (1998)
  Copy   BIBTEX

Abstract

We prove that every monadic second-order property of the unfolding of a transition system is a monadic second-order property of the system itself. An unfolding is an instance of the general notion of graph covering. We consider two more instances of this notion. A similar result is possible for one of them but not for the other

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(97)00048-1

Links

PhilArchive



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

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.
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,.
Reviewed Work(s): Graph structure and monadic second-order logic. Encyclopedia of Mathematics and Its Applications, vol. 138 by Bruno Courcelle; Joost Engelfriet.Achim Blumensath - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
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.
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.
Isomorphisms and nonisomorphisms of graph models.Harold Schellinx - 1991 - Journal of Symbolic Logic 56 (1):227-249.
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.
The monadic second-order logic of graphs VIII: Orientations.Bruno Courcelle - 1995 - Annals of Pure and Applied Logic 72 (2):103-143.
Representability in second-order propositional poly-modal logic.G. Aldo Antonelli & Richmond H. Thomason - 2002 - Journal of Symbolic Logic 67 (3):1039-1054.
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.
Querying linguistic treebanks with monadic second-order logic in linear time.Stephan Kepser - 2004 - Journal of Logic, Language and Information 13 (4):457-470.
Logic of transition systems.Johan Van Benthem & Jan Bergstra - 1994 - Journal of Logic, Language and Information 3 (4):247-283.
Logic of transition systems.Johan Benthem & Jan Bergstra - 1994 - Journal of Logic, Language and Information 3 (4):247-283.

Analytics

Added to PP
2014-01-16

Downloads
33 (#480,801)

6 months
3 (#967,057)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Add more references