Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-26T18:42:26.677Z Has data issue: false hasContentIssue false
  • English
  • Français

On countable chains having decidable monadic theory

Published online by Cambridge University Press:  12 March 2014

Alexis Bés  and
Alexander Rabinovich
Alexis Bés
Affiliation:
University of Paris-Est Créteil, Laboratoire d'Algorithmique, Complexité et Logique, Faculté des Sciences et Technologie, 61 Avenue du Général de Gaulle, 94010 Créteil, France, E-mail: [email protected]
Alexander Rabinovich
Affiliation:
The Blavatnik School of Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat Aviv 69978, Tel Aviv, Israel, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Rationals and countable ordinals are important examples of structures with decidable monadic second-order theories. A chain is an expansion of a linear order by monadic predicates. We show that if the monadic second-order theory of a countable chain C is decidable then C has a non-trivial expansion with decidable monadic second-order theory.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 77 , Issue 2 , June 2012 , pp. 593 - 608
Copyright
Copyright © Association for Symbolic Logic 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Bés, A. and Cégielski, P., Weakly maximal decidable structures, RAIRO Theoretical Informatics and Applications, vol. 42 (2008). no. 1. pp. 137–145.Google Scholar
[2] Bés, A. and Cégielski, P., Nonmaximal decidable structures. Journal of Mathematical Sciences, vol. 158 (2009), pp. 615–622.Google Scholar
[3] Bés, A. and Rabinovkh, A.. Decidable expansions of labelled linear orderings, Logical Methods in Computer Science, vol. 7 (2011), no. 2.Google Scholar
[4] Blumensath, A., Colcombet, T.. and Löding, C., Logical theories and compatible operations. Logic and automata: History and Perspectives (Flum, J., Grädel, E.. and Wilke, T.. editors), Amsterdam University Press. 2007. pp. 72–106.Google Scholar
[5] Büchi, J. R., On a decision method in the restricted second-order arithmetic. Proceedings of the International Congress on Logic, Methodology and Philosophy of Science, Berkeley 1960. Stanford University Press, 1962, pp. 1–11.Google Scholar
[6] Büchi, J. R., Transfinite automata recursions and weak second order theory of ordinals. Proceedings of the Internation Congress on Logic, Methodology, and Philosophy of Science, Jerusalem 1964, North Holland, 1965, pp. 2–23.Google Scholar
[7] Büchi, J. R. and Zaiontz, C., Deterministic automata and the monadic theory of ordinals ω2 , Zeitschrift für mathematische Logik und Grundlagen der Mathematik. vol. 29 (1983), pp. 313–336.CrossRefGoogle Scholar
[8] Elgot, C. C. and Rabin, M. O.. Decidability and undecidability of extensions of second (first) order theory of (generalized) successor, this Journal, vol. 31 (1966), no. 2. pp. 169–181.Google Scholar
[9] Feferman, S. and Vaught, R. L.. The first order properties of products of algebraic systems, Fundamenta Mathematicae, vol. 47 (1959), pp. 57–103.Google Scholar
[10] Gurevich, Y., Modest theory of short chains. I, this Journal, vol. 44 (1979). no. 4. pp. 481–490.Google Scholar
[11] Gurevich, Y., Monadic second-order theories. Model-theoretic logics (Barwise, J. and Feferman, S.. editors). Perspectives in Mathematical Logic, Springer-Verlag. 1985. pp. 479–506.Google Scholar
[12] Gurevich, Y., Magidor, M., and Shelah, S.. The monadic theory of ω2 . this Journal, vol. 48 (1983), no. 2, pp. 387–398.Google Scholar
[13] Gurevich, Y. and Shelah, S., Modest theory of short chains. II. this Journal, vol. 44 (1979), no. 4. pp. 491–502.Google Scholar
[14] Gurevich, Y. and Shelah, S., Interpreting second-order logic in the monadic theory of order, this Journal, vol. 48 (1983), no. 3. pp. 816–828.Google Scholar
[15] Läuchli, H., A decision procedure for the weak second-order theory of linear order. Contributions to Mathematical Logic (Schmidt, H. A., Schütte, K., and Thiele, H.-J.. editors), North-Holland Publishing Company, 1968, pp. 189–197.Google Scholar
[16] Makowsky, J. A., Algorithmic uses of the Feferman–Vaught theorem, Annals of Pure and Applied Logic, vol. 126 (2004), no. 1–3. pp. 159–213.Google Scholar
[17] Rabin, M. O., Decidability of second-order theories and automata on infinite trees, Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar
[18] Rabinovich, A.. The full binary tree cannot be interpreted in a chain, this Journal, vol. 75 (2010), no. 4, pp. 1489–1498.Google Scholar
[19] Rosenstein, J. G., Linear orderings. Academic Press. New York, 1982.Google Scholar
[20] Shelah, S., The monadic theory of order. Annals of Mathematics, vol. 102 (1975), pp. 379–419.Google Scholar
[21] Soprunov, S., Decidable expansions of structures, Voprosy Kibernet, vol. 134 (1988), pp. 175–179, (in Russian).Google Scholar
[22] Thomas, W., Ehrenfeucht games, the composition method, and the monadic theory of ordinal words, Structures in Logic and Computer Science, A Selection of Essays in Honor of A. Ehrenfeucht. Lecture Notes in Computer Science, no. 1261, Springer, 1997, pp. 118–143.Google Scholar
[23] Thomas, W., Languages, automata, and logic, Handbook of formal languages (Rozenberg, G. and Salomaa, A., editors), vol. III, Springer, 1997, pp. 389–455.Google Scholar
[24] Thomas, W., Model transformations in decidability proofs for monadic theories, Computer science logic 2008 (Kaminski, Michael and Martini, Simone, editors). Lecture Notes in Computer Science, vol. 5213, Springer, 2008, pp. 23–31.Google Scholar
[25] Zeitman, R. S., The composition method, Ph.D. thesis, Wayne State University, Michigan, 1994.Google Scholar