@article{VILLEMAIRE1992337,
    Abstract = {We first give a simple encoding for k-automata in 〈N, +, Vk〉, where Vk is the function from N⧹{0} to N mapping x to the largest power of k which divides x. This, with a result of Hodgson, gives a proof of B{\"u}chi's theorem, which states that a subset of Nn is k-recognizable by automata if and only if it is definable in 〈N, +, Vk〉. Our proof also shows that every formula of 〈N, +, Vk〉 is equivalent to a ∃∀∃-formula. Furthermore, solving a problem of A. Joyal, we show that the first-order theory of 〈N, +, Vk, Vl〉 is undecidable for k,l multiplicatively independent.},
    Author = {Villemaire, Roger},
    File = {The theory of <N, +, Vk, Vl > is undecidable - 1-s2.0-030439759290256F-main.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Number = {2},
    Pages = {337--349},
    Title = {{The theory of $\langle \mathbb N, +, V_k, V_l \rangle$ is undecidable}},
    URL = {https://www.sciencedirect.com/science/article/pii/030439759290256F},
    Volume = {106},
    Year = {1992},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/030439759290256F},
    bdsk-url-2 = {https://doi.org/10.1016/0304-3975(92)90256-F},
    date-added = {2021-04-09 14:18:07 +0200},
    date-modified = {2021-04-09 14:19:26 +0200},
    doi = {10.1016/0304-3975(92)90256-F}
}

@article{VILLEMAIRE1992337, Abstract = {We first give a simple encoding for k-automata in 〈N, +, Vk〉, where Vk is the function from N⧹{0} to N mapping x to the largest power of k which divides x. This, with a result of Hodgson, gives a proof of B{\"u}chi's theorem, which states that a subset of Nn is k-recognizable by automata if and only if it is definable in 〈N, +, Vk〉. Our proof also shows that every formula of 〈N, +, Vk〉 is equivalent to a ∃∀∃-formula. Furthermore, solving a problem of A. Joyal, we show that the first-order theory of 〈N, +, Vk, Vl〉 is undecidable for k,l multiplicatively independent.}, Author = {Villemaire, Roger}, File = {The theory of is undecidable - 1-s2.0-030439759290256F-main.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Number = {2}, Pages = {337--349}, Title = {{The theory of $\langle \mathbb N, +, V_k, V_l \rangle$ is undecidable}}, URL = {https://www.sciencedirect.com/science/article/pii/030439759290256F}, Volume = {106}, Year = {1992}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/030439759290256F}, bdsk-url-2 = {https://doi.org/10.1016/0304-3975(92)90256-F}, date-added = {2021-04-09 14:18:07 +0200}, date-modified = {2021-04-09 14:19:26 +0200}, doi = {10.1016/0304-3975(92)90256-F} }