An extension of the Cobham-Semënov Theorem

DOI10.2307/2586532zbMath0958.03025OpenAlexW2130116755MaRDI QIDQ4953215

Alexis Bès

Publication date: 19 March 2001

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2586532

zbMATH Keywords

automataarithmeticdefinabilityrecognizable sets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) First-order arithmetic and fragments (03F30) Automata sequences (11B85) Interpolation, preservation, definability (03C40)

Related Items (8)

On multiplicatively dependent linear numeration systems, and periodic points ⋮ Bertrand numeration systems and recognizability ⋮ An asymptotic version of Cobham’s theorem ⋮ Cobham's theorem for substitutions ⋮ Self-similar tiling systems, topological factors and stretching factors ⋮ Semi-synchronous transductions ⋮ On recognizable sets of integers ⋮ Independent numeration systems and syndeticity

Cites Work

• Presburgerness of predicates regular in two number systems
• Independent numeration systems and syndeticity
• A generalization of Cobham's theorem
• Bertrand numeration systems and recognizability
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• Weak Second‐Order Arithmetic and Finite Automata
• Systems of Numeration
• On the base-dependence of sets of numbers recognizable by finite automata

This page was built for publication: An extension of the Cobham-Semënov Theorem