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
topHow 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.
- S. Feferman and R.L. Vaught, The first order properties of products of algebraic systems. Fund. Math.47 (1959) 57–103.
- 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.
- S. Shelah, The monadic theory of order. Ann. Math.102 (1975) 379–419.
- S. Soprunov, Decidable expansions of structures. Vopr. Kibern.134 (1988) 175–179 (in Russian).
- W. Thomas, The theory of successor with an extra predicate. Math. Ann.237 (1978) 121–132.
- 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.