Weakly maximal decidable structures

Alexis Bès; Patrick Cégielski

RAIRO - Theoretical Informatics and Applications (2008)

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

Abstract

top
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. 


How to cite

top

Bè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
  1. 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.  
  2. 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.  
  3. 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
  4. S. Feferman and R.L. Vaught, The first order properties of products of algebraic systems. Fund. Math.47 (1959) 57–103.  Zbl0088.24803
  5. D. Perrin and J.-É. Pin, Infinite Words. Pure Appl. Math.141 (2004).  
  6. V.S. Harizanov, Computably-theoretic complexity of countable structures. Bull. Symbolic Logic8 (2002) 457–477.  Zbl1039.03027
  7. S. Shelah, The monadic theory of order. Ann. Math.102 (1975) 379–419.  Zbl0345.02034
  8. S. Soprunov, Decidable expansions of structures. Vopr. Kibern.134 (1988) 175–179 (in Russian).  Zbl0665.03004
  9. W. Thomas, The theory of successor with an extra predicate. Math. Ann.237 (1978) 121–132.  Zbl0369.02025
  10. 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 ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.