×

Weakly maximal decidable structures. (English) Zbl 1149.03015

A structure \(M = (S, P_1,\dots,P_n)\) is a set \(S\) on which some predicates \(P_1,\dots,P_n\) are defined. First-order (FO) and monadic second-order (MSO) theories of \(M\) are considered. With the help of the Feferman-Vaught composition theorem on the reducibility of the FO theory of a generalized product of some structures to the theory of the factor structures and to the MSO theory of the index structures, Shelah’s composition theorem, and Büchi’s results on the connection beween MSO of the structure \((N,<)\) and finite automata, the authors construct a structure \(M\) whose MSO theory is decidable and such that the FO theory of every expansion of \(M\) by a non-definable constant is undecidable.

MSC:

03B25 Decidability of theories and sets of sentences
03C57 Computable structure theory, computable model theory
03D05 Automata and formal grammars in connection with logical questions
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML

References:

[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 · Zbl 0144.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 · Zbl 0088.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 · Zbl 1039.03027
[7] S. Shelah, The monadic theory of order. Ann. Math.102 (1975) 379-419. · Zbl 0345.02034
[8] S. Soprunov, Decidable expansions of structures. Vopr. Kibern.134 (1988) 175-179 (in Russian). · Zbl 0665.03004
[9] W. Thomas, The theory of successor with an extra predicate. Math. Ann.237 (1978) 121-132. Zbl0369.02025 · Zbl 0369.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. Zbl0888.03002 · Zbl 0888.03002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.