Geodesic
Non-maximal decidable structures
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 23-37 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Given any infinite structure $\mathfrak M$ with a decidable first-order theory, we give a sufficient condition in terms of the Gaifman graph of $\mathfrak M$, which ensures that $\mathfrak M$ can be expanded with some non-definable predicate in such a way that the first-order theory of the expansion is still decidable. Bibl. – 10 titles. 
@article{ZNSL_2008_358_a1,
     author = {A. B\`es and P. C\'egielski},
     title = {Non-maximal decidable structures},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {23--37},
     year = {2008},
     volume = {358},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a1/}
}
TY  - JOUR
AU  - A. Bès
AU  - P. Cégielski
TI  - Non-maximal decidable structures
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2008
SP  - 23
EP  - 37
VL  - 358
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a1/
LA  - en
ID  - ZNSL_2008_358_a1
ER  - 
%0 Journal Article
%A A. Bès
%A P. Cégielski
%T Non-maximal decidable structures
%J Zapiski Nauchnykh Seminarov POMI
%D 2008
%P 23-37
%V 358
%U http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a1/
%G en
%F ZNSL_2008_358_a1
A. Bès; P. Cégielski. Non-maximal decidable structures. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 23-37. http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a1/

[1] A. Bès, P. Cégielski, “Weakly maximal decidable structures”, RAIRO – Theor. Inf. Appl., 42:1 (2008), 137–135 | DOI | MR

[2] A. Blumensath, Locality and Modular Ehrenfeucht-Fraisse Games, Preprint, 2006

[3] Calvin C. Elgot, Michael O. Rabin, “Decidability and undecidability of extensions of second (first) order theory of (generalized) successor”, J. Symb. Log., 31:2 (1966), 169–181 | DOI

[4] H. Gaifman, “On local and non-local properties”, Logic Colloquium 81, Proc. Herbrand Symp. (Marseille, 1981), Stud. Logic Found. Math., 107, North-Holland, Amsterdam, 1982, 105–135 | MR

[5] C. H. Langford, “Theorem on deducibility (second paper)”, Annals of Math., 2 (1927), 459–471 | MR | Zbl

[6] L. Libkin, Elements of Finite Model Theory, Springer, Berlin, 2004 | MR

[7] M. Presburger, “Über de vollständigkeit eines gewissen systems der arithmetic ganzer zahlen, in welchen, die addition als einzige operation hervortritt”, Comptes Rendus du Premier Congrès des Mathématicienes des Pays Slaves, Warsaw, 1927, 92–101

[8] Alexei L. Semenov, “Decidability of monadic theories”, Mathematical Foundations of Computer Science (Prague, 1984), Lecture Notes in Computer Science, 176, eds. Michal Chytil,Václav Koubek, Springer, Berlin, 1984, 162–175 | MR

[9] Valentina S. Harizanov, “Computably-theoretic complexity of countable structures”, Bulletin of Symbolic Logic, 8 (2002), 457–477 | DOI | MR | Zbl

[10] S. Soprunov, “Decidable expansions of structures”, Vopr. Kibern., 134 (1988), 175–179 | MR | Zbl