\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{subfigure}
\usepackage{vaucanson-g}

\newcommand{\f}{\varphi}
\newcommand{\rep}{\textrm{rep}}
\newcommand{\val}{\textrm{val}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\NP}{-\mathbb{N}}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/~njas/sequences/index.html?q=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf On the Recognizability of Self-Generating \\
\vskip .1in
Sets
}
\vskip 1cm
\large
Tomi K\"arki\footnote{Part of this research was done when the author was working in the Department of Mathematics at the University of Li{\`e}ge. The financial support from the Osk. Huttunen Foundation  is gratefully acknowledged.}\\
University of Turku \\
Department of  Mathematics\\ 
FI-20014 Turku \\
Finland\\
\href{mailto:topeka@utu.fi}{\tt topeka@utu.fi} \\
\ \\
Anne Lacroix and Michel Rigo\\
University of Li{\`e}ge \\
Department of  Mathematics\\
Grande Traverse 12 (B37) \\
B-4000 Li{\`e}ge \\
Belgium\\
\href{mailto:A.Lacroix@ulg.ac.be}{\tt A.Lacroix@ulg.ac.be} \\
\href{mailto:M.Rigo@ulg.ac.be}{\tt M.Rigo@ulg.ac.be} \\
\end{center}

\vskip .2 in

\begin{abstract}
    Let $I$ be a finite set of integers and $F$ 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
    $k$-recognizability of the minimal set $X$ of integers containing
    $I$ and satisfying $\varphi(X)\subseteq X$ for all $\varphi\in F$.
    We answer an open problem of Garth and Gouge by showing that $X$ is $k$-recognizable when the multiplicative constants $k_i$ are all powers of $k$ 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
    $k_i$ are multiplicatively independent, then $X$ is not
    $k$-recognizable for any $k\ge 2$.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}







\section{Introduction}

In the general framework of numeration systems, the so-called
recognizable sets of integers have been extensively studied. Let $k\ge
2$ be an integer.  The function $\rep_k\colon \mathbb{N} \to
\{0,\ldots,k-1\}^*$ maps a non-negative integer onto its $k$-ary
representation (without leading zeros). A set $X\subseteq\mathbb{N}$
is {\em $k$-recognizable} if the language $\rep_k(X)=\{\rep_k(n)\mid
n\in X\}$ is regular; see, for instance, \cite{BHMV}. A similar
definition can be given for the $k$-recognizable subsets of
$\mathbb{Z}$ using convenient conventions to represent negative
numbers, like adding a symbol ``$-$'' to the alphabet or considering
the positive and the negative elements separately. Since the seminal
work of Cobham \cite{Cob69}, it is well-known that the recognizability
of a set depends on the choice of the base $k$ --- except for the
ultimately periodic sets, i.e., the union of a finite set and a finite
number of infinite arithmetic progressions, which are easily seen to
be $k$-recognizable for all $k\ge 2$. The celebrated theorem of Cobham
can be stated as follows. Let $k,\ell\ge 2$ be two multiplicatively
independent bases, i.e., $\log k/\log \ell$ is irrational.  If a set
$X\subseteq\mathbb{N}$ is both $k$-recognizable and
$\ell$-recognizable, then it is ultimately periodic.

Kimberling~\cite{Kim00} introduced the so-called \emph{self-generating} sets of
integers. They can be defined as follows. Let $r\ge 1$
and $G=\{\f_1,\f_2,\ldots,\f_r\}$ be a set of affine maps where
$\f_i\colon n\mapsto k_i\, n+\ell_i$ with $k_i,\ell_i \in
\mathbb{Z}$ and $2 \leq k_1 \leq k_2 \leq \cdots \leq k_r$. The set
generated by $G$ and a finite set of integers $I$ is the minimal
subset $X$ of $\mathbb{Z}$ containing $I$ and such that
$\f_i(X)\subseteq X$ for all $i=1,\ldots,r$. For any subset
$S\subseteq\mathbb{Z}$, we set $G(S):=\{\f(s) \mid s \in S, \f\in
G\}$, $G^0(S):=S$ and $G^{m+1}(S):=G(G^m(S))$ for all $m\ge 0$.
Otherwise stated, $X=\bigcup_{m\ge 0} G^m(I)$ is the set of all
integers $n$ such that there exist $m\ge 0$, $a \in I$ and a finite
sequence $(\f_{i_1},\f_{i_2},\ldots,\f_{i_m})$ of maps in $G$ such
that
\begin{equation}\label{eqDefSG}
    n=\f_{i_m} \circ \f_{i_{m-1}}\circ \cdots \circ \f_{i_1}(a)
=\f_{i_m}(\f_{i_{m-1}}(\cdots \f_{i_1}(a) \cdots)).
\end{equation}
\begin{example}\label{exa:1}
    Kimberling~\cite{Kim00} showed for $G=\{n\mapsto 2n,n\mapsto 4n-1\}$ and $I=\{1\}$ that the corresponding self-generating set
    $$\mathcal{K}_1=\{1,2,3,4,6,7,8,11,12,14,15,16,\ldots\}$$ is
    closely related to the Fibonacci word. This relationship will be developed in Section~\ref{secKF},
where with our techniques we obtain again Kimberling's original
result. Notice that for $I=\{0\}$,
    we get a subset containing negative integers:
    $\mathcal{K}_0=\{0,-1,-2,-4,-5,-8,-9,\ldots\}$. In particular, for
    $I=\{0,1\}$, the corresponding self-generating set is
    $\mathcal{K}_0\cup\mathcal{K}_1$.
\end{example}

Self-generating sets are also called \emph{affinely recursive}
in~\cite{Kim04} where the correspondence between words $i_1 i_2
\cdots i_m$ over the alphabet $\{1,2,\ldots,r\}$ and integers
$\f_{i_m}(\f_{i_{m-1}}(\cdots \f_{i_1}(1) \cdots))$ is studied. For
example, conditions under which this correspondence is one-to-one
are given, which in turn implies that the natural ordering of the
integers induces an ordering on the set of non-empty words over
$\{1,2,\ldots,r\}$ providing a kind of abstract numeration system
\cite{LR}. Note that in the definition of affinely recursive sets~\cite{Kim04}
the set of generating functions~$G$ can be an
infinite set of maps of the form $\f_i\colon n\mapsto k_i\,
n+\ell_i$, where $k_i,\ell_i \in \mathbb{N}$.

Allouche, Shallit and Skordev \cite{AllSha05} consider a general framework for self-generating sets.
The $k$-ary representations of the elements of some
self-generating sets are related to words over
$\Sigma_k=\{0,1,\ldots,k-1\}$ where some fixed block of digits is
missing. As an illustration, one can notice that the set
$\mathcal{K}_1-1=\{0,1,2,3,5,6,7,10,\ldots\}$ introduced in
Example~\ref{exa:1} consists of all integers whose binary expansion
does not contain ``$00$'' as factor.  Recall that the {\em
  characteristic sequence} $(\mathbf{c}_X(n))_{n\geq 0}$ of a set
$X\subseteq\mathbb{N}$ is defined by $\mathbf{c}_X(n)=1$, if $n \in
X$ and $\mathbf{c}_X(n)=0$, otherwise. In particular, $X$ is
$k$-recognizable (resp., ultimately periodic) if and only if
$(\mathbf{c}_X(n))_{n\geq 0}$ is $k$-automatic (resp., an ultimately
periodic infinite word).  Self-generating sets are consequently
studied from the point of view of automatic and morphic sequences as
well as in relation to non-standard numeration systems; for the
definitions and further information, see~\cite{AllSha03,Lot02}.
Moreover, Allouche, Shallit and Skordev ask the following question:
\emph{Under what conditions is the characteristic sequence of a self-generating
set $k$-automatic?} They also present the following conjecture.
\begin{conjecture}\label{conj}
    {\em With ``mixed base'' rules, such as $G=\{n\mapsto
      2n+1,n\mapsto 3n\}$, the set generated from $I=\{1\}$ is not
      $k$-recognizable for any integer base $k\ge 2$.}
\end{conjecture}
Let us fix the notation once and for all.
\begin{definition}\label{def}
    In this paper, instead of considering a set $G$ of maps as
    described above, we will moreover consider the extended set of
    $r+1\ge 2$ maps
$$F=G\cup\{\f_0\}=\{\f_0,\f_1,\ldots,\f_r\}$$
where $\f_0\colon n \mapsto n$ and $\f_i\colon n\mapsto k_i\,
n+\ell_i$ with $k_i,\ell_i \in \mathbb{Z}$ and $$2 \leq k_1
\leq k_2 \leq \cdots \leq k_r.$$ Having the identity function $\f_0$
at our disposal, for any set $S\subseteq\mathbb{Z}$, we have
$F^m(S)\subseteq F^{m+1}(S)$. Therefore, for any finite set $I$ of
integers, the set
$$F^\omega(I):=\lim_{m\to\infty}F^m(I)$$ is exactly the {\em
self-generating set} with respect to $G$ and $I$.
\end{definition}

This article is an extended version of
our presentation given in the MFCS conference 2009
\cite{KLR}. The content of the paper is the following. In Section~\ref{secRed}
we give some simple observations on self-generating sets.
  For example, if we add to $F$ an extra map $\psi\colon n\mapsto n+\ell$ with $\ell\neq 0$,
    then the corresponding self-generating set $F^\omega(I)$ is
    ultimately periodic and  therefore $k$-recognizable for all $k\ge
    2$. We also show that we can restrict our considerations to subsets
    of $\mathbb{N}$ and assume that all additive constants $\ell_i$ for the maps $\f_i \in F$ are non-negative.

In sections~\ref{secMD} and~\ref{secKF} we consider the
multiplicatively dependent case. The results are based on Frougny's
normalization transducer; see, e.g., Chapter 7 in~\cite{Lot02}. If
all multiplicative constants $k_i$ are pairwise
    multiplicatively dependent, then we give a general method to build
    a finite automaton recognizing $\rep_k(F^\omega(I))$ for any $k$
    that is multiplicatively dependent on every $k_i$.  This allows us to
    generalize a recognizability result of Garth and Gouge~\cite{garth}. Moreover, a new proof
    of the relation between the Kimberling set $\mathcal{K}_1$ and the
    infinite Fibonacci word is given in Section~\ref{secKF}; for other proofs,
    see~\cite{AllSha05,Kim00}.

In the multiplicatively independent case of Section~\ref{secMI} we
study differences and ratios of consecutive elements in the
considered self-generating set. The results rely on a classical gap
theorem; see Theorem~\ref{thGap}. We prove that if there exist $i,j$
such that $k_i$ and $k_j$ are
    multiplicatively independent and if $\sum_{i=1}^r k_i^{-1}<1$,
    then $F^\omega(I)$ is not $k$-recognizable for any $k\ge 2$.
    In particular, this condition always holds for sets
    $F$ where $r=2$ and $k_1<k_2$ are multiplicatively
    independent, answering Conjecture~\ref{conj} in the affirmative.



\section{Some reductions}\label{secRed}

First we show that assuming $k_i\geq 2$ for every $i=1,2,\ldots,r$ is not a real restriction from the point of view of recognizability.

\begin{lemma}
    If we add to $F$ in Definition~\ref{def} an extra map
    $\psi\colon n\mapsto n+\ell$ with $\ell\neq 0$, then the corresponding
    self-generating set $F^\omega(I)$ is ultimately periodic of period
    $\ell$.
\end{lemma}

\begin{proof}
    Denote by $F^j(I) \bmod{\ell}$ the set $\{ n \bmod{\ell} \mid n
    \in F^j(I)\}$. Recall that the identity function $\f_0$ belongs to
    $F$. Since there are finitely many congruence classes modulo
    $\ell$ and $F^j(I) \bmod{\ell} \subseteq F^{j+1}(I) \bmod{\ell}$,
    there must exist an integer $J$ such that
$F^{J+1}(I) \bmod{\ell}=F^{J}(I) \bmod{\ell}$.
Moreover, this means that $F^j(I) \bmod{\ell}=F^{J}(I) \bmod{\ell}$ for
every $j\geq J$, and, consequently,
\begin{equation}\label{eqCongr}
    F^\omega(I) \bmod{\ell}=F^{J}(I)\bmod{\ell}.
\end{equation}

On the other hand, if $n \in F^\omega(I)$, then $\psi^t(n)=n+t\, \ell \in
F^\omega(I)$. Since $n+t\, \ell \equiv n \bmod{\ell}$, we conclude
by~\eqref{eqCongr}, for any $n \geq \max F^J(I)$, that
\[
\mathbf{c}_{F^\omega(I)}(n)=\left \{ \begin{array}{ll}
        1, & \text{ if $n \bmod{\ell} \in F^J(I) \bmod{\ell}$;}\\
        0, & \text{ otherwise}.\\
\end{array} \right.
\]
Hence, the characteristic sequence of $F^\omega(I)$ is ultimately
periodic with preperiod $\max F^J(I)$ and period~$\ell$.
\end{proof}

\begin{remark}
    In Definition~\ref{def} and in what follows, we always assume
    that all multiplicative constants $k_i$ of the affine maps
    $\f_1,\ldots,\f_r$ in $F$ are at least $2$.  This condition does
    not guarantee that the corresponding self-generating set is not
    ultimately periodic. For example, if $\f_{i}(x)=r\, x+i$ for
    $i=1,\ldots,r$, then we easily see that $F^\omega(\{0\}) =
    \mathbb{N}$.
\end{remark}

The next lemma justifies that we may restrict our consideration to
non-negative integers.

\begin{lemma}\label{lem:2}
Let $F^\omega(I)$ be a self-generating set as given in
Definition~\ref{def}. One can effectively construct two finite sets
of non-negative integers $I^+$ and $I^-$ such that
\[
F^\omega(I) \cap \NN=F^\omega(I^+) \cap \NN \quad \text{and} \quad
F^\omega(I) \cap \NP=-(\overline{F}^\omega(I^-) \cap \NN),
\]
where $\NP$ is the set of all non-positive
integers and
$\overline{F}=\{\f_0,\overline{\f}_1,\overline{\f}_2,\ldots,\overline{\f}_r\}$
with $\overline{\f}_i \colon n\mapsto k_i\, n-\ell_i$ for
$i=1,2,\ldots,r$.
\end{lemma}

\begin{proof}
Let $m=\max\{|\ell_i| \mid i=1,2,\ldots,r\}$ and denote by $M$ the
interval of integers $[\![-m,m]\!]$. Define $I_j:=F^j(I) \cap M$ for
$j\geq0$. Since $k_i\geq 2$ for all $i\in\{1,2, \ldots, r\}$, it
follows that if $n$ does not belong to $M$, then $\f_i(n) \not \in
M$ for all $i\in\{0,1,\ldots,r\}$. By this property and since
$F^j(I)\subseteq F^{j+1}(I)$, there must exist an integer $J$ such
that $I_j=I_J$ for all $j\geq J$. Hence, the integers of
$F^\omega(I)$ falling into the interval $M$ are exactly the ones in
$I_J$ and we can find the set $I^+:=((F^\omega(I) \cap M) \cup I)
\cap \NN$ effectively.

Next we show that $F^\omega(I) \cap \NN = F^\omega(I^+) \cap \NN$.
Since $I^+ \subseteq F^\omega(I)$, it is clear by definition that
$F^\omega(I^+) \cap \NN \subseteq F^\omega(I) \cap \NN$. Assume now
that there exists an integer $x$ belonging to $(F^\omega(I) \cap
\NN) \setminus (F^\omega(I^+) \cap \NN)$. Since $I^+$ contains all
non-negative elements of $I$, the element $x$ must be generated from
some negative element $a \in I$. In other words, there exists a
finite sequence $(\f_{i_1},\f_{i_2},\ldots,\f_{i_t})$ of maps in $F$
such that $x = \f_{i_t} \circ \f_{i_{t-1}}\circ \cdots \circ
\f_{i_1}(a)$. Since $a$ is negative and $x$ is positive, there
exists $j$ such that $\f_{i_{j-1}} \circ
\f_{i_{j-2}}\circ \cdots \circ \f_{i_1}(a)=y<0$ and $\f_{i_j}(y)=z
\geq 0$. Hence, we have $k_{i_j}y<0$ and $z=k_{i_j}y+\ell_{i_j}<m$.
This means that $z \in (F^\omega(I) \cap M) \cap \NN$ and therefore
$x = \f_{i_t} \circ \f_{i_{t-1}}\circ \cdots \circ \f_{i_{j+1}}(z)
\in F^\omega(I^+) \cap \NN$. This is a contradiction.

Similarly, by defining $I^-:=-(((F^\omega(I) \cap M) \cup I) \cap
\NP)$, we obtain $F^\omega(I) \cap \NP = F^\omega(-I^-) \cap \NP$.
If
$\overline{F}=\{\f_0,\overline{\f}_1,\overline{\f}_2,\ldots,\overline{\f}_r\}$,
where $\overline{\f}_i \colon n\mapsto k_i\, n-\ell_i$ for
$i=1,2,\ldots,r$, then we clearly have $F^\omega(I) \cap \NP=
-(\overline{F}^\omega(I^{-}) \cap \NN)$, which concludes the proof.
\end{proof}

Let $y\ge 0$. Recall (for instance, see \cite{BHMV}) that a set
$Y\subseteq\mathbb{N}$ is $k$-recognizable if and only if $Y+y$ is
$k$-recognizable. As explained by the following lemma, from the
point of view of recognizability of subsets of $\mathbb{N}$, one can
also assume that all additive constants $\ell_i$ are non-negative.

\begin{lemma}\label{lmPos}
    Let $F^\omega(I)$ be a self-generating set as given in
    Definition~\ref{def}. There exist a non-negative integer $y$ and a
    self-generating set $\widehat{F}^\omega(I-y)$ such that
    $F^\omega(I)=\widehat{F}^\omega(I-y)+y$ and $\widehat{F}=\{\f_0,\widehat{\f}_1,\ldots, \widehat{\f}_r\}$,
    where $\widehat{\f}_i \colon n\mapsto k_i\,
    n+\widehat{\ell}_i$ for every $i=1,2,\ldots,r$ with some
    non-negative constants $\widehat{\ell}_i$ completely determined
    by $F$.
\end{lemma}

\begin{proof}
    Assume that at least for some function $\f_i \in F$ the constant
    $\ell_i$ is negative. Otherwise, the claim is trivial. Let $y=\max
    \{ |\ell_i| \mid \ell_i<0\}$ and set
    $$\widehat{\ell}_i:=\ell_i+(k_i-1)y$$
    for $i=1,2,\ldots,r$. Since $k_i\ge 2$, the constants
    $\widehat{\ell}_i$ are non-negative for every $i$.
    Let $\widehat{F}=\{\f_0, \widehat{\f}_1,\ldots,
    \widehat{\f}_r\}$ where $\widehat{\f}_i \colon n\mapsto k_i\,
    n+\widehat{\ell}_i$ for $i=1,\ldots,r$. We show by induction on the number of applied maps $m$ that $x$
    belongs to $F^m(I)$ if and only if $x-y$ belongs to
    $\widehat{F}^m(I-y)$.

    First, for any $x \in I$, it is obvious
    that $x-y$ belongs to $I-y$ and vice versa. Assume now that $x \in F^m(I)$ for some $m\ge 1$.
    In other words, there exist $z\in F^{m-1}(I)$
    and $i\in\{0,\ldots,r\}$ such that $x=\f_i(z)$. By induction
    hypothesis, $z-y$ belongs to $\widehat{F}^{m-1}(I-y)$.
    If $\f_i=\f_0$, then $x = z$ and $x-y \in {\widehat{F}^{m-1}(I-y)} \subseteq
    \widehat{F}^m(I-y)$.
    Hence, assume that $\f_i \neq \f_0$.
    We have $\f_i(z)=k_i\,
    z+\ell_i$ and
    $\widehat{\f}_i(z-y)=k_i(z-y)+\ell_i+(k_i-1)y=\f_i(z)-y$. This
    proves that $x-y$ belongs to $\widehat{F}^{m}(I-y)$.

    Next assume
    that $x-y \in \widehat{F}^{m}(I-y)$ for some $m\ge 1$, i.e., $x-y=\widehat{\f}_i(z)$ for
    some $z\in \widehat{F}^{m-1}(I-y)$ and $i\in\{0,\ldots,r\}$. As above, we may assume that $\f_i \neq \f_0$.
    Then we have $x=\widehat{\f}_i(z)+y=k_i(z+y)+\ell_i=\f_i(z+y)$, where
    $z+y$ belongs to $F^{m-1}(I)$ by
    induction hypothesis. Hence, $x$ belongs to $F^{m}(I)$.
\end{proof}

\begin{example}\label{exMissingBlock}
    Consider the set $\mathcal{K}_1$ of Example~\ref{exa:1}
    generated from $\{1\}$ by the maps $n\mapsto 2n$ and $n\mapsto
    4n-1$.  Applying the construction given in the previous proof,
    set $y=1$ and consider the maps $2n+1$ and $4n+2$. These two maps
    generate from $\{1\}-1=\{0\}$, the set
    $\{0,1,2,3,5,6,7,10,\ldots\}$ which is equal to $\mathcal{K}_1-1$.
\end{example}



\section{Multiplicatively Dependent Case}\label{secMD}

In this section we assume that the multiplicative coefficients $k_i$
appearing in Definition~\ref{def} are all pairwise multiplicatively
dependent, i.e., for every pair $(i,j)$, there exist positive
integers $e_i$ and $e_j$ such that $k_i^{e_i}=k_j^{e_j}$. Note that
$k_i$ and $k_j$ are multiplicatively dependent if and only if there
exist an integer $n\geq2$ and two integers $d_i,d_j \geq 1$ such
that $k_i=n^{d_i}$ and $k_j=n^{d_j}$.  By this characterization, it
is easy to see that if the coefficients $k_i$ are pairwise
multiplicatively dependent, then there exists an integer $k$ such
that every $k_i$ is a power of $k$. Our aim is to build a finite
automaton showing that the set $F^\omega(I)$ is $k$-recognizable.

Recall that $\Sigma_k=\{0,1,\ldots, k-1\}$ and that $\rep_k\colon
\mathbb{N} \to \Sigma_k^*$ maps an integer $n$ to its $k$-ary
representation without leading zeros. For any finite alphabet
$A\subseteq\mathbb{Z}$, the function $\val_{A,k}\colon A^* \to
\mathbb{Z}$ maps a word $w=w_nw_{n-1}\cdots w_0$ over $A$ to the
corresponding numerical value $$\val_{A,k}(w)=\sum_{i=0}^{n}w_i\, k^i.$$
The function defined over the set of words $w\in A^*$ such that
$\val_{A,k}(w)\ge 0$ and which maps $w$ to $\rep_k(\val_{A,k}(w))$ is
called {\em normalization} over $A$. In the special case $A=\Sigma_k$,
we simply write $\val_k$ instead of $\val_{\Sigma_k,k}$.

\begin{theorem}\label{thMD}
    Let $F$ given in Definition~\ref{def} be such that the
    multiplicative coefficients $k_1,\ldots,k_r$ are all pairwise
    multiplicatively dependent. For any finite $I \subset \mathbb{Z}$,
    the self-generating set $F^\omega(I)$ is $k$-recognizable if $k_i$ is a power of $k$ for
    every $i=1,2, \ldots,r$.
\end{theorem}

We give a proof relying on Frougny's normalization theorem. Another
proof is given in~\cite{KLR}.


\begin{proof}
    Assume that the maps in~$F$ are of the
    kind $\f_i \colon n\mapsto k^{e_i}\, n+\ell_i$ with $e_i\ge 1$ for all
    $i\in\{1,\ldots,r\}$. Since in the
    constructions of $\overline{F}$ and $\widehat{F}$ of Lemma~\ref{lem:2} and
    Lemma~\ref{lmPos} the multiplicative constants $k_i$ are not
    modified, it suffices to
    consider only non-negative elements of $F^\omega(I)$ and,
    moreover, we may assume that all initial values in~$I$ and all additive constants
    $\ell_i$ are non-negative. Thus, we assume $F^\omega(I)
    \subseteq \NN$ and show that this
    self-generating set is $k$-recognizable.


    Let $n$ be an element of~$F^\omega(I)$. In other words, there exists a finite
    sequence $(\f_{i_1},\f_{i_2},\ldots,\f_{i_m})$ of maps in $F$ such that
    $n=\f_{i_m}(\f_{i_{m-1}}(\cdots \f_{i_1}(a)\cdots))$ for some $a\in I$. With that integer, we
    associate the word $$w=a\, 0^{e_{i_1}-1}\ell_{i_1} \cdots
    0^{e_{i_m}-1}\ell_{i_m}$$ over the finite alphabet $A=I\cup
    \{0,\ell_1,\ldots,\ell_r\}\subset\NN$. One can notice that
    $\val_{A,k}(w)=n$ and $\val_{A,k}(I\{0^{e_{1}-1}\ell_1,\ldots,0^{e_{r}-1}\ell_r\}^*)=F^\omega(I)$.
    Frougny's normalization theorem (\cite[Proposition 7.1.4]{Lot02}, see also \cite{Fro}) says that
    normalization over~$A$ is computable by a finite transducer~$T$. It is also well-known
    (see, e.g.,~\cite[Theorem 4.3.6]{AllSha03}) that if a regular
    language $L$ is an input of a transducer then the output language is
    also regular. Hence, feeding the transducer $T$ with the language
    $I\{0^{e_{1}-1}\ell_1,\ldots,0^{e_{r}-1}\ell_r\}^*$ gives us the
    regular language $\rep_k(F^\omega(I))$, which proves the claim.
\end{proof}

\begin{remark}
    The set $F^\omega(I)$ considered in the above theorem is
    $k$-recognizable and therefore $k^n$-recognizable for all $n\ge
    1$; again, see \cite{BHMV} for details. But usually this set is not
    ultimately periodic and therefore, by Cobham's Theorem, not
    $\ell$-recognizable for any $\ell\ge 2$ such that $k$ and $\ell$
    are multiplicatively independent. Indeed, if
    Theorem~\ref{thNotSyn} described below can be applied, then
    $F^\omega(I)$ contains arbitrarily large gaps.
\end{remark}

\begin{remark}
Garth and Gouge~\cite{garth} consider the sequence $S_F$ which is
the increasing sequence of the elements in $F^\omega(I)$ in the case
where $I=\{1\}$, $k_i=k^{e_i}$, $1=e_1\leq e_2 \leq \cdots \leq
e_r$, $\ell_1=0$ and $-k^{e_i} < \ell_i \leq 0$ for each
$i=1,2,\ldots,r$. They prove that this sequence reduced modulo
positive integer $m$ is \emph{morphic}. In other words, there exists
a morphism $f$ satisfying $f(a)=ax$ for some letter $a$ and some
word $x \neq \varepsilon$ such that $S_F\bmod{m}$ is the image
under a coding of the infinite word
\[
f^\omega(a)=\lim_{n \to \infty}f^n(a)=axf(x)f^2(x)\cdots,
\]
which is a fixed point of $f$. Moreover, they show that the
characteristic sequence of $F^\omega(I)$ is $k$-automatic.

The authors of~\cite{garth} ask whether their results hold for more general
families of functions, for example, allowing $\ell_i \leq -k^{e_i}$.
The answer for the case where the multiplicative constants~$k_i$ are powers
of a fixed~$k$ but additive constants~$\ell_i$ are chosen freely follows easily from Theorem~\ref{thMD}.
Namely, as was mentioned in the introduction, the set of non-negative integers
$F^\omega(I)$ is $k$-recognizable if and only if its characteristic
sequence $(\mathbf{c}_{F^\omega(I)}(n))_{n\geq 0}$ is $k$-automatic.
Note that in the general case $F^\omega(I) \subseteq \mathbb{Z}$ we
should consider two-sided $k$-automatic sequences and two-sided
infinite fixed points (see Section $5.3$ and Section $7.4$
in~\cite{AllSha03} for more information) or consider non-negative
and non-positive integers separately. In any case, by
Lemma~\ref{lem:2}, the general case can be reduced to subsets of
$\mathbb{N}$.

Hence, let us consider a self-generating set $F^\omega(I) \subseteq
\mathbb{N}$ where the multiplicative constants~$k_i$ are powers of
some~$k$. By Theorem~\ref{thMD}, the characteristic sequence
$(\mathbf{c}_{F^\omega(I)}(n))_{n\geq 0}$ is $k$-automatic. Since
\mbox{$(n \bmod{m})_{n\geq0}$} is clearly $k$-automatic for any
$k\geq2$, then also the sequence
\[
\mathbf{u}=([\mathbf{c}_{F^\omega(I)}(n), n\bmod{m}])_{n \geq 0}
\] over the alphabet $\Sigma_2 \times \Sigma_m$ is $k$-automatic.
Thus, by the result of Cobham~\cite{cob1972}, it is the image
under a coding of a fixed point of a $k$-uniform morphism. Define a morphism $f\colon
(\Sigma_2 \times \Sigma_m)^* \to \Sigma_m^*$ by
\[
f([a,b])=\left \{ \begin{array}{ll}
        \varepsilon, & \text{ if $a=0$;}\\
        b, & \text{ otherwise}.\\
\end{array}
\right.
\]
Since the image of a morphic sequence by any morphism is either
finite or morphic~\cite{Cob68b} (see also \cite[Corollary
7.7.5]{AllSha03}) and $(\mathbf{c}_{F^\omega(I)}(n))_{n\geq 0}$
contains infinitely many ones, we conclude that $f(\mathbf{u})$ is
morphic. Since $f(\mathbf{u})$ is clearly the sequence $S_F$ reduced
modulo $m$, we have answered the open question of Garth and Gouge~\cite{garth} by
generalizing their results for any additive
constants $\ell_i$.
\end{remark}

\begin{remark}  Sequences with missing blocks are considered in~\cite{AllSha05,garth,Kim04}.
For example, if $\f_1\colon n \mapsto 2n+1, \f_2\colon n \mapsto
4n+2$ and $I=\{0\}$, then the set $F^\omega(I)$ is the set of
integers that do not contain the block ``$00$" in their normalized
binary expansion. Recall that this set is $\mathcal{K}_1-1$; see
Example~\ref{exMissingBlock}. In~\cite{AllSha05} the authors ask
whether or not the sequences with missing blocks are always
particular cases of affinely recursive sets. We want to make a
remark that, if $F^\omega(I)$ is a sequence with missing blocks,
then all constants $k_i$ must be multiplicatively dependent.
Otherwise, assume that $k_1$ and $k_2$ are multiplicatively
independent. Consider now the subset $X_i \subseteq F^\omega(I)$
generated from $I$ by only applying the map $\f_i$. By
Theorem~\ref{thMD}, this subset is $k_i$-recognizable. Consider now
the language~$0^*\rep_{k}(X_i)$, where $k$ is multiplicatively
independent to $k_i$. It is known that this language is \emph{right
dense} meaning that every word over the alphabet $\Sigma_k$ appears
as a prefix of some word in $0^*\rep_{k}(X_i)$; for a proof,
see~\cite[Lemma 11.1.1]{AllSha03}. Hence, it follows that any block of
digits over $\Sigma_k$ is a factor of $\rep_k(n)$ for some integer
$n \in X_i$. For any integer $k\geq 2$, either $k_1$ or $k_2$ is
multiplicatively independent with $k$, and therefore the set $X_1$
or $X_2$, and consequently also $F^\omega(I)$, cannot be a set of
integers that do not have some block of digits in their normalized
base-$k$ representation.
\end{remark}

In order to obtain a self-contained proof for
Theorem~\ref{thMD}, we may tailor Frougny's normalization transducer
for the language
$0^*I\{0^{e_{1}-1}\ell_1,\ldots,0^{e_{r}-1}\ell_r\}^*$ and directly
conclude that the output language over $\Sigma_k$ is regular. Next
we describe this in more detail. The following construction is
needed to prove the result relating $\mathcal{K}_1$ and the infinite
Fibonacci word in the next section. By Lemma~\ref{lem:2}, it
suffices to consider the set $F^\omega(I) \cap \NN$.

Let $C \subset \mathbb{Z}$ be a finite input alphabet and let
$\Sigma_k$ be the output alphabet. Denote $m=\max\{|c-a| \mid c \in
C, a \in \Sigma_k \}$ and let $\gamma=m/(k-1)$. Note that by the
Euclidean division, for every $s \in \mathbb{Z}$ and $c \in C$,
there exist a unique $a \in \Sigma_k$ and $s' \in \mathbb{Z}$ such
that $s+c=s'k+a$. Moreover, if $|s|<\gamma$, then $|s'|\leq
(|s|+|c-a|)/k<(\gamma+m)/k=\gamma$. This justifies that we may
define a finite right subsequential transducer, where the set of
states $Q=\{s \in \mathbb{Z} \mid |s|<\gamma\}$ corresponds to
possible carries, the initial state is $0$ and the set of edges is
\begin{equation}\label{eqEdges}
E=\{s \stackrel{c/a}{\longrightarrow}s' \mid s+c=s'k+a\}.
\end{equation}
A {\em right subsequential} transducer is a transducer that reads the input from right to left and the underlying
automaton where only inputs are considered is deterministic.
Moreover, we have a partial terminal function $\omega\colon Q \to
\Sigma_k^*$ mapping a state $s\geq0$ onto its normalized
representation $\rep_k(s)$. Let $w=c_nc_{n-1} \cdots c_0 \in
C^*\setminus 0C^*$ be a representation of an integer
$N=\val_{C,k}(w)\geq 0$. If we enter $w$ into the transducer, there is
a unique path
\[
0=s_0 \stackrel{c_0/a_0}{\longrightarrow} s_1
\stackrel{c_1/a_1}{\longrightarrow} s_2
\stackrel{c_2/a_2}{\longrightarrow} \cdots
\stackrel{c_n/a_n}{\longrightarrow}  s_{n+1}
\]
such that
$N=\sum_{i=0}^{n}c_ik^i=\sum_{i=0}^{n}a_ik^i+s_{n+1}k^{n+1}$. Hence,
$\omega(s_{n+1})a_na_{n_1} \cdots a_0$ is the normalized
representation in base $k$ of the integer $N$. This transducer is
Frougny's normalization transducer for an input not containing
leading zeros; see the proof of Lemma~7.1.1 in~\cite{Lot02}.

Next we adapt the above construction to our specific case of
self-generating sets. Let the input alphabet be $C=I\cup
\{0,\ell_1,\ldots,\ell_r\}$. We want to restrict the accepted input
to the words $w \in
0^*I\{0^{e_{1}-1}\ell_1,\ldots,0^{e_{r}-1}\ell_r\}^*$ such that
$\val_{C,k}(w)\geq 0$. As was shown in the proof of
Theorem~\ref{thMD}, these words represent exactly the numbers in
$F^\omega(I) \cap \NN$. Hence, we build a transducer $\mathcal{T}$
such that from each carry state $q \in Q={\{s \in \mathbb{Z} \mid
|s|<\gamma\}}$ we may read only words of the form $0^{e_i-1}\ell_i$ from right to left,
output the corresponding output of Frougny's
transducer and end up in some carry state $q' \in Q$. This can be
achieved by introducing chains of intermediate states where each
state has only one incoming and outgoing edge simulating the
behavior of Frougny's transducer. For example, assume that $k=2$,
$q=1$ and we want to read $003$ from right to left. This corresponds
to the map $\f\colon n \mapsto 8n+3$. By the construction, in our
modified transducer there is a path
\[
1 \stackrel{3/0}{\longrightarrow} \hat{2}
\stackrel{0/0}{\longrightarrow} \hat{1}
\stackrel{0/1}{\longrightarrow} 0,
\]
where $\hat{2}$ and $\hat{1}$ are additional intermediate states and
the starting state $1$ and the ending state $0$ belong to the
original set $Q$. From each state $q \in Q$ there are exactly $r$
paths of this kind corresponding to the $r$ maps $\f_i \in F$.

In addition, we need transitions corresponding to the initial values~$I$.
Let $t \not \in Q$ be a unique final state. For each $q \in Q$ and $a \in I$ such that $q+a\geq0$, we
add extra states and transitions which form a separate path from~$q$ to~$t$ such that it
simulates Frougny's transducer with input $0^{i}a$, where $i$ is the
maximum integer satisfying $k^i \leq q+a$. Padding with sufficiently
many zeros insures that the carry is $0$ after entering the final
state~$t$. Note that since we consider only non-negative elements of
$F^\omega(I)$, we do not build a path from~$q$ to the final state~$t$ for
an initial value~$a\in I$ such that $q+a<0$. For example, in the case $k=2$, $q=1$
and $a=5$ we have $i=2$, since $k^2<q+a=6<k^3$, and the path from
$q$ to $t$ is
\[
1 \stackrel{5/0}{\longrightarrow} \hat{3}
\stackrel{0/1}{\longrightarrow} \hat{1}
\stackrel{0/1}{\longrightarrow} t,
\]
where $\hat{3}$ and $\hat{1}$ are new intermediate states. There is
also a loop from the final state~$t$ onto itself with input $0$ and
output $0$. This corresponds to allowing leading zeros after the
most significant non-zero digit.

By our construction, each path from the initial state~$0$ to the
final state~$t$ corresponds to reading some word of the language
$0^*I\{0^{e_{1}-1}\ell_1,\ldots,0^{e_{r}-1}\ell_r\}^*$. Therefore,
the output of such an accepted path in our transducer $\mathcal{T}$
corresponds to some normalized representation (with possibly leading
zeros) of a number in the self-generating set $F^\omega(I)$.
Conversely, the normalized representation of a number
in~$F^\omega(I)$ padded with sufficiently many zeros corresponds to
the input of some accepted path in our transducer~$\mathcal{T}$.
Therefore, we may forget the input and consider a finite automaton
$\mathcal{A}$ where the edges are labeled only with the output.
Moreover, let us define that if in $\mathcal{A}$ there is a path from a state $q$
to the state $t$ with a label belonging to $0^*$,
then the set $q$ is an accepting state. This allows us to accept all
normalized representations with an arbitrary number of leading
zeros. We may also change the reading direction by turning the
arrows and changing the roles of the initial and final states. Of
course, the automaton obtained this way need not be complete and
deterministic, but it can be made complete by adding missing edges
which end up in a sink state and it can be made deterministic by the
subset construction. Hence, we have constructed this way a
deterministic finite automaton~$\mathcal{B}$ which recognizes
$0^*\rep_k(F^\omega(I) \cap \NN)$ and, by Lemma~\ref{lem:2}, we
conclude that $F^\omega(I)$ is $k$-recognizable.

\section{Kimberling set and the Fibonacci
word}\label{secKF}

In this section we show a result connecting the Kimberling set
$\mathcal{K}_1$ considered in Example~\ref{exa:1} and the infinite
Fibonacci word defined as the fixed point
$\f^\omega(0)=01\f(1)\f^2(1)\cdots =01001010\cdots$ of the morphism
$\f\colon {0 \mapsto 01}, {1 \mapsto 0}$. Recall that
$\mathcal{K}_1=F^\omega(I)$, where $F=\{\f_0,\f_1,\f_2\}$,
$\f_1\colon n \mapsto 2n$, $\f_2\colon n \mapsto 4n-1$ and
$I=\{1\}$.

\begin{theorem}
Let $S$ be the increasing sequence of elements of $\mathcal{K}_1$.
Omitting the first term, the sequence $S$ reduced modulo $2$, is the
Fibonacci word $\f^\omega(0)$.
\end{theorem}

This was the main result in~\cite{Kim00} and it was reproved
in~\cite{AllSha05}. Here we give a third proof based on the
transducer construction of the previous section and on some
technical manipulation of morphisms.

\begin{proof}
Let us first build the transducer~$\mathcal{T}$ for the set
$\mathcal{K}_1=F^\omega(I)$ as explained in the end of
Section~\ref{secMD}. This transducer and the corresponding reduced
automaton~$\mathcal{A}$ are illustrated in Figure~\ref{figTrans}.
Using the same notation as above, we have $k=2$, $C=\{1,0,-1\}$,
$m=2$ and $\gamma=2$. Since we never reach a carry state~$1$ from
the initial state~$0$, our set $Q=\{-1,0,1\}$ can be reduced to
$\{-1,0\}$. The input~$0$ corresponds to the map~$\f_1$ and the
input~$0(-1)$ corresponds to the map~$\f_2$. When we read $0(-1)$ from right
to left starting from either state $0$ or $-1$, we
introduce an intermediate state $\widehat{-1}$. Namely, for $s=0$
and $c=-1$, we have $s+c=(-1) \cdot k +1$ and, for $s=-1$ and
$c=-1$, we have $s+c=(-1) \cdot k +0$. Then from the state
$\widehat{-1}$ we must read $0$ and, since $-1+0=-1 \cdot k +1$, we
output $1$ and end up in $-1 \in Q$. Moreover, we can read the
initial value $1 \in I$ starting from any state in $Q$. For example,
there is an edge with label $1/0$ from $-1$ to $F$, since $-1+1=0
\cdot k +0$.


\begin{figure}[htbp]
        \centering
\subfigure{

\VCDraw{%
        \begin{VCPicture}{(-2,-1)(6,4)}
% states
 \State[0]{(0,3)}{P}
 \State[\widehat{-1}]{(3,3)}{Q}
 \State[F]{(0,0)}{R}
 \State[-1]{(3,0)}{S}
% initial--final
\Initial[n]{P}
\Final[s]{R}
% transitions
\LoopW[.5]{P}{0/0}
\EdgeR{P}{R}{1/1}
\EdgeL{P}{Q}{-1/1}
\LoopE[.5]{S}{0/1}
\LoopW[.5]{R}{0/0}
\ArcR{Q}{S}{0/1}
\ArcR{S}{Q}{-1/0}
\EdgeL{S}{R}{1/0}
%\ArcR[.6]{P}{Q}{(\#,b),(a,\#),(b,\#)}
%
\end{VCPicture}}
}
\subfigure{

\VCDraw{%
        \begin{VCPicture}{(-2,-1)(6,4)}
% states
 \State[0]{(0,3)}{P}
 \State[\widehat{-1}]{(3,3)}{Q}
 \State[F]{(0,0)}{R}
 \State[-1]{(3,0)}{S}
% initial--final
\Initial[n]{P}
\Final[s]{S}
\Final[s]{R}
% transitions
\LoopW[.5]{P}{0}
\EdgeR{P}{R}{1}
\EdgeL{P}{Q}{1}
\LoopE[.5]{S}{1}
\LoopW[.5]{R}{0}
\ArcR{Q}{S}{1}
\ArcR{S}{Q}{0}
\EdgeL{S}{R}{0}
%
\end{VCPicture}}

}
        \caption{Transducer~$\mathcal{T}$ and automaton~$\mathcal{A}$ corresponding to the Kimberling set.}
        \label{figTrans}
    \end{figure}

Using standard techniques we may easily build from $\mathcal{A}$ a
deterministic automaton $\mathcal{B}$ accepting
$0^*\rep_2(\mathcal{K}_1)$ when reading digits from left to right.
This automaton is described in Figure~\ref{figB}. A number in $\mathcal{K}_1$ such that its
binary representation is accepted by $b$ (the corresponding path ends in the final state~$b$) must be odd, since all incoming edges of $b$ are labeled by $1$.
Similarly, we conclude that a number having
a binary representation accepted by $c$ or $d$ must be even. Hence,
with an output function $\tau\colon A^* \mapsto \Sigma_2^*$, where
$A$ denotes the set of states of $\mathcal{B}$ and
\[
\tau(x) = \left \{ \begin{array}{ll}
        1, & \text{ if $x=b$;}\\
        0, & \text{ if $x=c$ or $x=d$;}\\
        \varepsilon, & \text{ otherwise},\\
\end{array}
\right.
\]
the automaton $\mathcal{B}_\tau$ generates the sequence $S\bmod{2}$, where $S$ is the increasing sequence of elements of
$\mathcal{K}_1$.



\begin{figure}[htbp]
        \centering
\VCDraw{%
        \begin{VCPicture}{(-2,-1)(6,4)}
% states
 \State[a]{(0,3)}{a}
 \State[b]{(0,0)}{b}
 \State[c]{(3,3)}{c}
 \State[d]{(6,3)}{d}
 \State[e]{(3,0)}{e}
 \State[f]{(6,0)}{f}
 \State[g]{(8,2)}{g}
% initial--final
\Initial[n]{a}
\Final[s]{b}
\Final[n]{c}
\Final[s]{d}
% transitions
\LoopW[.5]{a}{0}
\EdgeR{a}{b}{1}
\LoopW[.5]{b}{1}
\EdgeL{b}{c}{0}
\EdgeL{c}{d}{0}
\EdgeL{c}{e}{1}
\LoopN[.5]{d}{0}
\EdgeL{d}{g}{1}
\LoopE[.5]{g}{0,1}
\EdgeL{e}{b}{1}
\ArcR{e}{f}{0}
\ArcR{f}{e}{1}
\EdgeL{f}{g}{0}
%
\end{VCPicture}}

        \caption{A finite deterministic automaton~$\mathcal{B}$ accepting $0^*\rep_2(\mathcal{K}_1)$.}
        \label{figB}
    \end{figure}


The $2$-uniform morphism corresponding to $\mathcal{B}$ is
$\sigma\colon A^* \to A^*$ defined by
\[
a \mapsto ab, \quad b \mapsto cb, \quad c \mapsto de, \quad d
\mapsto dg, \quad e \mapsto fb, \quad f \mapsto ge, \quad g \mapsto
gg.
\]
By the above reasoning, it is clear that $\tau(\sigma^\omega(a))= S\bmod{2}$. Let us denote $B=\{a,b,c,d,e,f,g,h\}$. Using the
techniques described in the proof of Theorem~7.6.1 and Theorem~7.7.4
in~\cite{AllSha03}, we obtain a coding $\nu\colon B^* \to
\Sigma_2^*$ and a non-erasing morphism $\mu\colon B^* \to B^*$ such
that $\nu(\mu^\omega(a))=\mathcal{S}(\tau(\sigma^\omega(a)))$, where
$\mathcal{S}$ is the shift function deleting the first element of
the infinite word. The morphism $\mu$ is defined by
\begin{eqnarray*}
&a \mapsto abcdbeb, \quad b \mapsto cdb, \quad c \mapsto fgb, \quad d \mapsto eb, \quad e \mapsto fh,&\\
& \quad f \mapsto f, \quad g \mapsto gbeb, \quad h \mapsto hcdb&
\end{eqnarray*}
and
\[
\nu(x) = \left \{ \begin{array}{ll}
        1, & \text{ if $x=b$ or $x=h$;}\\
        0, & \text{ otherwise}.\\
\end{array}
\right.
\]

Our goal is to show that $\nu(\mu^\omega(a))$ is the infinite Fibonacci word.
For this purpose, let us first simplify the morphism $\mu$.
Since $\mu(fgb)=fgbebcdb=\mu(cdb)$, we conclude that
$\nu(\mu^i(fgb))=\nu(\mu^i(cdb))$ for every $i\geq0$ and,
consequently, we may set $\mu(c)=cdb$ without changing
$\nu(\mu^\omega(a))$. Similarly,  $\mu(fh)=fhcdb=\mu(eb)$ and
therefore $\nu(\mu^i(e))=\nu(\mu^i(d))$ for $i\geq0$. Thus, we may
set $e=d$ and replace the morphism $\mu$ by a simpler morphism on a
four-letter alphabet $\{a,b,c,d\}$:
\[
a \mapsto abcdbdb, \quad b \mapsto cdb, \quad c \mapsto cdb, \quad d
\mapsto db.
\]
Note that $b$ and $c$ have a different role with respect to the
coding, i.e., $\nu(b) \neq \nu(c)$. Since $b$ is always preceded by
$d$ except in the very beginning, we finally redefine the morphism
$\mu\colon \{a,b,c,d\}^* \to \{a,b,c,d\}^*$ by
\[
a \mapsto abcdbdbc, \quad b \mapsto db, \quad c \mapsto cdb, \quad d
\mapsto dbc.
\]
Hence, the sequence obtained by reducing $S$ modulo $2$ and omitting
the first element can be obtained as the image of a coding $\nu$ of
the fixed point $\mu^\omega(a)$.

Let us next modify the morphism generating the Fibonacci word.
First, note that we may replace $\f$ by $\f^2$, since clearly
$\lim_{n \to \infty}\f^n(0)=\lim_{n \to \infty}(\f^2)^n(0)$. Since
$\f^2(0)=010$ and $\f^2(1)=01$, we notice that there are two types
of zeros in the Fibonacci word: those followed by $0$ will be
denoted by $c$ and those followed by $1$ will be denoted by $d$. Let
us also replace every $1$ by $b$. Hence, we have
$\f^\omega(0)=\nu(\phi^\omega(d))$, where $\nu$ is the coding
defined above and $\phi\colon\{b,c,d\}^* \to \{b,c,d\}^*$ is a
morphism such that
\[
b \mapsto db, \quad c \mapsto dbc, \quad d \mapsto dbc.
\]
We denote $(f_n)_{n \geq 0}=\phi^\omega(d)=dbcdb\cdots$ and
$(s_n)_{n \geq 0}=\mu^\omega(a)=abcdbdbcdb\cdots$. In order to prove
the result of Kimberling, we have to show that
$\nu(\phi^\omega(d))=\nu(\mu^\omega(a))$. Since
$\nu(f_0)=\nu(d)=0=\nu(a)=\nu(s_0)$, it suffices to show that
$f_n=s_n$ for all $n\geq 1$. We do this by induction.

First observe that if $s_n=f_n$ for all $n=1,2,\ldots,k$, then
\begin{equation}\label{eqLength}
|\mu(s_0 \cdots s_k)|=|\phi(f_0 \cdots f_k)|+5.
\end{equation}
This holds because $|\mu(x)|_y=|\phi(x)|_y$ for every $x$ and $y$ in
$\{b,c,d\}$ and $|\mu(s_0)|=|\mu(a)|=|\phi(f_0)|+5$. Here $|w|_y$
denotes the number of letters $y$ occurring in the word $w$.

Now assume that $s_n=f_n$ for $1 \leq n \leq l$ and $l$ is such that
$\phi(f_0\cdots f_k)=f_0f_1 \cdots f_l$ for some $k>1$ satisfying
$f_k=b$. This implies that $\phi(f_0\cdots f_k)=uf_{l-1}f_l=udb$
and, by~\eqref{eqLength} and by the assumption, we have
\begin{equation}\label{eqInduction}
\mu(s_0\cdots
s_k)=udbs_{l+1}s_{l+2}s_{l+3}s_{l+4}s_{l+5}=udb.dbc.db,
\end{equation}
where $s_{l+4}s_{l+5}=\mu(s_k)=\mu(b)$ and
$s_{l+1}s_{l+2}s_{l+3}=\mu(s_{k-1})=\mu(d)$, since $s_k=b$ must be
preceded by~$d$ if $k>1$. We have two possibilities, either
$f_{k+1}f_{k+2}=db$ or $f_{k+1}f_{k+2}f_{k+3}=cdb$.

If $f_{k+1}f_{k+2}=db$, then $\phi(f_0\cdots
f_{k+2})=udb\phi(f_{k+1})\phi(f_{k+2})=udb.dbc.db$ and, by comparing
this to~\eqref{eqInduction}, we conclude that the claim $s_n=f_n$
holds for $1\leq n \leq l+5$.

Assume next that $f_{k+1}f_{k+2}f_{k+3}=cdb$. Now $f_1\cdots
f_{k+3}=s_1\cdots s_{k+3}$, since we must have $k+3\leq l$. Hence,
we obtain
\begin{eqnarray*}
\phi(f_0\cdots f_{k+3})&=&udb.dbc.dbc.db,\\
\mu(s_0\cdots s_{k+3})&=&udb.dbc.db.cdb.dbc.db,
\end{eqnarray*}
which implies that $s_n=f_n$ for $1\leq n \leq l+8$.

Since in the first case $f_{k+2}=b$ and in the second case
$f_{k+3}=b$, we may proceed by induction. This concludes the proof,
since the claim clearly holds for small values of $n\geq1$.
\end{proof}

\section{Multiplicatively Independent Case}\label{secMI}

In this section our aim is to show that
$F^\omega(I)\subseteq\mathbb{N}$ given in Definition~\ref{def} is
not recognizable in any base $k\ge 2$ provided that $\sum_{i=1}^r
k_i^{-1}<1$ and that there are at least two multiplicatively
independent coefficients $k_i$. For the proof, we introduce the
following notation. Let $X=\{x_0<x_1<x_2<\cdots\}$ be an infinite
ordered subset of $\mathbb{N}$. Then we denote
\[
R_X=\limsup_{i \rightarrow \infty}\, \frac{x_{i+1}}{x_i}\text{ and }D_X=\limsup_{i \rightarrow \infty}\, (x_{i+1}-x_i).
\]
In order to prove that a set is not $k$-recognizable for any base
$k\ge 2$, we use the following result from \cite{cob1972}, see also
Eilenberg's book \cite[Chapter V, Theorem~5.4]{Eil74}.

\begin{theorem}[Gap Theorem]\label{thGap} Let $k\ge 2$. If $X$ is a
    $k$-recognizable infinite subset of $\mathbb{N}$, then either
    $R_X>1$ or $D_X<\infty$.
\end{theorem}

Note that $D_X<\infty$ means that $X$ is \emph{syndetic}, i.e., there
exists a constant $C$ such that the gap $x_{i+1}-x_{i}$ between any
two consecutive elements $x_i,x_{i+1}$ in $X$ is bounded by $C$.  Let
us first show that if $\sum_{i=1}^r k_i^{-1}<1$, then the set
$F^\omega(I)$ given in Definition~\ref{def} contains arbitrarily large
gaps.

\begin{theorem}\label{thNotSyn}
    Let $X=F^\omega(I)$ be a self-generating subset of $\mathbb{N}$
    given in Definition~\ref{def}.  If $\sum_{i=1}^r k_i^{-1}<1$, then
    $X$ is not syndetic.
\end{theorem}

\begin{proof}  Let $n\ge 1$ and $K=k_1k_2 \cdots k_r$.
    Let $g=g_1 \circ g_2 \circ \cdots \circ g_n$ be a composite
    function, where $g_j$ belongs to $G=\{\f_1,\f_2, \ldots, \f_r\}$ for
    every $j=1,2,\ldots, n$ and $g_j = \f_i$ for exactly $n_i$
    integers $j\in\{1,\ldots,n\}$. Note that $n_1+n_2\cdots+n_r=n$. By
    definition, we have $g(x)=k_1^{n_1}k_2^{n_2}\cdots k_r^{n_r} x +
    c_g$, where $c_g$ is some constant depending on $g$. Since
    $k_1^{n_1}k_2^{n_2}\cdots k_r^{n_r}$ divides $K^n$, we get
$$\#\{g(x)\bmod{K^n}\mid x\in\mathbb{Z}\}=k_1^{n-n_1}k_2^{n-n_2}\cdots k_r^{n-n_r}.$$

Recall that $F=G \cup \{\f_0\}$, where $\f_0$ denotes the identity function.
The set $F^{n}(I)$ contains exactly the integers obtained by at most
$n$ applications of maps in $G$. For any interval of integers
$[\![N,N+K^n-1]\!]$ where $N>\max F^{n}(I)$, the elements of~$X$
belonging to this interval have been obtained by applying at least
$n+1$ maps.  Hence, in the interval $[\![N,N+K^n-1]\!]$ there can be
at most $k_1^{n-n_1}k_2^{n-n_2}\cdots k_r^{n-n_r}$ integers $x \in
X$ such that the last $n$ maps which produce $x$ correspond to the
composite function~$g$, i.e., such that there exists $y\in X$
satisfying $g(y)=x$.  For fixed numbers $n_i$, $i=1,2,\ldots, r$,
there are $n!/(n_1!n_2!\cdots n_r!)$ functions $g$ of the type
described above.  Thus, the number of integers in $X \cap
[\![N,N+K^n-1]\!]$ for any large enough $N$ is at most
\[
\sum_{n_1,n_2,\ldots,n_r} \left ( \frac{n!}{n_1!n_2!\cdots n_r!}
\right ) k_1^{n-n_1}k_2^{n-n_2}\cdots k_r^{n-n_r}=K^n \left (
\frac{1}{k_1}+\frac{1}{k_2}+ \cdots + \frac{1}{k_r} \right )^n
\]
where the sum is over $n_1,n_2,\ldots,n_r \geq 0$ satisfying
$n_1+n_2+\cdots+n_r=n$.

Hence, the biggest gap $x_{i+1}-x_i$ between
two consecutive elements $x_i, x_{i+1}\in X$ in the interval
$[\![N,N+K^n-1]\!]$ is at least
\[
d(n)=\frac{K^n}{K^n \left ( \frac{1}{k_1}+\frac{1}{k_2}+ \cdots +
\frac{1}{k_r} \right )^n} = \left ( \frac{1}{k_1}+\frac{1}{k_2}+
\cdots + \frac{1}{k_r} \right )^{-n}.
\]
Since $\sum_{i=1}^r k_i^{-1}<1$, the function $d(n)$ tends to infinity
as $n$ tends to infinity. This means that there are arbitrarily large
gaps in $X$. In other words, the self-generating set $X$ is not
syndetic.
 \end{proof}

 Before showing that $R_X=1$ let us first recall the density property
 of multiplicatively independent integers. A set $S$ is \emph{dense} in an
 interval $I \subseteq \mathbb{R}$ if every subinterval of $I$ contains an element of $S$.

\begin{theorem}\label{thDense}
    If $k,\ell\ge 2$ are multiplicatively independent, $\left \{
        k^p/\ell^q \mid p,q \geq 0 \right \}$ is dense in
    $[0,\infty)$.
\end{theorem}

This is a consequence of Kronecker's theorem, which states that
for any irrational number $\theta$ the sequence
$(\{n\theta\})_{n\geq0}$ is dense in the interval $[0,1)$. Here
$\{x\}$ denotes the fractional part of the real number $x$. The proof
of Kronecker's theorem as well as the proof of Theorem~\ref{thDense}
can be found in~\cite[Section 2.5]{AllSha03} or \cite{HW}. As an easy
consequence of the previous theorem, we obtain the following result.

\begin{corollary}\label{corDense}
    Let $\alpha>0$ and $\beta$ be two real numbers. If $k$ and $\ell$
    are multiplicatively independent, then the set $\left \{ (\alpha
        k^p+\beta)/\ell^q \mid p,q \geq 0 \right \} $ is
dense in $[0,\infty)$.
\end{corollary}

\begin{proof}
    We show how to get arbitrarily close to any positive real number
    $x$. Let $\epsilon >0$. By Theorem~\ref{thDense}, there exist
    integers $p$ and $q$ such that
\[
\left | \frac{x}{\alpha}-\frac{k^p}{\ell^q} \right | <
\frac{\epsilon}{2 \alpha} \quad \textrm{and} \quad \left |
\frac{\beta}{\ell^q} \right |< \frac{\epsilon}{2} .
\]
Hence, it follows that
\[
\left | x - \frac{\alpha k^p+\beta}{\ell^q} \right | \leq \left |
x-\frac{\alpha k^p}{\ell^q} \right | + \left | \frac{\beta}{\ell^q}
\right |< \frac{\epsilon}{2 \alpha} \alpha +
\frac{\epsilon}{2}=\epsilon.
\]
\end{proof}

Let us next consider the ratio $R_X$ of a self-generating set $X$.

\begin{theorem}\label{thRatio}
    For any self-generating set $X=F^\omega(I) \subseteq \mathbb{N}$ given in
    Definition~\ref{def} where $k_i$ and $k_j$ are multiplicatively
    independent for some $i$ and $j$, we have $R_X=1$.
\end{theorem}

\begin{proof}
    Without loss of generality, we may assume that
    $F=\{\f_0,\f_1,\f_2\}$, where $\f_1 \colon n\mapsto k_1\, n+\ell_1$,
    $\f_2 \colon n\mapsto k_2\, n+\ell_2$, and $k_1$ and $k_2$ are
    multiplicatively independent. Namely, for $F \subseteq F'$, it is
    obvious that $F^\omega(I) \subseteq F'^\omega(I)$ and
    consequently, $R_{F^\omega(I)}=1$ implies $R_{F'^\omega(I)}=1$. By
    Lemma~\ref{lmPos}, we may also assume that $\ell_1$ and $\ell_2$
    are non-negative.

    Let $a \in X$ be a positive integer and set $X_n:=X \cap
    [\f_1^{n-1}(a),\f_1^n(a)]$ for all $n>0$. Note that $\cup_{n \in
      \mathbb{N}}X_n=X\cap[a,\infty)$.  Recall that
    $X=\{x_0<x_1<x_2<\cdots\}$ and define
\[
r_n:=\max \left \{ \left. \frac{x_{i+1}-x_{i}}{x_i} \right| x_{i+1},x_i \in X_n \right \}.
\]
Note that, for all $x$ and for $j=1,2$, if we set
$b_j:=\ell_j/(k_j-1)$, then we have
\begin{equation}\label{eqImage}
\f_j^n(x)=k_j^n x+ \ell_j \sum_{i=0}^{n-1}k_j^i=(x + b_j)\, k_j^n-b_j.
\end{equation}

Let $m\geq0$ and $x_{i},x_{i+1}$ be two consecutive elements belonging
to the set~$X_m$.  By Corollary~\ref{corDense}, there exist
infinitely many positive integers $p$ and $q$ such that $\frac{\f_2^p(a)}{k_1^q}$ is equal to
$$\frac{(a+b_2) k_2^p-b_2}{k_1^q} \in
\left[ x_{i+1}+b_1-\frac{3}{4}( x_{i+1}-x_i), x_{i}+b_1+\frac{3}{4}( x_{i+1}-x_i) \right].$$
Therefore $\f_2^p(a)$ is an element of~$X$ belonging to the interval
\[
[c,d]:=\left[k_1^q(x_{i+1}+b_1)-\frac{3}{4}k_1^q( x_{i+1}-x_i) , k_1^q(x_i+b_1)+\frac{3}{4}k_1^q( x_{i+1}-x_i)  \right],
\]
which is a sub-interval\footnote{$c-\f_1^q(x_i)=\frac14
  k_1^q(x_{i+1}-x_i)+b_1$ and $\f_1^q(x_{i+1})-d=\frac14
  k_1^q(x_{i+1}-x_i)-b_1$ which is positive for large enough $q$.} of
the interval $[\f_1^{q}(x_{i}),\f_1^{q}(x_{i+1})]$. In other words, we have
$$ \f_1^{q}(x_{i}) <c< \f_2^p(a) <d<  \f_1^{q}(x_{i+1}).$$
 Hence, for all
$t>q$, the difference $x_{j+1}-x_j$ of any two consecutive elements
$x_j$, $x_{j+1}$ of $X$ in the interval
$[\f_1^{t}(x_{i}),\f_1^{t}(x_{i+1})]$ is at most
\begin{align*}
&\max\{\f_1^{t-q}(\f_1^q(x_{i+1}))-\f_1^{t-q}(\f_2^p(a)),\f_1^{t-q}(\f_2^p(a))-\f_1^{t-q}(\f_1^q(x_{i}))\}\\
&\qquad \leq\max\{\f_1^t(x_{i+1})-\f_1^{t-q}(c),\f_1^{t-q}(d)-\f_1^t(x_i)\} =\frac{3}{4}k_1^t(x_{i+1}-x_i)+b_1k_1^{t-q}.
\end{align*}
Thus, the ratio $(x_{j+1}-x_j)/x_j$ is at most
\begin{equation}\label{eqUB}
\frac{3\, k_1^t(x_{i+1}-x_i)}{4\, \f_1^t(x_i)}+\frac{b_1k_1^{t-q}}
{\f_1^t(x_i)}=\frac{3\, k_1^t(x_{i+1}-x_i)}{4\,
  \f_1^t(x_i)}+\frac{1}{k_1^q} \frac{b_1k_1^t}{(x_i+b_1)k_1^t-b_1}.
\end{equation}
The latter term in this sum can be taken as small as possible for
$q$ and $t$ large enough ($1/k_1^q$ tends to $0$ and the other
factor tends to the constant $b_1/(x_i+b_1)$). In particular, for
$q$ and $t$ large enough, we have
$$\frac{b_1k_1^{t-q}}{\f_1^t(x_i)}<\frac{x_{i+1}-x_i}{12x_i}.$$
Moreover, we have
$$\frac{3\, k_1^t(x_{i+1}-x_i)}{4\, \f_1^t(x_i)}=
\frac{3\, (x_{i+1}-x_i)}{4\, (x_i+b_1-b_1/k_1^t)}<\frac{3\,
(x_{i+1}-x_i)}{4\, x_i} <\frac{10\, (x_{i+1}-x_i)}{12\, x_i}.$$
Thus, by~\eqref{eqUB}, we obtain
\begin{equation}\label{eqAppr}
\frac{x_{j+1}-x_j}{x_j}<\frac{11\, (x_{i+1}-x_i)}{12\, x_i}.
\end{equation}
Since the above holds for any consecutive elements $x_i$ and $x_{i+1}$
in $X_m$ and there are only finitely many such pairs, we conclude that
there exists an integer $N_1$ such that \eqref{eqAppr} holds for any
consecutive elements $x_j,x_{j+1} \in X_n$ where $n\geq N_1$. Hence,
we obtain $r_{n}<\frac{11}{12}\, r_m$ for every $n\geq N_1$. Moreover,
by repeating this procedure, we conclude that there exists an integer
$N_k$ such that
\[
r_{n}<\left( \frac{11}{12} \right)^k r_m
\]
for every $n\geq N_k$. This implies that $\limsup_{n \rightarrow \infty}r_n=0$ and, consequently,
\[
R_X=1+\limsup_{n \rightarrow \infty}r_n=1.
\]

\end{proof}

Our main result is a straightforward consequence of the previous theorems.

\begin{theorem}\label{thMain}
    Let $X=F^\omega(I) \subseteq \mathbb{N}$ be given in Definition~\ref{def}.  If
    $\sum_{t=1}^r k_t^{-1}<1$ and there exist $i,j$ such that $k_i$
    and $k_j$ are multiplicatively independent, then $F^\omega(I)$ is
    not $k$-recognizable for any integer base $k\ge 2$.
\end{theorem}

\begin{proof}
Let $X=F^\omega(I)$ satisfy the assumptions of the theorem. By
Theorem~\ref{thNotSyn}, we have $D_X=\infty$ and, by
Theorem~\ref{thRatio}, we have $R_X=1$. Thus, Theorem~\ref{thGap}
implies that $X$ is not $k$-recognizable for any $k\geq 2$.
\end{proof}

As a corollary, we have solved the conjecture of Allouche, Shallit and Skordev~\cite{AllSha05}.

\begin{corollary}
    Let $F=\{\f_0,n\mapsto k_1\, n+\ell_1,n\mapsto k_2\, n+\ell_2\}$,
    where $k_1$ and $k_2$ are multiplicatively independent.  Then any
    infinite self-generating set~$F^\omega(I)$ given in
    Definition~\ref{def} is not $k$-recognizable for any $k\ge 2$.
\end{corollary}

\begin{proof}
This follows directly from Theorem~\ref{thMain}. Namely, if $k_1$
and $k_2$ are multiplicatively independent, then $k_1\geq 2$ and
$k_2\geq3$ and $k_1^{-1}+k_2^{-1}\leq 1/2 + 1/3 = 5/6 <1$.
\end{proof}

The condition $\sum_{t=1}^r k_t^{-1}<1$ is not needed in a very
special case of self-generating sets where $\ell_i=0$ for every
$i=1,2,\ldots,r$. This situation is related to so-called $y$-smooth
numbers. An integer is \emph{$y$-smooth} if it has no prime factors
greater than $y$. For more on smooth numbers, see, e.g.,~\cite{Gra08}.

\begin{theorem}
Let $X=F^\omega(I)$ be given in Definition~\ref{def}. If $\ell_i=0$
for every $i=1,2,\ldots,r$ and there exist $i,j$ such that $k_i$ and
$k_j$ are multiplicatively independent, then $F^\omega(I)$ is not
$k$-recognizable for any integer base $k\ge 2$. In particular, for $y\geq 3$, the set
of $y$-smooth numbers is not $k$-recognizable for any $k\geq 2$.
\end{theorem}

\begin{proof}
Assume that $\f_i\colon n \mapsto k_in$ for $i=1,2,\ldots,r$ and
denote $X=F^\omega(I)$. Let $x\geq 2$ be an integer and consider $n
\in X \cap [0,x]$. By the definition of~$X$, the integer~$n$
must be of the form $k_1^{e_1} \cdots k_r^{e_r}a$, where $a \in I$.
Since the exponent $e_i$ is at most $\log_2(x)$ for every
$i=1,2,\ldots,r$, the number of integers in $X \cap [0,x]$ is
at most $(1+\log_2(x))^r|I|=O(\log^r (x))$. It follows that $x/|X
\cap [0,x]|$ tends to infinity when $x$ tends to infinity.
This implies that $F^\omega(I)$ cannot be syndetic, i.e., $D_X =
\infty$. If there are two multiplicatively independent constants
$k_1$ and $k_2$, then $R_X=1$ by Theorem~\ref{thRatio}. Hence, by
Theorem~\ref{thGap}, the self-generating set $X$ is not
$k$-recognizable for any $k\geq2$. The second claim follows, since
the set of $y$-smooth numbers can be represented as a
self-generating set $F^\omega(I)$, where $I=\{1\}$ and $\f_i\colon n
\mapsto p_in$ for $i=1,2,\ldots,r$. Here $p_i$ is the $i$th smallest
prime and $p_r$ is the largest prime less than or equal to~$y$.
\end{proof}

\section{Acknowledgments}
We thank the anonymous referees of the MFCS version of this paper for
suggesting improvements in the presentation of this paper. In
particular, it is one of the referees who pointed out a possible
connection with smooth numbers.

\begin{thebibliography}{50}

  \bibitem{AllSha03} J.-P. Allouche, J. Shallit, {\em Automatic
      Sequences: Theory, Applications, Generalizations}, Cambridge
    University Press, 2003.

  \bibitem{AllSha05} J.-P. Allouche, J. Shallit, G. Skordev,
    Self-generating sets, integers with missing blocks, and
    substitutions, {\em Discrete Math.} {\bf 292} (2005), 1--15.

  \bibitem{BHMV} V. Bruy\`ere, G. Hansel, C. Michaux, R. Villemaire,
    Logic and $p$-recognizable sets of integers, {\em Bull. Belg.
      Math. Soc.} {\bf 1} (1994), 191--238.

  \bibitem{Cob68b} A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines, in \emph{IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory}, 1968, pp. 51--60. Also appeared as IBM Research Technical Report {\bf RC-2178}, August 23, 1968.

  \bibitem{Cob69} A. Cobham, On the base-dependence of sets of numbers
    recognizable by finite automata, {\em Math. Systems Theory} {\bf
      3} (1969), 186--192.

  \bibitem{cob1972} A. Cobham, Uniform tag sequences, {\em Math.
      Systems Theory} {\bf 6} (1972), 164--192.

  \bibitem{Eil74} S. Eilenberg, {\em Automata, Languages, and
      Machines}, Vol. A., Pure and Applied Mathematics, Vol. {\bf 58},
    Academic Press, 1974.

  \bibitem{Fro} C. Frougny, Representations of numbers and finite
    automata, {\em Math. Systems Theory} {\bf 25} (1992), 37--60.

  \bibitem{garth} D. Garth, A. Gouge, Affinely self-generating sets
    and morphisms, {\em J. Integer Seq.} {\bf 10} (2007), Article 07.1.5.

  \bibitem{Gra08} A. Granville, Smooth numbers: computational number theory and beyond, in
  J. P. Buhler, P. Stevenhagen, eds., \emph{Algorithmic number theory: lattices, number fields, curves and cryptography}, Math. Sci. Res. Inst. Publ. {\bf 44}, Cambridge University Press, 2008, pp. 267--323.

  \bibitem{HW} G. H. Hardy, E. M. Wright, {\em Introduction to the
      Theory of Numbers}, Oxford University Press, 1985.

  \bibitem{KLR} T. K\"arki, A. Lacroix, M. Rigo, On the recognizability of self-generating sets, in R. Kr\'alovi\v c, D. Niwi\'nski, eds., \emph{Proceedings of the 34st International Symposium on Mathematical Foundations of Computer Science, Bratislava, August 24 - 28, 2009}, Lecture Notes in Comput.
Sci. {\bf 5734} (2009), 525--536.

  \bibitem{Kim00} C. Kimberling, A self-generating set and the golden
    mean, {\em J. Integer Seq.} {\bf 3} (2000), Article 00.2.8.

\bibitem{Kim04} C. Kimberling, Affinely recursive sets and orderings
  of languages, {\em Discrete Math.} {\bf 274} (2004), 147--159.

\bibitem{LR} P. B. A. Lecomte, M. Rigo, Numeration systems on a regular
  language, {\em Theory Comput. Syst.} {\bf 34} (2001), 27--44.

\bibitem{Lot02} M. Lothaire, {\em Algebraic Combinatorics on Words},
  Encyclopedia of Mathematics and its Applications, {\bf 90},
  Cambridge University Press, 2002.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 68Q45; Secondary 68R15, 11B85.

\noindent \emph{Keywords: }
self-generating set, recognizability, numeration systems, multiplicatively independent integers, Fibonacci word.

\bigskip
\hrule
\bigskip


\noindent (Concerned with sequences \seqnum{A000045}, \seqnum{A000201},
\seqnum{A001950}, \seqnum{A003754}, \seqnum{A003849}, \seqnum{A052499}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 16 2009;
revised version received  January 21 2010.
Published in {\it Journal of Integer Sequences}, January 27 2010.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}