# Weakly maximal decidable structures

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 1, page 137-145
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBès, Alexis, and Cégielski, Patrick. "Weakly maximal decidable structures." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 137-145. <http://eudml.org/doc/250370>.

@article{Bès2008,

abstract = {
We prove that there exists a structure M whose monadic second order theory is decidable, and such that the first-order theory of every expansion of M by a constant is undecidable.
},

author = {Bès, Alexis, Cégielski, Patrick},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Decidability; first-order theories; monadic second-order theories; maximality; automata; rich words; logical structure; first-order logic; maximality of theory; definability in logic; decidability; finite automaton; recognizability by automaton; relationship between definability and recognizability},

language = {eng},

month = {1},

number = {1},

pages = {137-145},

publisher = {EDP Sciences},

title = {Weakly maximal decidable structures},

url = {http://eudml.org/doc/250370},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Bès, Alexis

AU - Cégielski, Patrick

TI - Weakly maximal decidable structures

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/1//

PB - EDP Sciences

VL - 42

IS - 1

SP - 137

EP - 145

AB -
We prove that there exists a structure M whose monadic second order theory is decidable, and such that the first-order theory of every expansion of M by a constant is undecidable.

LA - eng

KW - Decidability; first-order theories; monadic second-order theories; maximality; automata; rich words; logical structure; first-order logic; maximality of theory; definability in logic; decidability; finite automaton; recognizability by automaton; relationship between definability and recognizability

UR - http://eudml.org/doc/250370

ER -

## References

top- J.R. Büchi, On a decision method in the restricted second-order arithmetic. In Proc. Int. Congress Logic, Methodology and Philosophy of science, Berkeley 1960. Stanford University Press (1962) 1–11.
- K.J. Compton, On rich words. In M. Lothaire, editor, Combinatorics on words. Progress and perspectives, Proc. Int. Meet., Waterloo, Canada (1982). Encyclopedia of Mathematics17, Addison-Wesley (1983) 39–61.
- C.C. Elgot and M.O. Rabin. Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. J. Symbolic Logic31 (1966) 169–181. Zbl0144.24501
- S. Feferman and R.L. Vaught, The first order properties of products of algebraic systems. Fund. Math.47 (1959) 57–103. Zbl0088.24803
- D. Perrin and J.-É. Pin, Infinite Words. Pure Appl. Math.141 (2004).
- V.S. Harizanov, Computably-theoretic complexity of countable structures. Bull. Symbolic Logic8 (2002) 457–477. Zbl1039.03027
- S. Shelah, The monadic theory of order. Ann. Math.102 (1975) 379–419. Zbl0345.02034
- S. Soprunov, Decidable expansions of structures. Vopr. Kibern.134 (1988) 175–179 (in Russian). Zbl0665.03004
- W. Thomas, The theory of successor with an extra predicate. Math. Ann.237 (1978) 121–132. Zbl0369.02025
- W. Thomas, Ehrenfeucht games, the composition method, and the monadic theory of ordinal words. In Structures in Logic and Computer Science, A Selection of Essays in Honor of A. Ehrenfeucht. Lect. Notes Comput. Sci.1261 (1997) 118–143.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.