Successor-invariant first-order logic on finite structures

Journal of Symbolic Logic 72 (2):601-618 (2007)
  Copy   BIBTEX

Abstract

We consider successor-invariant first-order logic (FO + succ)inv, consisting of sentences Φ involving an “auxiliary” binary relation S such that (

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1185803625

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,795

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

Epsilon-logic is more expressive than first-order logic over finite structures.Martin Otto - 2000 - Journal of Symbolic Logic 65 (4):1749-1757.
Definability in the monadic second-order theory of successor.J. Richard Buchi & Lawrence H. Landweber - 1969 - Journal of Symbolic Logic 34 (2):166 - 170.
Towards a characterization of order-invariant queries over tame graphs.Michael A. Benedikt & Luc Segoufin - 2009 - Journal of Symbolic Logic 74 (1):168-186.
Small substructures and decidability issues for first-order logic with two variables.Emanuel Kieroński & Martin Otto - 2012 - Journal of Symbolic Logic 77 (3):729-765.
On the Decision Problem for Two-Variable First-Order Logic.Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
On the decision problem for two-variable first-order logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
Toward Model-Theoretic Modal Logics.M. A. Minghui - 2010 - Frontiers of Philosophy in China 5 (2):294-311.
Toward model-theoretic modal logics.Minghui Ma - 2010 - Frontiers of Philosophy in China 5 (2):294-311.
Normal forms for second-order logic over finite structures, and classification of NP optimization problems.Thomas Eiter, Georg Gottlob & Yuri Gurevich - 1996 - Annals of Pure and Applied Logic 78 (1-3):111-125.
Decidability and undecidability of extensions of second (first) order theory of (generalized) successor.Calvin C. Elgot & Michael O. Rabin - 1966 - Journal of Symbolic Logic 31 (2):169-181.

Analytics

Added to PP
2010-08-24

Downloads
30 (#759,424)

6 months
11 (#364,844)

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

No references found.

Add more references