We prove that there exists a structure whose monadic second order theory is decidable, and such that the first-order theory of every expansion of by a constant is undecidable.
Mots-clés : decidability, first-order theories, monadic second-order theories, maximality, automata, rich words
@article{ITA_2008__42_1_137_0, author = {B\`es, Alexis and C\'egielski, Patrick}, title = {Weakly maximal decidable structures}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {137--145}, publisher = {EDP-Sciences}, volume = {42}, number = {1}, year = {2008}, doi = {10.1051/ita:2007044}, mrnumber = {2382548}, zbl = {1149.03015}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2007044/} }
TY - JOUR AU - Bès, Alexis AU - Cégielski, Patrick TI - Weakly maximal decidable structures JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2008 SP - 137 EP - 145 VL - 42 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2007044/ DO - 10.1051/ita:2007044 LA - en ID - ITA_2008__42_1_137_0 ER -
%0 Journal Article %A Bès, Alexis %A Cégielski, Patrick %T Weakly maximal decidable structures %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 137-145 %V 42 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2007044/ %R 10.1051/ita:2007044 %G en %F ITA_2008__42_1_137_0
Bès, Alexis; Cégielski, Patrick. Weakly maximal decidable structures. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 1, pp. 137-145. doi : 10.1051/ita:2007044. http://archive.numdam.org/articles/10.1051/ita:2007044/
[1] 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. | MR
,[2] On rich words. In M. Lothaire, editor, Combinatorics on words. Progress and perspectives, Proc. Int. Meet., Waterloo, Canada (1982). Encyclopedia of Mathematics 17, Addison-Wesley (1983) 39-61. | MR | Zbl
,[3] Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. J. Symbolic Logic 31 (1966) 169-181. | Zbl
and .[4] The first order properties of products of algebraic systems. Fund. Math. 47 (1959) 57-103. | MR | Zbl
and ,[5] Infinite Words. Pure Appl. Math. 141 (2004). | Zbl
and ,[6] Computably-theoretic complexity of countable structures. Bull. Symbolic Logic 8 (2002) 457-477. | MR | Zbl
,[7] The monadic theory of order. Ann. Math. 102 (1975) 379-419. | MR | Zbl
,[8] Decidable expansions of structures. Vopr. Kibern. 134 (1988) 175-179 (in Russian). | MR | Zbl
,[9] The theory of successor with an extra predicate. Math. Ann. 237 (1978) 121-132. | MR | Zbl
,[10] 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. | MR | Zbl
,Cité par Sources :