Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems

DOI10.1016/0168-0072(95)00022-4zbMath0857.03003OpenAlexW2092583023WikidataQ56059272 ScholiaQ56059272MaRDI QIDQ1919534

Christian Michaux, Roger Villemaire

Publication date: 11 March 1997

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(95)00022-4

zbMATH Keywords

definabilityPresburger arithmeticCobham's theoremrecognizability by automataSemenov's theorem

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) First-order arithmetic and fragments (03F30)

Related Items (23)

Externally definable quotients and NIP expansions of the real ordered additive group ⋮ On iterating linear transformations over recognizable sets of integers ⋮ LOGICAL CHARACTERIZATION OF RECOGNIZABLE SETS OF POLYNOMIALS OVER A FINITE FIELD ⋮ Expansions of Presburger arithmetic with the exchange property ⋮ Quantitative estimates for the size of an intersection of sparse automatic sets ⋮ Strong theories of ordered Abelian groups ⋮ The definable criterion for definability in Presburger arithmetic and its applications. ⋮ An asymptotic version of Cobham’s theorem ⋮ Cobham's Theorem seen through Büchi's Theorem ⋮ THERE ARE NO INTERMEDIATE STRUCTURES BETWEEN THE GROUP OF INTEGERS AND PRESBURGER ARITHMETIC ⋮ Cobham-Semenov theorem and \(\mathbb N^d\)-subshifts ⋮ Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem ⋮ Words derivated from Sturmian words ⋮ A list of arithmetical structures complete with respect to the first-order definability ⋮ Sturmian words and a criterium by Michaux-Villemaire ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ An extension of the Cobham-Semënov Theorem ⋮ Self-similar tiling systems, topological factors and stretching factors ⋮ Defining Multiplication in Some Additive Expansions of Polynomial Rings ⋮ Presburger sets and p-minimal fields ⋮ On recognizable sets of integers ⋮ Independent numeration systems and syndeticity ⋮ Essentially periodic ordered groups

Cites Work

• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• Presburgerness of predicates regular in two number systems
• Logic and \(p\)-recognizable sets of integers
• The definable criterion for definability in Presburger arithmetic and its applications.
• Weak Second‐Order Arithmetic and Finite Automata
• ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
• Joining k- and l-recognizable sets of natural numbers
• On the base-dependence of sets of numbers recognizable by finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems