Logic and \(p\)-recognizable sets of integers
type: Item
instance of: scholarly article
title: Logic and \(p\)-recognizable sets of integers
zbMATH Open document ID: 0804.11024
author: Véronique Bruyère
author: Georges Hansel
author: Christian Michaux
author: Roger Villemaire
published in: Bulletin of the Belgian Mathematical Society - Simon Stevin
publication date: 1995-01-22T00:00:00Z
full work available at URL: https://eudml.org/doc/232407
review text: A theorem of \textit{A. Cobham} [Math. Syst. Theory 3, 186--192 (1969; Zbl 0253.02029)] asserts that if \(p\) and \(q\) are two multiplicatively independent integers (i.e. \(\log p/ \log q\) is irrational), then a sequence both \(p\)-automatic and \(q\)-automatic is necessarily ultimately periodic. The proof given by Cobham is rather intricate and many works have been devoted to simplify it. One of them, due to Semenov, uses arguments from logic to prove a multidimensional version of Cobham's theorem and... is not particularly simple. In the extremely interesting paper under review the authors give a very general and complete survey on these results (as well as the relationship with algebraic formal power series on a finite field and the Christol, Kamae, Mendès France and Rauzy theorem). Furthermore they give and simplify a proof of the Cobham-Semenov theorem, originally due to Muchnik. An essential result is that a sequence is \(p\)-automatic if and only if it is (first-order) definable in \(\langle \mathbb{N}, + ,V_p \rangle\), where \(V_p(n) = p^{v_p(n)}\) and \(v_p(n)\) is the largest \(\alpha\) such that \(p^\alpha\) divides \(n\) (here \(p\) is prime). Note that in the case \(p=2\) Büchi stated the result but used \(P_2\) instead of \(v_2\) where \(P_2(x)\) is the unary relation ``\(x\) is a power of 2''. MacNaughton noticed that the proof was wrong and the correct formulation and proof with \(v_p\) are due to the first author in her ``Mémoire de fin d'études'' written in 1985.
Mathematics Subject Classification ID: 11B85
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 589785
zbMATH Keywords: infinite words
zbMATH Keywords: \(p\)-recognizable sequences
zbMATH Keywords: finite automata
zbMATH Keywords: first-order definability
zbMATH Keywords: survey
zbMATH Keywords: formal power series
zbMATH Keywords: Cobham-Semenov theorem
reviewed by: Jean-Paul Allouche
MaRDI profile type: Publication
Recommended article: Cobham’s theorem and its extensions
Recommended article: Q3023976
Recommended article: Q4427624
Recommended article: Une généralisation du théorème de Cobham
Recommended article: 2- and 3-Mahler recurrences
Recommended article: Q3803206
Recommended article: Automata in number theory
Recommended article: How to prove that a sequence is not automatic
Recommended article: Q3469154
Recommended article: AUTOMATIC MAPS ON A SEMIRING WITH DIGITS
description: scientific article; zbMATH DE number 589785