On the Recognizability of Self-Generating Sets

Let

be a finite set of integers and

be a finite set of maps of the form $n\mapsto k_i\, n+\ell_i$ with integer coefficients. For an integer base $k\ge 2$ , we study the

-recognizability of the minimal set

of integers containing

and satisfying $\varphi(X)\subseteq X$ for all $\varphi\in F$ . We answer an open problem of Garth and Gouge by showing that

-recognizable when the multiplicative constants

are all powers of

and additive constants $\ell_i$ are chosen freely. Moreover, solving a conjecture of Allouche, Shallit and Skordev, we prove under some technical conditions that if two of the constants

are multiplicatively independent, then

is not

-recognizable for any $k\ge 2$ .

Received November 16 2009; revised versions received January 21 2010. Published in Journal of Integer Sequences, January 27 2010.

On the Recognizability of Self-Generating Sets

Tomi Kärki University of Turku Department of Mathematics FI-20014 Turku Finland Anne Lacroix and Michel Rigo University of Liège Department of Mathematics Grande Traverse 12 (B37) B-4000 Liège Belgium

Tomi Kärki
University of Turku
Department of Mathematics
FI-20014 Turku
Finland

Anne Lacroix and Michel Rigo
University of Liège
Department of Mathematics
Grande Traverse 12 (B37)
B-4000 Liège
Belgium