Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
- 1 December 1997
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 62 (4) , 1280-1296
- https://doi.org/10.2307/2275643
Abstract
Let k and l be two multiplicatively independent integers, and let L ⊆ ℕn be a l-recognizable set which is not definable in 〈ℕ; +〉. We prove that the elementary theory of 〈ℕ; +, Vk, L〉, where Vk(x) denotes the greatest power of k dividing x, is undecidable. This result leads to a new proof of the Cobham-Semënov theorem.Keywords
This publication has 7 references indexed in Scilit:
- Open Questions around BÜchi and Presburger ArithmeticsPublished by Oxford University Press (OUP) ,1996
- Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theoremsAnnals of Pure and Applied Logic, 1996
- The theory of
N , +, VTheoretical Computer Science, 1992 - Presburgerness of predicates regular in two number systemsSiberian Mathematical Journal, 1977
- A note on undecidable extensions of monadic second order successor arithmeticArchive for Mathematical Logic, 1975
- On the base-dependence of sets of numbers recognizable by finite automataTheory of Computing Systems, 1969
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960