Abstract
We show that the first order theory of < IN, +, V k , V l >, where V r : IN{0} → IN is the function which sends x to V r (x), the greatest power of r which divides x and k, l are multiplicatively independent (i.e. they have no common power) is undecidable. Actually we prove that multiplication is definable in < IN, +, V k , V l >. This shows that the theorem of Büchi cannot be generalized to a class containing all k- and all l-recognizable sets.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
V. Bruyère, Entiers et automates finis, U.E. Mons (mémoire de licence en mathématiques) 1984–85
J.R. Büchi, Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlagen Math. 6 (1960), pp 66–92
A. Cobham, On the Base-Dependence of Sets of Numbers Recognizable by Finite-Automata, Math. Systems Theory 3, 1969, pp 186–192.
S. Eilenberg, Automata, Languages and Machines, Academic Press 1974.
C.C. Elgot, M.O. Rabin, Decidability and undecidability of extensions of second (first) order theory of (generalized) successor, J.S.L. vol. 31 (2) 1966, pp 169–181.
G. Hansel, A propos d'un théorème de Cobham, in: D. Perrin, ed., Actes de la FÊte des Mots, Greco de Programmation, CNRS, Rouen (1982).
R. McNaughton, Review of [2], J. Symbolic Logic 28 (1963), pp 100–102.
C. Michaux, F. Point, Les ensembles k-reconnaissables sont définissables dans < IN, +, Vk >, C.R. Acad. Sc. Paris t. 303, Série I, no 19, 1986, p.---
D. Perrin, Finite Automata, in: J. van Leeuwen, Handbook of Theoretical Computer Science, Elsevier 1990.
W.V. Quine. Concatenation as a basis for arithmetic. J.S.L. (1946) vol. 11 pp 105–114.
A.L. Semenov, On certain extensions of the arithmetic of addition of natural numbers, Math. USSR. Izvestiya, vol 15 (1980), 2, p.401–418.
J.W. Thatcher, Decision Problems for multiple successor arithmetics, J.S.L. (1966) vol. 11 pp 182–190.
W. Thomas, A note on undecidable extensions of monadic second order successor arithmetic, Arch. math. Logik 17 (1975), pp 43–44.
R. Villemaire, < IN, +,V k ,Vl> is undecidable. (preprint).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Villemaire, R. (1992). Joining k- and l-recognizable sets of natural numbers. In: Finkel, A., Jantzen, M. (eds) STACS 92. STACS 1992. Lecture Notes in Computer Science, vol 577. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55210-3_175
Download citation
DOI: https://doi.org/10.1007/3-540-55210-3_175
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55210-9
Online ISBN: 978-3-540-46775-5
eBook Packages: Springer Book Archive