%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% V. BRUYERE: Latex file "Automata and Numeration Systems"  SLC 35
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{article}

\usepackage{amsfonts}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{conjecture}{Conjecture}
\newtheorem{example}{Example}
\newtheorem{question}{Question}


\hsize=12cm



\def\N{\mathbb N}
\def\Z{\mathbb Z}
\def\F{\mathbb F}
\def\.{\enspace .}
\def\,{\enspace ,}
\def\iff{if and only if}


\input{psfig.sty}

%-----------------------------------------------------------------------------
\begin{document}
\title{Automata and Numeration Systems\thanks{This work was partially supported by ESPRIT-BRA Working Group 6317 {\it ASMICS}}}

\author{V\'eronique Bruy\`ere \\
Universit\'e de Mons-Hainaut, \\
15 Avenue Maistriau, \\
B-7000 Mons, Belgium. \\
{\tt vero@sun1.umh.ac.be}}


\date{}
\maketitle
%-----------------------------------------------------------------------------

\section{Introduction}	\label{sec 1}
%--------------------

This article is a short survey on the following problem: given a set $X \subseteq \N$, find a ``simple algorithm'' accepting $X$ and rejecting $\N \setminus X$. By simple algorithm, we mean a finite automaton, a substitution, a logical formula,~\ldots  

We will see that these algorithms strongly depend on the way one represents the integers. However, once the base of representation is fixed, these models are all equivalent. 

This article is divided into two parts. Standard bases like base $10$ are first considered. The properties are then generalized to nonstandard bases like the Fibonacci one. No proofs are given, but several examples try to explain the results.  

The state of the art on this subject was presented at the ``S\'eminaire Lotharingien de Combinatoire", Hesselberg, Germany, 4--6 October 1995.

%-----------------------------------------------------------------------------
\section{Standard Numeration Systems}	\label{sec 2}
%------------------------------------
\subsection{Dependence on the Base}	\label{dep_base}
%----------------------------------
We begin with an example: the set $X$ of powers of two
	$$X = \{2^n ~|~ n \in \N \} \.$$
In base $2$, $X$ is represented as the set of binary words equal to $X_2 = \{1,10,100,1000, \ldots\}$. The {\it finite automaton} of Figure \ref{fig1} accepts $X$ because the words of $X_2$ (with any number of leading zeroes) are exactly the labels of the paths going from the {\it initial state} $a$ to the {\it final state} $b$. We say that $X$ is {\it $2$-recognizable}.

\begin{figure}
\centerline{\hbox{\psfig{figure=fig1.eps,height=2cm}}}
\caption{Automaton for the powers of two in base 2. \label{fig1}}
\end{figure}

In base $4$, there is also a finite automaton accepting $X$ (see Figure \ref{fig2}). The set $X$ is represented in base $4$ as $X_4 = \{1,2,10,20,100,200,\ldots\}$ and the words of $X_4$ over the alphabet $\{0,1,2,3\}$ are the labels of the paths from state $a$ to $b$ in Figure \ref{fig2} (leading zeroes are allowed). The set $X$ is then $4$-recognizable. 

\begin{figure}
\centerline{\hbox{\psfig{figure=fig2.eps,height=2.65cm}}}
\caption{Automaton for the powers of two in base 4. \label{fig2}}
\end{figure}

The automaton in base $4$ is easily constructed from the automaton in base $2$. The three states are identical, the arrows of the second automaton are exactly the paths with length $2$ of the first one. Indeed letters $0$, $1$, $2$, $3$ in base $4$ correspond to words $00$, $01$, $10$, $11$ in base $2$.

The set $X$ written in base $3$ is $X_3 = \{1,2,11,22,121,1012,\ldots\}$. No regularity appears inside the first words of $X_3$. Does this mean that $X$ is {\it not} $3$-recognizable?  

To answer this question, we are going to state some results, in particular the famous Cobham's theorem. 

Given a base $p \geq 2$, a set $X \subseteq \N$ is called {\it $p$-recognizable} if $X$ written in base $p$ is accepted by a finite automaton. Two bases $p, q \geq 2$ are said {\it multiplicatively dependent} if $p = r^k$, $q = r^l$ for some $r, k, l \in \N$. Otherwise, they are {\it multiplicatively independent}. The relation ``to be multiplicatively dependent'' divides $\N \setminus \{0,1\}$ into equivalence classes $\{ \{2,4,8,\ldots\}$, $\{3,9,27,\ldots\}$, $\{5,25,125,\ldots\}$, $\{6,36,216\}$, $\ldots \}$.  

It is rather easy to prove that {\it inside a class}, the existence of an automaton accepting $X \subseteq \N$ is independent of the base (remember the example above with bases $2$ and $4$).

\begin{proposition} Let $p, q \geq 2$ be two multiplicatively dependent bases. Then a set $X \subseteq \N$ is $p$-recognizable \iff\ it is $q$-recognizable. 
\end{proposition}

Some sets $X$ admit a finite automaton in {\it any} base. These are the {\it ultimately periodic} sets, equal to finite unions of arithmetic progressions, like the set $X = \{3n ~|~ n \in \N\} \cup \{3n+1 ~|~ n \in \N \}$.

\begin{proposition}
Let $X \subseteq \N$ be an ultimately periodic set, then $X$ is $p$-recognizable for any $p \geq 2$.
\end{proposition}

Cobham's theorem \cite{Co69} states that ultimately periodic sets are the only ones to be recognizable in every base. It states more: $X$ is ultimately periodic as soon as it is recognizable in two bases chosen in two distinct equivalence classes. This result shows that the set $X$ of powers of two cannot be $3$-recognizable, as this set is not ultimately periodic.

\begin{theorem}	\label{cobham}
Let $p, q \geq 2$ be two multiplicatively independent bases. If a set $X \subseteq \N$ is $p$-recognizable and $q$-recognizable, then $X$ is ultimately periodic. 
\end{theorem}

The reader is referred to Chapter 5 of Eilenberg's book \cite{Ei74} for properties of $p$-recognizable sets. Cobham's proof \cite{Co69} is only 4 pages long, but Eilenberg says that ``it is a challenge to find a more reasonable proof''. The first comprehensible proof is Hansel's one \cite{Ha82,Pe90}. Other authors have recently found simple logical proofs \cite{MV93}. An extension of Cobham's theorem to subsets $X$ of $N^m$ with $m \geq 2$ is due to Semenov \cite{Se77}. The proof of Semenov is difficult; simpler proofs are available in \cite{Mu91,BHMV94}, \cite{MV95} and \cite{Bes96a}. Fagnot \cite{Fa95} has recently extended Cobham's theorem where the set $X$ is replaced by two sets $X, Y$ with the same ``set of factors''.


\subsection{Equivalence of the Models}	\label{equiv_models}
%------------------------------------

We again consider the example $X$ of the powers of two and the (fixed) base $2$. We already know that $X$ is $2$-recognizable. 

It is also {\it $2$-substitutive} in the following way. There exists a {\it $2$-substitution} $f : A = \{a,b,c\} \rightarrow A^2$ and a projection $g : A \rightarrow \{0,1\}$  		
	$$\begin{array}{llllllllll}
	f &:& a &\rightarrow& ab & \quad \quad g &:& a &\rightarrow& 0 \\
	  & & b &\rightarrow& bc &               & & b &\rightarrow& 1 \\
	  & & c &\rightarrow& cc &               & & c &\rightarrow& 0 \.
	\end{array}$$
In this situation, the algorithm accepting $X$ runs as follows: infinitely iterate $f$ on letter $a$, apply $g$ on the generated infinite word. Notice that this infinite word is a fixpoint of $f$ because $f(a)$ begins with $a$.
	$$\begin{array}{clclclclcll}
	a &\rightarrow& ab &\rightarrow& abbc &\rightarrow& abbcbccc &\rightarrow& \ldots \\
	\downarrow&     &\downarrow&       &\downarrow&           &\downarrow& \\
	0 &\rightarrow& 01 &\rightarrow& 0110 &\rightarrow& 01101000 &\rightarrow& \ldots
	  &\rightarrow& \underline{X} \.
	\end{array}$$
The generated binary infinite word is precisely the {\it characteristic word} $\underline{X}$ of $X$ 	
	$$n \in X \Leftrightarrow \underline{X}_n = 1 \.$$

Another model to accept $X$ uses formal series. With $X$ we associate the {\it formal series}	
	$$X(y) = \sum_{n=0}^{\infty} y^{2^n} = y + y^2 + y^4 + \ldots \.$$
The set $X$ is called {\it $2$-algebraic} because the series $X(y)$ is algebraic over $\F_2[y]$, i.e., it is root of the polynomial $p(t) = t^2 + t + y$ with coefficients in $\F_2[y]$. Indeed, remember that in the field $\F_2$ with characteristic $2$, one has $1 + 1 = 0$.  

The last model uses logical formulas. Let $\langle  \N, +, V_2 \rangle$ be the logical {\it structure} where $+$ denotes the usual addition in $\N$ and $V_2(x) = y$ means that $y$ is the greatest power of two dividing $x$. The computation of $y = V_2(x)$ is easy if $x$ is written in base $2$: if the representation of $x$ is $u10^n$, then the representation of $y$ is $10^n$. With this structure, we can write {\it first-order formulas} with variables describing $\N$, the equality $=$, the two functions $+$ and $V_2$, the connectives $\vee, \wedge, \neg, \rightarrow, \leftrightarrow$ and the quantifiers $\exists, \forall$ (on the variables). 

We say that the set $X$ of powers of two is {\it $2$-definable} because $X$ is defined by the formula $\varphi(x)$ equal to $V_2(x) = x$. Another example of $2$-definable set is $\{3n ~|~ n \in \N \}$ using the formula $(\exists y)(x = y + y + y)$.

Let us now give the general definitions for a fixed base $p \geq 2$. The first one is the notion of $p$-recognizable set introduced in Subsection \ref{dep_base}. A set $X \subseteq \N$ is called {\it $p$-substitutive} if there exist a {\it $p$-substitution} $f : A \rightarrow A^p$ (with $f(a)$ beginning with $a$ for some $a \in A$) and a projection $g : A \rightarrow \{0,1\}$ such that the characteristic infinite word $\underline{X}$ of $X$ is equal to $g(f^{\omega}(a))$. If $p$ is a prime number, $X$ is said to be {\it $p$-algebraic} if the formal series $X(y) = \sum_{n \in X} y^n$ is algebraic over $K[y]$ with $K$ a field with characteristic $p$. Finally, we say that $X$ is {\it $p$-definable} if $X$ equals $\{ x \in \N ~|~ \varphi(x) \mbox{ is true } \}$ where $\varphi(x)$ is a first-order formula of the structure $\langle \N, +, V_p \rangle$. Recall that $V_p(x) = y$ means that $y$ is the greatest power of $p$ dividing $x$. 

As shown on the example above, the four models are equivalent.

\begin{theorem} \label{thm_equiv}
Let $p \geq 2$ and $X \subseteq N$. Are equivalent\\
1. $X$ is $p$-recognizable,\\
2. $X$ is $p$-substitutive,\\
3. $X$ is $p$-algebraic (if $p$ is prime),\\
4. $X$ is $p$-definable.
\end{theorem}

Theorem \ref{thm_equiv} collects the works of several authors. Equivalence $(1) \Leftrightarrow (2)$ is proved in \cite{Co72} where Cobham calls ``tag systems" the $p$-substitutions. 

Let us show on the example of the powers of two, how substitutions simulate automata. Remember that this set is $2$-substitutive, thanks to $f$ defined by $f(a) = ab$, $f(b) = bc$, $f(c) = cc$, and $g$ defined by $g(a) = 0$, $g(b) = 1$, $g(c) = 0$. The $2$-substitution $f$ simulates the transitions of the automaton of Figure \ref{fig1}. Indeed the alphabet $A$ used by $f$ is the set of states $\{a,b,c\}$ of the automaton. The image of $a$ by $f$ is $ab$ because there is an arrow from state $a$ to state $a$ labelled by $0$ and an arrow from state $a$ to state $b$ labelled by $1$. The iteration of $f$ on the initial state $a$ indicates the list of states reached by binary words of length $1$, $2$, $3$, \ldots  The projection $g$ indicates, by a $1$, which states are final.
{\scriptsize	
	$$\begin{array}{lllllllllllllllllll}		
	&								&	0&1 &           & 00&01&10&11 &           & 000&001&010&011&100&101&110&111 \\
	a &\rightarrow& a&b &\rightarrow& a & b& b& c &\rightarrow&	a  &b  &b  &c  &b  &c  &c  &c  \\
	\downarrow \\
	0 &\rightarrow& 0&1 &\rightarrow& 0 & 1& 1& 0 &\rightarrow&	0  &1  &1  &0  &1  &0  &0  &0  
	\end{array}$$
}

Equivalence $(1) \Leftrightarrow (3)$ is proved in \cite{CKMR}.

Equivalence $(1) \Leftrightarrow (4)$ is due to B\"uchi \cite{Bu60}, with a proof only for base $2$ and structure $\langle \N, +, P_2 \rangle$ instead of $\langle  \N, +, V_2 \rangle$ (predicate $P_2(x)$ means that $x$ is a power of $p$). In a review of B\"uchi's paper, MacNaughton \cite{MacN63} says that predicate $P_2$ is not correct and suggests predicate $e_2(x,y)$ meaning that $y$ is a power of $2$ which appears with digit $1$ in the representation of $x$ in base $2$. In \cite{Br85}, B\"uchi's paper is corrected and generalized to any base $p$ with structure $\langle \N, +, V_p \rangle$ instead of $\langle \N, +, P_p \rangle$. Moreover the proof of $(4) \Rightarrow (1)$ uses techniques developed by Hodgson in \cite{Ho83}. The other implication $(1) \Rightarrow (4)$ is first simplified in \cite{MP86} and then in \cite{Vi92}.

The characterization of automata by formulas is plenty of information for the following reasons. Addition can be checked by a finite automaton. The case of base $2$ is given on Figure \ref{fig3}: the two states $a, b$ indicate correct computation without and with carry respectively, the state $c$ indicates uncorrect computation. Notice that words must be read from right to left.

\begin{figure}
\centerline{\hbox{\psfig{figure=fig3.eps,height=6cm}}}
\caption{Automaton for the addition in base 2. \label{fig3}}
\end{figure}


Multiplication cannot be checked by a finite automaton (because it cannot be defined by a formula of $\langle \N, +, V_p \rangle$). Only multiplication by a constant is allowed since $c * y$, with $c$ an integer constant, is defined in $\langle \N, +, V_p \rangle$ by $y + \cdots + y$ ($c$ times).  The set $X$ whose ``elements are numbers $27*y$ with $y = z+1$ and $z$ divisible by $4$'' is $p$-recognizable for any $p \geq 2$. Indeed, $X$ is definable by the following formula $\varphi(x)$ of $\langle \N, + \rangle$ which is a substructure of $\langle \N, +, V_p \rangle$  	
$$(\exists y)(\exists z)(\exists t) (x = 27*y) \wedge (y = z+1) \wedge (z = 4*t)$$ 
(constants are definable in $\langle \N, + \rangle$). A proof based on automata would be rather tedious.

Hodgson's paper \cite{Ho83} shows that $\N$, $=$, $+$ and $V_p$ are the ``core'' of the automata. It describes a generic method to translate a formula of $\langle \N, +, V_p \rangle$ into a finite automaton, as soon as the ``basic'' automata for $\N$, $\{ (x,y) \in \N^2 ~|~ x = y \}$, $\{ (x,y,z) \in \N^3 ~|~ x+y=z \}$ and $\{ (x,y) ~|~ V_p(x)=y \}$ are known.

Finally, notice \cite{MP86} that the structure $\langle \N, +, V_p \rangle$ has the same expressive power than the structure $\langle \N,+,e_p(x,y) \rangle$ proposed by MacNaughton. Notice also that B\"uchi has really made a mistake by using $\langle \N, +, P_p \rangle$ instead of $\langle \N, +, V_p \rangle$ which is more powerful than $\langle \N, +, P_p \rangle$ \cite{De91,Se84,CP86,Br85}.


%-----------------------------------------------------------------------------
\section{Nonstandard Numeration Systems} %---------------------------------------

\subsection{Representations of Integers}
%---------------------------------------

The Fibonacci sequence can be used as a nonstandard base. For instance, the integer sixteen is represented as the following binary word{\bf s} 
	$$\begin{array}{llrllllll}	
	\ldots & 34 & 13 & 8 & 5 & 3 & 2 & 1 \\
	\hline
	&    &  1 & 0 & 0 & 1 & 0 & 0 \\
	&    &  1 & 0 & 0 & 0 & 1 & 1 \\
	&    &    & 1 & 1 & 1 & 0 & 0 \\
	&    &    & 1 & 1 & 0 & 1 & 1	
	\end{array}$$
Among these four representations, one is more natural, the first one given by the Euclidean algorithm. We call it the {\it normalized representation} of sixteen in the Fibonacci base.


More generally \cite{Fr85}, a {\it base} or {\it numeration system} is a striclty increasing sequence $U = (U_n)_{n \in \N}$ of integers such that
\begin{enumerate}
\item $U_0 = 1$ (in a way to represent all $n \in \N$), 
\item $\sup \frac{U_{n+1}}{U_n} < \infty$ (in a way to have a finite alphabet of digits when using the Euclidean algorithm).
\end{enumerate}
The {\it canonical alphabet} associated with $U$ is therefore $A_U = \{0,1,\ldots,c\}$ with $c$ maximum such that $c < \sup \frac{U_{n+1}}{U_n}$. A {\it representation} of $n \in \N$ is any word $a_k \cdots a_0 \in A_U^*$ such that $n = \sum_{l=0}^{k}a_lU_l$. The particular representation given by the Euclidean algorithm is called {\it normalized representation}. These definitions naturally generalize the usual bases $p \geq 2$.


\subsection{$U$-Recognizable Sets}
%---------------------------------

\begin{figure}
\centerline{\hbox{\psfig{figure=fig4.eps,height=2cm}}}
\caption{Automaton for $\N$ in Fibonacci base. \label{fig4}}
\end{figure}

Let $U$ be a numeration system. A set $X \subseteq \N$ is {\it $U$-recognizable} is the normalized representations of the elements of $X$ are accepted by a finite automaton. Figures \ref{fig4} and \ref{fig5} show two examples for the Fibonacci base, respectively $X = \N$ and $X = \{ n \in \N ~|~$ the normalized representation of $n$ has an even number of $1$'s $\}$.

\begin{figure}
\centerline{\hbox{\psfig{figure=fig5.eps,height=4.7cm}}}
\caption{Automaton for Thue-Morse set in Fibonacci base. \label{fig5}}
\end{figure}

To get a logical characterization of $U$-recognizable sets, as it was done for standard bases in Theorem \ref{thm_equiv}, the first task is the construction of a finite automaton for the set $\N$, the equality $=$, the addition $+$ and the function $V_U$. This is done in the next sections. 


\subsection{$U$-Recognizability of $\N$}	\label{N}
%---------------------------------------

Contrarily to standard bases $p \geq 2$, for some numeration systems, a finite automaton for $\N$ does not exist.

\begin{proposition} {\rm \cite{Sh92,Lo95}}	\label{rec}
Let $U$ be a numeration system. If $\N$ is $U$-recognizable, then $U$ satisfies a linear recurrence relation with integer coefficients.
\end{proposition}

For instance, if $U$ is the Fibonacci base, we know that $\N$ is $U$-recognizable (see Figure \ref{fig4}) and we have $U_n = U_{n-1} + U_{n-2}$, for all $n \geq 2$. The same holds for the usual base $10$ for which $U_n = 10 U_{n-1}$. 

The converse of Proposition \ref{rec} is false, since $\N$ is not $U$-recognizable for the numeration system $U$ defined by the recurrence $U_n = 2U_{n-2} + U_{n-3}$ and the initial conditions $U_0 = 1$, $U_1 = 2$ and $U_2 = 4$.

Hollander \cite{Hol95} has recently described which recurrence relations allow a finite automaton for $\N$, under the hypothesis that
	 $$\lim_{n \rightarrow \infty} \frac{U_{n+1}}{U_n} = \theta$$ 
for some real number $\theta > 1$. His description is strongly related to the {\it $\theta$-expansion} $e_{\theta}(1)$ of $1$ defined as follows \cite{Pa60}. Compute by the greedy algorithm
	$$1 = \sum_{i=1}^{\infty} \frac{d_i}{\theta^i} \.$$
Then $e_{\theta}(1)$ is equal to $d_1d_2 \cdots d_i \cdots$.

For instance, for the Fibonacci base, $\lim \frac{U_{n+1}}{U_n} = \varphi = \frac{1 + \sqrt{5}}{2}$ and $1 = \frac{1}{\varphi} + \frac{1}{\varphi^2}$. For the decimal numeration system, $e_{\theta}(1) = 10$. For the numeration system $U_n = 3U_{n-1} - U_{n-2}$, with $U_0 = 1$, $U_1 = 3$, we have $\lim \frac{U_{n+1}}{U_n} = \varphi^2$ and $e_{\varphi^2}(1) = 21^{\omega}$. Observe that in these three examples, $\N$ is $U$-recognizable and the $\theta$-expansion of $1$ is either finite or ultimately periodic. This is always the case.

\begin{proposition} {\rm \cite{Hol95}}
Let $U$ be a numeration system such that $\lim \frac{U_{n+1}}{U_n} = \theta > 1$. If $\N$ is $U$-recognizable, then $e_{\theta}(1)$ is finite or ultimately periodic
({\rm in this case, $\theta$ is called a $\beta$-number \cite{Pa60}}).
\end{proposition} 

Now, assume that the $\theta$-expansion of $1$ is ultimately periodic $$e_{\theta}(1) = d_1 \cdots d_l(d_{l+1} \cdots d_{l+p})^{\omega} \.$$
One verifies that $e_{\theta}(1)$ is root of the polynomial
	$$P_{l,p}(x) = x^{l+p} - \sum_{i=1}^{l+p}d_ix^{l+p-i} - x^l + \sum_{i=1}^{l}d_ix^{l-i} \.$$
If $l, p$ are minimal, then $P_{l,p}(x)$ is called {\it $\theta$-polynomial}, otherwise {\it extended $\theta$-polynomial}.

For example, for the previous system $U_n = 3U_{n-1} - U_{n-2}$, with $21^\omega$ as $\theta$-expansion of $1$, we get $P_{1,1}(x) = x^2 -3x + 1$ as $\theta$-polynomial and $P_{2,2}(x) = x(x+1)(x^2 -3x + 1)$ as an extended $\theta$-polynomial. One can notice that $P_{1,1}(x)$ is exactly the polynomial of the recurrence $U_n = 3U_{n-1} - U_{n-2}$ defining $U$.

We can now state the main theorem \cite{Hol95}.

\begin{theorem}	{\rm \label{holl}} 
Let $U$ be a numeration system such that $\lim \frac{U_{n+1}}{U_n} = \theta > 1$. Assume that $e_{\theta}(1)$ is ultimately periodic. Then $\N$ is $U$-recognizable if and only if $U$ satisfies a recurrence relation whose polynomial is a (extended) $\theta$-polynomial. 
\end{theorem} 

A little more complex characterization holds, when $e_{\theta}(1)$ is finite, instead of being ultimately periodic.


\subsection{Bertrand Numeration Systems}
%---------------------------------------


In \cite{Ber89}, particular numeration systems are introduced, which can be seen as the most natural numeration systems in the following sense. A system $U$ is called {\it Bertrand numeration system} if  		
	\begin{center}\begin{tabular}{ll}		
	& $w$ is a normalized representation \\
	$\Leftrightarrow$ & $w0^n$ is a normalized representation.
 	\end{tabular}\end{center}
For example, the Fibonacci base is a Bertrand numeration system. However, the system $U$ with the same reccurence $U_n = U_{n-1} + U_{n-2}$, but with different initial conditions $U_0 = 1$ and $U_1 = 4$, is not a Bertrand numeration system.

The next property characterizes Bertrand numeration systems.

\begin{theorem}
A system $U$ is a Bertrand numeration system if and only if 	
	$$\begin{array}{lll}
	U_0 $=$ 1 \\
	U_n = d_1 U_{n-1} + d_2 U_{n-2} + \ldots + d_n U_0 + 1 
	\end{array}$$
where $d_1d_2 \cdots d_i \cdots$ is the $\theta$-expansion $e_{\theta}(1)$ of $1$, for some $\theta > 1$.
\end{theorem}

Moreover, with respect to Theorem \ref{holl}, one can prove that for a Bertrand numeration system $U$, $\N$ is $U$-recognizable if and only if the polynomial of the recurrence defining $U$ is {\it the $\theta$-polynomial} of $\theta$ and the initial conditions are those described in the previous theorem.


\subsection{$\beta$-Numbers}
%---------------------------

Theorem \ref{holl} suggests the following question: ``which numbers $\theta > 1$ are $\beta$-numbers?''. As we will see, these numbers are related to {\it Pisot} (resp. {\it Salem}, {\it Perron}) numbers defined as algebraic integers $\theta > 1$ whose conjugates have modulus $< 1$ (resp. $\le 1$, $< \theta$). For instance, $\frac{1 + \sqrt{5}}{2}$ is a Pisot number, $\frac{5 + \sqrt{5}}{2}$ is a Perron number which is not a Salem number. The following strict inclusions hold 
$$\Z \subset ~\mbox{Pisot}~ \subset ~\mbox{Salem}~ \subset ~\mbox{Perron} \.$$  

The relation between $\beta$-numbers and these numbers is described in Figure \ref{fig} summarizing the next results.

\begin{figure}
\centerline{\hbox{\psfig{figure=fig.eps,height=3cm}}}
\caption{$\beta$-numbers inside the family of Perron numbers. \label{fig}}
\end{figure}

\begin{theorem}
Let $\theta$ be a $\beta$-number. Then the conjugates of $\theta$ have modulus respectively less than $2$ {\rm \cite{Pa60}}, $\frac{1 + \sqrt{5}}{2}$ {\rm \cite{So94,FLP94}}, $\theta$ {\rm \cite{Li84}}.
\end{theorem}

In \cite{Bl89}, Blanchard notes that if $\theta$ is a Perron number with some real conjugate $> 1$, then $\theta$ is not a $\beta$-number.

\begin{theorem} Let $\theta$ be respectively a Pisot number {\rm \cite{Ber77,Sc80}}, a Salem number with degree $4$ {\rm \cite{Bo89}}, then $\theta$ is a $\beta$-number.
\end{theorem}

Boyd \cite{Bo95b} has made several experimentations on Salem (not Pisot) numbers which suggest that, apart Salem numbers with degree $4$, the only Salem numbers being $\beta$-numbers should have degree $6$. In \cite{So94}, Solomyak has given the exact description of a compact subset of the plane which is the closure of the set of all conjugates of all $\beta$-numbers.


\subsection{$U$-Recognizability of the Addition}	\label{+}
%-----------------------------------------------

Let us now turn to the $U$-recognizability of the addition. The addition in standard bases $p \geq 2$ is well-known. However the addition in the Fibonacci base, can be surprizing, since left carry {\it and} right carry happen!

	$$\begin{array}{lrlllll}
	\ldots & 13 & 8 & 5 & 3 & 2 & 1 \\
	\\
	       &  0 & 0 & 1 & 0 & 1 & 0 \\
	       &  0 & 1 & 0 & 0 & 1 & 0 \\
	\hline 
	       &  1 & 0 & 0 & 1 & 0 & 1 
	\end{array}$$

A way to perform the addition of two numbers is to add them digit by digit without carry, and then to normalize the result \cite{Fr89}.

$$\begin{array}{lrllllll}
\ldots & 13 & 8 & 5 & 3 & 2 & 1 \\
\\
&  0 & 0 & 1 & 0 & 1 & 0 \\
&  0 & 1 & 0 & 0 & 1 & 0 \\
\hline 
&  0 & 1 & 1 & 0 & 2 & 0 & \mbox{addition without carry} \\	  
&  1 & 0 & 0 & 1 & 0 & 1 & \mbox{normalization}
\end{array}$$

Given a numeration system $U$, its canonical alphabet $A_U$ and some alphabet $B \subset \Z$, the normalization $\eta_{U,B}$ is a map replacing any $w \in B^*$ by the corresponding normalized representation (if it exists). Hence, if $\eta_{U,B}$ is computable by a finite automaton, with $B = 2A_U$, then the addition is $U$-recognizable. Figure \ref{fig6} shows a finite automaton for the normalization $\eta_{U,B}$ with $U$ the Fibonacci base and $B = \{0,1\}$.

\begin{figure}
\centerline{\hbox{\psfig{figure=fig6.eps,height=4cm}}}
\caption{Normalizer for the Fibonacci base. \label{fig6}}
\end{figure}

About the recognizability by a finite automaton of the normalization, and therefore of the addition, the known results only concern $\beta$-numbers $\theta > 1$ whose minimal polynomial is the polynomial of the recurrence satisfied by the numeration system $U$. The case of non minimal polynomials is open.

\begin{theorem} \cite{FS95}	\label{norm}
Let $U$ be a numeration system given by a linear recurrence whose polynomial is the minimal polynomial of a $\beta$-number.\\
1. If $\theta$ is a Pisot number, then $\eta_{U,B}$ is computable by a finite automaton, for any finite alphabet $B \subseteq \Z$,\\
2. if $\theta$ is a Perron number which is not Pisot, then $\eta_{U,B}$ is not computable by a finite automaton, for any finite alphabet $B \supseteq \{0,1,\ldots,c+1\}$, if $A_U = \{0,1,\ldots,c\}$. 
\end{theorem}
%
Another proof of the first part of Theorem \ref{norm} can be found in \cite{BH95}.


\subsection{$U$-Definable Sets and Cobham's Theorem} %--------------------------------------------------


As for standard bases $p \geq 2$, we define the logical structure $\langle \N, +, V_U \rangle$ where $V_U(x) = y$  means that $y$ is the smallest $U_n$ appearing in the normalized representation of $x$ with a non null digit. We say that $X \subseteq \N$ is $U$-definable if there exists a first-order formula of $\langle \N, +, V_U \rangle$ defining $X$. The following logical characterization uses the results of Subsection \ref{N} and \ref{+}.

\begin{theorem} {\rm \cite{BH95}}	\label{logic}
Let $U$ be a numeration system defined by a recurrence whose polynomial is the minimal polynomial of a Pisot number, then $X \subseteq \N$ is $U$-recognizable if and only if $X$ is $U$-definable.
\end{theorem}

Remember Cobham's theorem (Theorem \ref{cobham}) which states that the only sets recognizable in all standard bases $p \geq 2$ are the ultimately periodic ones.   As ultimately periodic sets are all definable in $\langle \N, + \rangle$, they are also definable in $\langle \N, +, V_U \rangle$, showing that they are $U$-recognizable for any system $U$ of Theorem \ref{logic}. This result was first proved in \cite{Fr89} by other techniques.

The contrary also holds under some hypotheses. This gives a Cobham's theorem for non standard bases. In \cite{PB96}, if $X \subseteq \N$ is $p$-definable and $U$-definable with $p \geq 2$ and $U$ a nonstandard numeration system as in Theorem \ref{logic}, then it is proved that $X$ is ultimately periodic. The result is still true in $N^m$. Another proof with $\theta$ a unitary Pisot number and in dimension 1 can already be found in \cite{Fab}. Very recently, Cobham's theorem has been extended to two nonstandard numeration systems $U$ and $U'$ in any dimension $m \geq 1$ \cite{Bes96b,Ha96}. Fabre's proof \cite{Fab} uses $U$-substitutions (see Subsection \ref{substi}), the proof in \cite{PB96} generalizes techniques developed in \cite{Mu91}, while Hansel's and B\`es' proofs \cite{Ha96,Bes96b} rely on two deep logical theorems established in \cite{MV93,MV95}. It seems that this last approach is the most powerful one.


\subsection{$U$-Substitutive Sets}	\label{substi}
%---------------------------------
Let us begin with an example. Figure \ref{fig4} is the minimal automaton for $\N$ in the Fibonacci base. This automaton can be ``simulated" by a substitution as follows. Let 
	$$\begin{array}{lllll}
	f &:& a &\rightarrow& ab \\ 
  & & b &\rightarrow& a 
\end{array}$$
This substitution describes the transition function on both states $a$ and $b$. The iteration of $f$ on the initial state $a$ works as follows.

$$\begin{array}{lllllllllllllll}
&           & 0&1 &           & 00&01&10 &        & 000&001&010&100&101 \\
a &\rightarrow& a&b &\rightarrow& a&b&a &\rightarrow& a&b&a&a&b &\rightarrow \ldots
\end{array}$$
%
The constructed infinite word $abaababaabaababa \cdots$ is such that the state at position $n$ equals $a$ (resp. $b$) \iff\ the normalized representation of $n$ in Fibonacci base goes from the initial state to state $a$ (resp. $b$).

More generally, we have the next property.

\begin{proposition} Let $U$ be a numeration system such that $\N$ is $U$-recognizable. Then there exists a canonical $U$-substitution $f_U$ which simulates the minimal automaton accepting $\N$. 
\end{proposition}

This notion of canonical substitution is introduced in \cite{Fa92} for Bertrand numeration systems. It has been generalized to any nonstandard base in \cite{BH95}. For classical bases $p \geq 2$, the canonical substitution is $f_p : a \rightarrow a^p$.

We now proceed with another example in the Fibonacci base $U$.  The automaton of Figure \ref{fig5} is simulated by the {\it $U$-substitution}	
$$\begin{array}{llllllllll}
f &:& a &\rightarrow & ab & \quad\quad g &:& a &\rightarrow& 1\\
& & b &\rightarrow & c  &   & & b &\rightarrow& 0\\
& & c &\rightarrow & cd &   & & c &\rightarrow& 0\\
& & d &\rightarrow & a  &   & & d &\rightarrow& 1\\ 
\end{array}$$
such that $f$ describes the transitions and $g$ the final states of the automaton.

Notice that the automaton of Figure \ref{fig5} is a ``splitting" of the automaton of Figure \ref{fig4}: merging states $a,c$, respectively $b,d$ of the second automaton leads to the first automaton. In the same way, function $f$ above is a ``splitting" of function $f_U$ defined at the beginning of this subsection.

Based on this example, given a numeration system $U$ such that $\N$ is $U$-recognizable, we call {\it $U$-substitution} any map $f$ which is a splitting of the canonical $U$-substitution $f_U$ associated with $U$.

For standard bases $p \geq 2$, as the canonical substitution is the map $f_p : a \rightarrow a^p$, all the splittings of $f_p$ are maps whose images are words with length $p$. These are exactly the $p$-substitutions introduced in Subsection \ref{equiv_models}. 

The next theorem generalizes the characterization of $p$-recognizable sets by $p$-substitutive sets.

\begin{theorem}	\label{truc}
Let $U$ be a numeration system such that $\N$ is $U$-recognizable. A set $X \subseteq \N$ is $U$-recognizable \iff\ there exist a $U$-substitution $f : B \rightarrow B^*$, a letter $a \in B$ and a map $g : B \rightarrow \{0,1\}$ such that 
	$$\underline{X} = g(f^{\omega}(a)).$$ 
\end{theorem}

This equivalence is proved in \cite{Fa92} for Bertrand numeration systems. The general case is solved in \cite{BH95}; the statement of Theorem \ref{truc} has been simplified to be more comprehensible. Another notion of substitution can be found in \cite{Sh88}.


%-------------------------------------------------------------
\begin{thebibliography}{111}

\bibitem{Ber77} A. Bertrand, D\'eveloppements en base de Pisot et r\'epartition modulo $1$, {\it C. R. Acad. Sci. Paris} {\bf 285} (1977) 419--421.

\bibitem{Ber89} A. Bertrand-Mathis, Comment \'ecrire les nombres entiers dans une base qui n'est pas enti\`ere, {\it Acta Math. Acad. Sci. Hungar.} {\bf 54} (1989) 237--241.

\bibitem{Bes96a} A. B\`es, Undecidable extensions of B\"uchi arithmetic and Cobham-Semenov theorem, {\it Technical report} {\bf 44}, LLAIC1, University of Auvergne, France (1996) 17 pages. 

\bibitem{Bes96b} A. B\`es, An extension of the Cobham-Semenov theorem, {\it preprint} (1996) 10 pages.

\bibitem{Bl89} F. Blanchard, $\beta$-expansions and symbolic dynamics, {\it Theoret. Comput. Sci.} {\bf 65} (1989) 131--141.

\bibitem{Bo89} D. Boyd, Salem numbers of degree $4$ have periodic expansions, {\it Th\'eorie des Nombres -- Number Theory}, J.M. de Koninck and C. Levesque, Eds., Walter de Gruyter \& Co., Berlin and New York (1989) 57--64.

\bibitem{Bo95b} D. Boyd, On the beta-expansion for Salem numbers of degree $6$, to appear in {\it Mathematics of Computation} (1995) 16 pages.

\bibitem{Br85} V. Bruy\`ere, Entiers et automates finis, {\it M\'emoire de fin d'\'etudes}, University of Mons, Belgium (1985).

\bibitem{BH95} V. Bruy\`ere, G. Hansel, Bertrand numeration systems and recognizability, submitted (1995) 22 pages. 

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

\bibitem{Bu60} J.R. B\"uchi, Weak second-order arithmetic and finite automata, {\it Z. Math. Logik Grundlag. Math.} {\bf 6} (1960) 66--92.

\bibitem{CP86} G. Cherlin, F. Point, On extensions of Presburger arithmetic, Proc. 4th Easter Model Theory conference, Gross K\"oris 1986 Seminarberichte 86, Humboldt Universit\"at zu Berlin (1986) 17--34. 

\bibitem{CKMR} G. Christol, T. Kamae, M. Mend\`es France, G. Rauzy, Suites alg\'ebriques, automates et substitutions, {\it Bull. Soc. Math. France} {\bf 108} (1980) 401--419.

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

\bibitem{Co72} A. Cobham, Uniform tag systems, {\it Math. Systems Theory} {\bf 6} (1972) 164--192.

\bibitem{De91} F. Delon, Personal communication (1991). 
  
\bibitem{Ei74} S. Eilenberg, {\it Automata, Languages and Machines}, Vol. A, Academic Press, New-York (1974). 

\bibitem{Fa92} S. Fabre, Substitutions et ind\'ependence des syst\`emes de num\'eration, {\it Th\`ese}, University Aix-Marseille II (1992).

\bibitem{Fab} S. Fabre, Une g\'en\'eralisation du th\'eor\`eme de Cobham, {\it Acta Arithmetica} {\bf 67} (1994) 197--208.

\bibitem{Fa95} I. Fagnot, Sur les facteurs des mots automatiques, to appear in {\it Theoret. Comput. Sci.} {\bf 172} (1995).

\bibitem{FLP94} L. Flatto, J.C. Lagarias, B. Poonen, The zeta function of the beta transformation, {\it Ergod. Theory Dynam. Sys.} {\bf 14} (1994) 237--266.

\bibitem{Fr85} A.S. Fraenkel, Systems of numeration, {\it Amer. Math. Monthly} {\bf 92} (1985) 105--114.

\bibitem{Fr89} C. Frougny, Syst\`emes de num\'eration lin\'eaires et automates finis, {\it Th\`ese d'Etat}, University Paris 7, France (1989).

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

\bibitem{FS95} C. Frougny, B. Solomyak, On representations of integers in linear numeration systems, to appear in {\it Ergod. Th. \& Dynam. Sys.}, M. Pollicott and K. Schmidt, Eds., London Mathematical Society Lecture Note Series, Cambridge University Press, and {\it LITP report} {\bf 94/54}, University Paris 7 (1995) 18 pages. 

\bibitem{Ha82} G. Hansel, A propos d'un th\'eor\`eme de Cobham, in: {\it Actes de la f\^ete des mots}, D. Perrin, Ed., Greco de Programmation, CNRS, Rouen (1982).

\bibitem{Ha96} G. Hansel, personal communication (1996).

\bibitem{Ho83} B.R. Hodgson, D\'ecidabilit\'e par automate fini, {\it Ann. Sci. Math. Qu\'ebec} {\bf 7} (1983) 39--57.

\bibitem{Hol95} M. Hollander, Greedy numeration systems and regularity, {\it preprint}  (1995) 21 pages.

\bibitem{Li84} D. Lind, The entropies of topological Markov shifts and a related class of algebraic integers {\it Ergod. Th. \& Dynam. Sys.} {\bf 4} (1984) 283--300.

\bibitem{Lo95} N. Loraud, Beta-shift, syst\`emes de num\'eration et automates, {\it preprint} (1995).

\bibitem{MacN63} R. MacNaughton, Review of \cite{Bu60}, {\it J. Symbolic Logic} {\bf 28} (1963) 100--102.

\bibitem{MP86} C. Michaux, F. Point, Les ensembles $k$-reconnaissables sont d\'efinissables dans $\langle \N,+,V_k \rangle$, {\it C. R. Acad. Sci. Paris} {\bf 303} (1986) 939--942. 

\bibitem{MV93} C. Michaux, R. Villemaire, Cobham's theorem seen through B\"uchi theorem, Proc. Icalp'93, {\it Lecture Notes inn Comput. Sci.} {\bf 700} (1993) 325--334.

\bibitem{MV95} C. Michaux, R. Villemaire, Presburger arithmetic and recognizability of natural numbers by automata: new proofs of Cobham's and Semenov's theorems, {\it Annals of Pure and Applied Logic} {\bf 77} (1996) 251--277.

\bibitem{Mu91} A. Muchnik, Definable criterion for definability in Presburger Arithmetic and its application, {\it preprint in Russian}, Institute of New Technologies (1991).

\bibitem{Pa60} W. Parry, On the $\beta$-expansions of real numbers, {\it Acta Math. Acad. Sci. Hungar.} {\bf 11} (1960) 401--416.

\bibitem{Pe90} D. Perrin, Finite automata, in: {\it Handbook of Theoretical Computer Science}, vol. B, J. Van Leeuwen, Ed., Elsevier (1990) 2--57.

\bibitem{PB96} F. Point, V. Bruy\`ere, On the Cobham-Semenov theorem, to appear in {\it Math. System Theory} (1996) 25 pages.

\bibitem{Sc80} K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers, {\it Bull. London. Math. Soc.} {\bf 12} (1980) 269--278.

\bibitem{Se77} A. L. Semenov, Presburgerness of predicates regular in two number systems (in Russian), {\it Sibirsk. Mat. Zh.} {\bf 18} (1977) 403--418, English translation, {\it Siberian Math. J.} {\bf 18} (1977) 289-299.

\bibitem{Se84} A. L. Semenov, On certain extensions of the arithmetic of addition of natural numbers (in Russian), {\it Izv. Akad. Nauk. SSSR ser. Mat.} {\bf 47} (1983) 623--658, English translation, {\it Math. USSR-Izv.} {\bf 22} (1984) 587--618.

\bibitem{Sh88} J. Shallit, A generalization of automatic sequences, {\it Theoret. Comput. Sci.} {\bf 61} (1988) 1--16.

\bibitem{Sh92} J. Shallit, Numeration systems, linear recurrences and regular sets, {\it Lect. Notes Comput. Sci.} {\bf 623} (1992) 89--100.

\bibitem{So94} B. Solomyak, Conjugates of beta-numbers and the zero-free for a class of analytic functions, {\it Proc. London Math. Soc.} {\bf 68} (1994) 477--498.

\bibitem{Vi92} R. Villemaire, The theory of $\langle \N,+,V_k,V_l \rangle$ is undecidable, {\it Theoret. Comput. Sci.} {\bf 106} (1992) 337--349.

\end{thebibliography}

\end{document}

