RAIRO-Theor. Inf. Appl. 42, 137-145 (2008)
DOI: 10.1051/ita:2007044

Weakly maximal decidable structures

Alexis Bès and Patrick Cégielski

LACL, EA 4213, Université Paris-Est, Faculté des Sciences et Technologie, 61 avenue du Général de Gaulle, 94010 Créteil Cedex, France; bes@univ-paris12.fr; cegielski@univ-paris12.fr

(Published online: 18 January 2008)

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.

Mathematics Subject Classification. 03B25, 03C57, 03D05

Key words: Decidability -- first-order theories -- monadic second-order theories -- maximality -- automata -- rich words


© EDP Sciences 2007