Abstract
Gurevich and Rabinovich raised the following question: given a property of a set of rational numbers definable in the real line by a monadic second-order formula, is it possible to define it directly in the rational line? In other words, is it true that the presence of reals at the background do not increase the expressive power of monadic second-order logic?
In this paper, we answer positively this question. The proof in itself is a simple application of classical and more recent techniques. This question will guide us in a tour of results and ideas related to monadic theories of linear orderings.
The research leading to these results has received funding from the European Uniona’s Seventh Framework Programme (FP7/2007-2013) under grant agreement n 259454. The author also acknowledges support from the project ANR 2010 BLAN 0202 02 FREC.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Büchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6, 66–92 (1960)
Büchi, J.R.: On a decision method in restricted second order arithmetic. In: Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.), pp. 1–11. Stanford Univ. Press, Stanford (1962)
Carton, O., Colcombet, T., Puppis, G.: Regular languages of words over countable linear orderings. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 125–136. Springer, Heidelberg (2011)
Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98, 21–51 (1961)
Feferman, S., Vaught, R.L.: The first order properties of products of algebraic systems. Fund. Math. 47, 57–103 (1959)
Gurevich, Y., Rabinovich, A.M.: Definability and undefinability with real order at the background. J. Symb. Log. 65(2), 946–958 (2000)
Gurevich, Y., Shelah, S.: Monadic theory of order and topology in zfc. In: Ann. of Math. Logic, vol. 23, pp. 179–198. North-Holland Publishing Compagny (1982)
Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141, 1–35 (1969)
Shelah, S.: The monadic theory of order. Ann. of Math. (2) 102(3), 379–419 (1975)
Trakhtenbrot, B.A.: Finite automata and monadic second order logic (Russian). Siberian Math. J 3, 103–131 (1962)
Trakthenbrot, B.A.: The impossibility of an algorithm for the decision problem for finite domains (Russian). Doklady Academii Nauk SSSR 70, 569–572 (1950)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Colcombet, T. (2013). Composition with Algebra at the Background. In: Bulatov, A.A., Shur, A.M. (eds) Computer Science – Theory and Applications. CSR 2013. Lecture Notes in Computer Science, vol 7913. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38536-0_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-38536-0_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38535-3
Online ISBN: 978-3-642-38536-0
eBook Packages: Computer ScienceComputer Science (R0)