\documentclass[12pt,reqno]{article}

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

\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\usetikzlibrary{matrix,arrows}

\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}

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

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

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

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{assumption}[theorem]{Assumption}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Symbolic Dynamics of $(-\beta)$-Expansions
}
\vskip 1cm
\large
K. Dajani and S. D. Ramawadh\\
Department of Mathematics\\
Utrecht University\\
Postbus 80.010 \\
3508 TA Utrecht\\
The Netherlands \\
\href{mailto:k.dajani1@uu.nl}{\tt k.dajani1@uu.nl} \\
\href{mailto:S.D.Ramawadh@uu.nl}{\tt S.D.Ramawadh@uu.nl}\\
\end{center}

\vskip .2 in

\newcommand{\ba}{\begin{eqnarray}}
\newcommand{\ea}{\end{eqnarray}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
%\newcommand{\cal}{\mathcal}
\newcommand{\T}{T_{-\beta}}
\newcommand{\Tl}{T_{L,-\beta}}
\newcommand{\Tr}{T_{R,-\beta}}
\newcommand{\dn}{d_{-\beta}}
\newcommand{\dl}{d_{L,-\beta}}
\newcommand{\dr}{d_{R,-\beta}}
\newcommand{\dls}{d^*_{L,-\beta}}
\newcommand{\drs}{d^*_{R,-\beta}}
\newcommand{\Sn}{S_{-\beta}}
\newcommand{\Sl}{S_{L,-\beta}}
\newcommand{\Sr}{S_{R,-\beta}}
\newcommand{\vectwo}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\vecthree}[3]{\begin{array}{c}#1\\#2\\#3\end{array}}


\begin{abstract}
We study shift spaces associated with a family of transformations
generating expansions in base $-\beta$, with $\beta>1$. We give a
complete characterization when these shift spaces are sofic or even
shifts of finite type.
\end{abstract}

\section{Introduction}
In 1957, R\'{e}nyi studied the expansions of numbers in base $\beta>1$.
He only considered the numbers in $[0,1)$, and only considered one
specific rule, the $\beta$-transformation, with which we could find
these expansions \cite{Ren57}. Many other mathematicians have studied
these expansions since then, of which the most famous result is a paper
by Parry \cite{Par60}, in which he gave quite an extensive description
of both ergodic and symbolic properties of the $\beta$-transformation
posed by R\'{e}nyi. Later on several others looked at other types of
$\beta$-expansions. Erd\H{o}s \cite{EJ91}, for example, studied lazy
$\beta$-expansions (the opposite, the greedy $\beta$-expansions were
studied by R\'{e}nyi). Dajani and Kraaikamp studied a whole class of
$\beta$-expansions \cite{DK03} and also random $\beta$-expansions
\cite{DK04,DV05}.

In 2009, Ito and Sadahiro \cite{IS09} studied $(-\beta)$-expansions in base $-\beta$, $\beta>1$. They introduced a transformation, the $(-\beta)$-transformation, which allowed them to find an expansion of the form
\ba\label{eq:1}
x = \sum_{n=1}^\infty \frac{x_n}{(-\beta)^n}, & & x_n\in\{0,1,\ldots,\lfloor\beta\rfloor\}
\ea 
of any number $x\in I:=\left[-\frac{\beta}{\beta+1},\frac{1}{\beta+1}\right)$. After having introduced this dynamical system, they continued their study of these expansions by introducing an order on the set of expansions and studying the resulting $(-\beta)$-shift. This approach was later continued by Frougny and Lai \cite{FL09}, who gave a detailed description of the symbolic properties of the $(-\beta)$-shift. Recently, others have considered different transformations generating $(-\beta)$-expansions. Dombek, Mas\'{a}kov\'{a} and Pelantov\'{a} 
\cite{DMP11} considered a generalization of the aforementioned approach. Dajani and Kalle \cite{DK11}, took an even more general approach by studying a whole class of transformations generating $(-\beta)$-expansions for $1<\beta<2$.

The aim of this paper is to study shift spaces associated with various transformations generating $(-\beta)$-expansions and to give a complete characterization when these shift spaces are sofic or shifts of finite type.

\section{The dynamical system}
Let $\beta>1$ be given. The set of numbers $x\in\RR$ that satisfy \eqref{eq:1} for certain coefficients $x_n\in\{0,1,\ldots,\lfloor\beta\rfloor\}$ is contained in the interval
\bea
I_{-\beta} := \left[-\frac{\beta\cdot\lfloor\beta\rfloor}{\beta^2-1},\ \frac{\lfloor\beta\rfloor}{\beta^2-1}\right].
\eea
We call the set ${\cal A}:=\{0,1,\ldots,\lfloor\beta\rfloor\}$ the \emph{canonical alphabet}. If $x$ has an expansion of the form \eqref{eq:1}, then we may refer to the right-hand side of \eqref{eq:1} as \emph{a $(-\beta)$-expansion of x}. Moreover, we can refer to the digits of the expansion explicitly as follows:
\bea
\dn(x) := (x_1,x_2,\ldots) & \textrm{and} & \dn(x,n) := x_n.
\eea
We may also write $x=(.x_1x_2\cdots)_{-\beta}$. Moreover, if a part is periodic we can show this by overlining it. For example, $(1,\overline{0,2})=(1,0,2,0,2,0,2,\ldots)$. If a sequence consists of only a periodic part, we will call it \emph{purely periodic}. If it consists of a pre-periodic and a periodic part, we will call it \emph{eventually periodic}. Now, suppose that $x\in I_{-\beta}$ with expansion $\dn(x)=(x_1,x_2,\ldots)$. It follows that
\bea
-\beta x-x_1 = \sum_{n=1}^\infty \frac{x_{n+1}}{(-\beta)^n}.
\eea
In particular, we see that $-\beta x-x_1\in I_{-\beta}$ as the right-hand side is another $(-\beta)$-expansion. Therefore, one should look at the family of maps $-\beta x-a$, $a\in{\cal A}$, on the interval $I_{-\beta}$. Figure \ref{fig:1} shows what happens for a specific choice for $\beta$.
\begin{figure}
\centering
\begin{tikzpicture}[scale=2.5]
    \draw[->] (-1.2,0) -- (0.8,0);
    \draw[->] (0,-1.2) -- (0,0.8);
    \draw[black!50!white] (0,-1) -- (0,0.62);
    \draw[black!50!white] (0.62,0) -- (-1,0);
    \draw[dashed] (-0.38,-1) -- (-0.38,0.62);
    \draw (-1,-1) rectangle (0.62,0.62);
    \draw[color=blue,thick] (-1,0.62) -- (0,-1);
    \draw[color=blue,thick] (-0.38,0.62) -- (0.62,-1);
    \draw (-1,-1) node [below] {$-1$} -- (-0.38,-1) node [below] {$-\frac{1}{\beta^2}$} -- (0.62,-1) node [below] {$\frac{1}{\beta}$};
\end{tikzpicture}
\caption{The maps $-\beta x-a$ with $a\in{\cal A}$ on $I_{-\beta}$ for $\beta=\frac{1+\sqrt{5}}{2}$.\label{fig:1}}
\end{figure}
Notice that there is a small subinterval for which there is more than one possibility for $a$ such that $-\beta x-a$ remains in $I_{-\beta}$ for all points in this subinterval. Such a subinterval will be called a \emph{choice region}. Other subintervals, where there is only one choice for $a\in{\cal A}$, are called \emph{uniqueness regions}. Note that this behaviour is not restricted to this specific base $-\beta$; in fact, it happens for all non-integer base $-\beta$. This is a consequence of our alphabet ${\cal A}$.

In any case, we need to specify a function $d:I_{-\beta}\to{\cal A}$, the \emph{digit function}, such that for any $x\in I_{-\beta}$ it follows that also $-\beta x-d(x)\in I_{-\beta}$. Henceforth, we will work with the following assumptions:
\begin{assumption}\label{ass:2.1}
The digit function $d:I_{-\beta}\to{\cal A}$ satisfies the following properties:
\begin{enumerate}
\item[i.] $d(x)$ is such that $x\in I_{-\beta}\Rightarrow -\beta x-d(x)\in I_{-\beta}$,
\item[ii.] $d$ is either left- or right-continuous everywhere,
\item[iii.] $d$ is nonincreasing on $I_{-\beta}$.
\end{enumerate}
\end{assumption}
The idea behind the assumptions on the digit function is that it divides the interval $I_{-\beta}$ into at most $\lfloor\beta\rfloor+1$ smaller intervals, where the intervals are all either left- or right-closed and each of the intervals has a digit from the alphabet ${\cal A}$ assigned to them. These digits are assigned in such a way that, from left to right, these digits are decreasing. This implies that all digits of ${\cal A}$ are actually used.

Property i of Assumption 2.1 is worth considering more carefully. As a consequence of our choice of alphabet ${\cal A}$, we have that for any $\beta>1$ and any $x\in I_{-\beta}$ there is at least one $a\in{\cal A}$ such that $-\beta x-a\in I_{-\beta}$. To see why, fix $x\in I_{-\beta}$ and consider the set $S(x)=\left\{-\beta x-a:\ a\in{\cal A}\right\}$. The smallest element of $S(x)$ cannot be greater than $\frac{\lfloor\beta\rfloor}{\beta^2-1}$ and the largest element of $S(x)$ cannot be smaller than $-\frac{\beta\cdot\lfloor\beta\rfloor}{\beta^2-1}$. Moreover, $I_{-\beta}$ has length strictly greater than $1$, whereas the difference between two consecutive digits in ${\cal A}$ is $1$. These observations imply that $S(x)\cap I_{-\beta}\neq\emptyset$.

The points where $d$ is discontinuous are called \emph{cut points}. The cut points always lie in choice regions, and the cut points divide these regions into smaller regions on which the digit function dictates which map $-\beta x-a$ to choose.

Using this digit function, we can finally pose our dynamical system. We define, for a given digit function $d$, the map 
\bea
\T(x) & := & -\beta x-d(x)
\eea
on $I_{-\beta}$. If we want to emphasize whether the underlying digit function is left- or right-continuous, we may write $\Tl(x)$ and $\Tr(x)$ respectively.
\begin{proposition}\label{prop:2.2}
Let $x\in I_{-\beta}$ be arbitrary and let $x_n := d\left(\T^{n-1}(x)\right)$. Then we have $x=(.x_1x_2\ldots)_{-\beta}$.
\end{proposition}
\begin{proof}
We show, by induction on $n$, that for all $n\geq 1$ we have 
\bea
x = \frac{\T^n(x)}{(-\beta)^n} + \sum_{k=1}^n \frac{x_k}{(-\beta)^k}.
\eea
By definition, we have $\T(x)=-\beta x-x_1$, which in turn is equivalent to $x=\frac{\T(x)}{-\beta}+\frac{x_1}{-\beta}$. Hence, the statement holds for $n=1$.

Now assume that the statement is true for some positive integer $m-1$. Since we know that $\T^m(x)=-\beta\T^{m-1}(x)-x_m$, we also have 
\bea
\T^{m-1}(x) = \frac{x_m}{-\beta}+\frac{T^m(x)}{-\beta}
\eea
and hence
\bea
x &=& \frac{\T^{m-1}(x)}{(-\beta)^{m-1}} + \sum_{k=1}^{m-1} \frac{x_k}{(-\beta)^k}\\
 &=& \frac{\frac{x_m}{-\beta}+\frac{T^m(x)}{-\beta}}{(-\beta)^{m-1}} + \sum_{k=1}^{m-1} \frac{x_k}{(-\beta)^k}\\
 &=& \frac{\T^m(x)}{(-\beta)^m} + \sum_{k=1}^m \frac{x_k}{(-\beta)^k}.
\eea
We see that the statement is true for $m$ as well. The proof is finished by noting that $\frac{\T^m(x)}{(-\beta)^m}\to 0$ as $m\to\infty$.
\end{proof}
The following example shows that the original $(-\beta)$-transformation posed by Ito and Sadahiro \cite{IS09} can be viewed as restrictions of our maps.
\begin{example}\label{ex:2.3}
Let the base be given by $\beta = \frac{1+\sqrt{5}}{2}$ and consider the map $\Tl$ with cut point $2-\sqrt{5}$. This map is shown in Figure \ref{fig:2}.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=2.5]
    \draw[->] (-1.2,0) -- (0.8,0);
    \draw[->] (0,-1.2) -- (0,0.8);
    \draw[black!50!white] (0,-1) -- (0,0.62);
    \draw[black!50!white] (0.62,0) -- (-1,0);
    \draw (-1,-1) rectangle (0.62,0.62);
    \draw[color=blue,thick] (-1,0.62) -- (-0.236,-0.62);
    \draw[color=blue,thick] (-0.232,0.36) -- (0.62,-1);
    \filldraw[color=blue] (-0.236,-0.62) circle(0.5pt);
    \draw[color=blue] (-0.239,0.38) circle(0.5pt);
    \draw (-1,-1) node [below] {$-1$} -- (0,-1) node [below left] {$0$} -- (0.62,-1) node [below] {$\beta-1$};
    \draw[dashed] (-0.62,-0.62) rectangle (0.38,0.38);
\end{tikzpicture}
\caption{The map $\Tl$ from Example \ref{ex:2.3}.\label{fig:2}}
\end{figure}
The smaller box in Figure \ref{fig:2} is the $(-\beta)$-transformation as defined by Ito and Sadahiro. Hence, for this particular $\beta$ and choice of cut point, our map $\Tl$ is an extension of their $(-\beta)$-transformation.

Finding $(-\beta)$-expansions using this map $\Tl$ can be done using Proposition \ref{prop:2.2}. For example, we find $-\frac{1}{2}=\left(.\overline{100}\right)_{-\beta}$, which agrees with the result of Ito and Sadahiro. However, we can also find $-\frac{3}{4}=\left(.1\overline{011110}\right)_{-\beta}$; a result that cannot be found using the original $(-\beta)$-transformation.
\end{example}

\section{Admissibility and shift spaces}
Henceforth, whenever we refer to the map $\T$, we assume that it has been fixed beforehand. A sequence $(x_1,x_2,\ldots)\in{\cal A}^\NN$ is called \emph{$\T$-admissible} if we have $\dn(x)=(x_1,x_2,\ldots)$ for some $x\in I_{-\beta}$ and, moreover, the $(-\beta)$-expansion of $x$ generated by the map $\T$ (see Proposition \ref{prop:2.2}) has coefficients $x_1,x_2,\ldots$ A finite block is called $\T$-admissible if it appears in a $\T$-admissible sequence.

In order to nicely characterize the $\T$-admissible sequences, we introduce an order on the set of $\T$-admissible sequences: the \emph{alternate (lexicographical) order}. We write $(x_1,x_2,\ldots)\prec(y_1,y_2,\ldots)$ if and only if there exists some integer $k\geq 1$ such that $x_i=y_i$ for all $i<k$ and $(-1)^k(x_k-y_k)<0$. Also,  $(x_1,x_2,\ldots)\preceq(y_1,y_2,\ldots)$ means that either $(x_1,x_2,\ldots)\prec(y_1,y_2,\ldots)$ or $(x_1,x_2,\ldots)=(y_1,y_2,\ldots)$ holds.
\begin{proposition}\label{prop:3.1}
Let $\T$ be given. Let $x,y\in I_{-\beta}$ with $x\neq y$ be arbitrary and let $\dn(x)$ and $\dn(y)$ be the $(-\beta)$-expansions of respectively $x$ and $y$ generated by $\T$. Then $x<y$ if and only if $\dn(x)\prec\dn(y)$.
\end{proposition}
\begin{proof}
This has been shown in \cite[Lemma 3.1]{DK11} for $1<\beta<2$. We give the proof here for completeness. Write $\dn(x)=(x_1,x_2,\ldots)$ and $\dn(y)=(y_1,y_2,\ldots)$. Let $k\geq 1$ be the smallest integer for which $x_k\neq y_k$. Then we have
\bea
x = \frac{\T^{k-1}(x)}{(-\beta)^{k-1}}+\sum_{i=1}^{k-1}\frac{x_i}{(-\beta)^i} < \frac{\T^{k-1}(y)}{(-\beta)^{k-1}}+\sum_{i=1}^{k-1}\frac{y_i}{(-\beta)^i} = y
\eea
if and only if
\bea
\frac{\T^{k-1}(x)}{(-\beta)^{k-1}}<\frac{\T^{k-1}(y)}{(-\beta)^{k-1}}.
\eea
This latter inequality is, regardless of the parity of $k$,
equivalent to the inequality $$(-1)^k\left(x_k-y_k\right)<0,$$
since $x_k=d\left(\T^{k-1}(x)\right)$ (similar for $y_k$).
The statement now follows.
\end{proof}

We see that the alternate order respects the natural order on $\RR$ (as long as we compare $(-\beta)$-expansions generated by the same map $\T$). The behaviour of the map $\T$, and hence the generated $(-\beta)$-expansions, are determined by our choice for the cut points; two maps with the same base $\beta$ but different cut points will produce different $(-\beta)$-expansions for at least one point $x\in I_{-\beta}$. Therefore, we should pay extra attention to our cut points. Let $c$ be any cut point of a given map $\T$, then we define $\dl(c)$ to be $(-\beta)$-expansion generated by the left-continuous version of $\T$, regardless of the continuity of $\T$ itself (we define $\dr(c)$ similarly).
\begin{example}\label{ex:3.2}
We continue Example \ref{ex:2.3}. Our cut point is $2-\sqrt{5}$, and the $(-\beta)$-expansion of this point generated by the map is $2-\sqrt{5}=\left(.11\overline{0}\right)_{-\beta}$. Since the map in Example \ref{ex:2.3} is left-continuous, we know that $\dl(2-\sqrt{5})=(1,1,\overline{0})$. To determine $\dr(2-\sqrt{5})$ we modify the map in Example \ref{ex:2.3} such that it is right-continuous at $2-\sqrt{5}$ (all other points remain unchanged). The $(-\beta)$-expansion of $2-\sqrt{5}$ generated by this new map is $\dr(2-\sqrt{5})$. The reader is invited to verify that $\dr(2-\sqrt{5})=(0,0,1,\overline{0})$.
\end{example}
In order to state the following characterization of $\T$-admissible sequences neatly, we introduce a little more notation. Recall that the digit function divides $I_{-\beta}$ into smaller subintervals. A subinterval on which the digit function is constant with value $a$ will be denoted by $I_a$. Its left and right endpoint will be denoted by respectively $\ell_a$ and $r_a$. We can now characterize $\T$-admissible sequences as follows:
\begin{proposition}\label{prop:3.3}
The following hold:
\begin{itemize}
\item[(a)] If $(x_1,x_2,\ldots)$ is $\Tl$-admissible, then for all $n\geq 1$:
\begin{itemize}
\item if $x_n=\lfloor\beta\rfloor$, then $\dn(\ell_{\lfloor\beta\rfloor})\preceq(x_n,x_{n+1},\ldots)\preceq\dl(r_{\lfloor\beta\rfloor})$;
\item if $x_n=a\neq\lfloor\beta\rfloor$, then $\dr(\ell_a)\prec(x_n,x_{n+1},\ldots)\preceq\dl(r_a)$.
\end{itemize}
\item[(b)] If $(x_1,x_2,\ldots)$ is $\Tr$-admissible, then for all $n\geq 1$:
\begin{itemize}
\item if $x_n=0$, then $\dr(\ell_0)\preceq(x_n,x_{n+1},\ldots)\preceq\dn(r_0)$;
\item if $x_n=a\neq 0$, then $\dr(\ell_a)\preceq(x_n,x_{n+1},\ldots)\prec\dl(r_a)$.
\end{itemize}
\end{itemize}
\end{proposition}
\begin{proof}
We will only prove (a), since the proof of (b) is similar. If $x_n=\lfloor\beta\rfloor$, the result follows from Proposition \ref{prop:3.1}.

Now, suppose that $x_n=a\neq\lfloor\beta\rfloor$. Then, by Proposition \ref{prop:3.1} we only need to show that $\dr(\ell_a)\prec(x_n,x_{n+1},\ldots)$. Since the map is left-continuous, we know that $\dl(\ell_a,1)\neq a$ and hence $\ell_a<\Tl^{n-1}(x)$. Hence, there is a smallest integer $k\geq 1$ such that $\dr(\ell_a,k)\neq\dr(\Tl^{n-1}(x),k)$. Regardless of the parity of $k$, it follows that
\bea
(-1)^k\left(\dr(\ell_a,k)-\dr(\Tl^{n-1}(x)),k\right)<0,
\eea
which proves $\dr(\ell_a)\prec(x_n,x_{n+1},\ldots)$.
\end{proof}
The converse of Proposition \ref{prop:3.3} is not generally true. It is true in the case of Example \ref{ex:2.3} (we will see this later). We present the following Example in which the converse is not true.
\begin{example}\label{ex:3.4}
Consider the map $\Tl$ with $\beta=\frac{1+\sqrt{5}}{2}$ and cut point $0$, that is, the map $\Tl$ on $I_{-\beta}=[-1,\beta-1]$ given by: 
\bea
\Tl(x) & = & \begin{cases}
-\beta x-1, & \text{if $-1\leq x\leq 0$};\\
-\beta x, & \text{if $0<x<\beta-1$}.
\end{cases}
\eea
Then, according to Proposition \ref{prop:3.3}, a sequence $(x_1,x_2,\ldots)$ is $\Tl$-admissible if
\bea
(\overline{1,0})\preceq(x_n,x_{n+1}\ldots)\preceq(1,\overline{1,0}) & \textrm{or} & (\overline{0})\prec(x_n,x_{n+1},\ldots)\preceq(\overline{0,1})
\eea
holds for all $n\geq 1$. The sequence $(0,1,\overline{1,0})$ also satisfies this condition, but it is not $\Tl$-admissible. To see this, note that $(.01\overline{10})_{-\beta}=0$, whereas the $(-\beta)$-expansion of $0$ generated by the map $\Tl$ is $\dn(0)=(1,\overline{1,0})$.
\end{example}
Hence, the set of sequences that satisfy the series of inequalities in Proposition \ref{prop:3.3} might be a bit larger than the set of $\T$-admissible sequences. The problem arises whenever a cut point gets mapped onto some (not necessarily different) cut point after an odd amount of applications of the map $\T$.

Let $\T$ be given and let $c$ be any cut point of $\T$. We define
\bea
\dls(c) := \lim_{x\uparrow c} \dn(x) & \textrm{and} & \drs(c) := \lim_{x\downarrow c} \dn(x).
\eea
Notice that the definition of $\dls(c)$ does not require that the underlying map is left-continuous (similar for $\drs(c)$). Instead, these sequences should be thought of as ``improvements'' of respectively $\dl(c)$ and $\dr(c)$. The improvement follows from the following lemma:
\begin{lemma}\label{lem:3.5}
Let $\T$ be given and let $c$ be any cut point of $\T$. The following hold:
\begin{enumerate}
\item[(a)] There exists no $\Tl$-admissible sequence $(x_1,x_2,\ldots)$ such that we have $\dr(c)\prec(x_1,x_2,\ldots)\prec\drs(c)$.
\item[(b)] There exists no $\Tr$-admissible sequence $(x_1,x_2,\ldots)$ such that we have $\dls(c)\prec(x_1,x_2,\ldots)\prec\dl(c)$.
\end{enumerate}
\end{lemma}
\begin{proof}
We only prove (a), since the proof of (b) is similar. Suppose that the statement is false and let $(x_1,x_2,\ldots)$ be a $\Tl$-admissible sequence satisfying $\dr(c)\prec(x_1,x_2,\ldots)\prec\drs(c)$ and $x=(.x_1x_2\cdots)_{-\beta}$. By assumption, we have $x_1=\dr(c,1)$, and hence $x>c$.

Let $(x^n)_{n=1}^\infty$ be a decreasing sequence for which $\dn(x^n,1)=\drs(c,1)$ for all $n\geq 1$, where $\dn(x^n)$ is the $(-\beta)$-expansion of $x^n$ generated by $\T$. For all $m,n\geq 1$ with $m<n$ we have $\dn(x^n)\prec\dn(x^m)$ by Proposition \ref{prop:3.1}. It follows that $\drs(c)\preceq\dn(x^n)$ for all $n\geq 1$. Moreover, the sequence converges to $c$ and hence for some $k\geq 1$ we have $x^k<x$ and $\drs(c)\preceq\dn(x^k)\prec\dn(x)$. This latter is, however, a contradiction and hence the sequence $(x_1,x_2,\ldots)$ cannot exist.
\end{proof}
For any given map $\T$, computing the sequences $\dls(c)$ and $\drs(c)$, where $c$ is a cut point, is not hard. Fix $c$ and suppose we want to find $\dls(c)$. We present the following algorithm:
\begin{enumerate}
\item[1.] Start with $k:=1$, $\hat{T}_1:=\Tl$ and $c_0:=c$.
\item[2.] Compute $c_k:=\hat{T}_k(c_{k-1})$ and set
\bea
\dls(c,k) & := &
\begin{cases}
d^L(c_{k-1}), & \text{if $\hat{T}_k=\Tl$};\\
d^R(c_{k-1}), & \text{if $\hat{T}_k=\Tr$};
\end{cases}
\eea
where $d^L$ and $d^R$ are the digit functions of $\Tl$ and $\Tr$ respectively.
\item[3.] Let $m:=\max\{0\leq i<k: c_i\textrm{ is a cut point}\}$. If $c_k$ is a cut point and if $k-m$ is odd, then:
\begin{itemize}
\item if $\hat{T}_k=\Tl$, then $\hat{T}_{k+1}:=\Tr$;
\item if $\hat{T}_k=\Tr$, then $\hat{T}_{k+1}:=\Tl$;
\end{itemize}
and else $\hat{T}_{k+1}:=\hat{T}_k$.
\item[4.] Increase $k$ by one and go back to step 2.
\end{enumerate}
If we wish to find $\drs(c)$ instead, all that changes is that we should start with $\hat{T}_1:=\Tr$.
\begin{proposition}\label{prop:3.6}
The method described above for finding $\dls(c)$ and $\drs(c)$ is correct.
\end{proposition}
\begin{proof}
We only prove correctness for $\dls(c)$. Call the sequence obtained by the algorithm above $s_{L,-\beta}(c)$, then we need to show that $s_{L,-\beta}(c)=\lim_{x\uparrow c} \dn(x)$. For any integer $n\geq 1$, define (recall that $\ell_{s_{L,-\beta}(c,k)}$ denotes the left endpoint of the subinterval on which the digit function equals the $k$th digit of $s_{L,-\beta}(c)$):
\bea
\epsilon_n & := & \frac{1}{\beta^{n-1}}\min\left(\left\{\left|c_k-\ell_{s_{L,-\beta}(c,k+1)}\right|:\ 0\leq k\leq n,\ k \textrm{ even}\right\}\right.\\
 & & \cup \left.\left\{\left|c_k-r_{s_{L,-\beta}(c,k+1)}\right|:\ 0\leq k\leq n,\ k \textrm{ odd}\right\}\right) .
\eea
It follows that any $x\in(c-\epsilon_n,c)$ satisfies $\dl(x,i)=s_{L,-\beta}(c,i)$ for all $i\leq n$. It suffices to show that $\epsilon_n\neq 0$ for all $n\geq 1$. Suppose that $k\geq 1$ is the smallest integer such that $\epsilon_k=0$ and assume that $k$ is odd (the proof is similar for $k$ even). It follows that $c_k=r_{s_{L,-\beta}(c,k+1)}$, and, since $\hat{T}_{k+1}=\Tr$, we must hit $r_{-\beta}$ after an odd number of iterations (it cannot be any other cut point since that would imply $c_k=\ell_{s_{L,-\beta(c,k+1)}}\neq r_{s_{L,-\beta}(c,k+1)}$). It follows that $c_{k-1}$ is either a cut point or $-\frac{\beta\cdot\lfloor\beta\rfloor}{\beta^2-1}$. By iterating this argument it follows that $c$ must be an endpoint of $I_{-\beta}$. We have reached a contradiction since the endpoints are no cut points. It follows that $\epsilon_n>0$ for all $n\geq 1$.
\end{proof}
\begin{example}\label{ex:3.7}
We continue Example \ref{ex:3.4}. Since the orbit of $0$ never hits $0$ again under $\Tl$, we conclude that $\dls(0)=\dl(0)=(1,\overline{1,0})$. Under $\Tr$, however, $0$ hits itself after one iteration. Hence, we have $\drs(0,1)=0$ and continue iterating $\Tl$. At this point, we know the orbit of $0$ under $\Tl$ and therefore $\drs(0)$ is the concatenation of the single-digit block $(0)$ with $(1,\overline{1,0})$: $\drs(0)=(0,1,\overline{1,0})$.
\end{example}
\begin{example}\label{ex:3.8}
We continue Example \ref{ex:3.2}. Since the orbit of $2-\sqrt{5}$ never hits itself under both $\Tl$ and $\Tr$, we have $\dls(2-\sqrt{5})=\dl(2-\sqrt{5})=(1,1,\overline{0})$ and $\drs(2-\sqrt{5})=\dr(2-\sqrt{5})=(0,0,1,\overline{0})$.
\end{example}

\begin{remark}
The sequences $\dls(c)$ and $\drs(c)$ are concatenations of blocks of sequences of the form $\dl(\ell_a)$, $\dr(\ell_a)$, $\dl(r_a)$ and $\dr(r_a)$ where $a\in{\cal A}$.
\end{remark}

The following lemma is very important:
\begin{lemma}
Let $(x_1,x_2,\ldots)\in{\cal A}^\NN$. The following hold:\label{lem:3.10}
\begin{itemize}
\item[(a)] If for all $n\geq 1$ we have
\bea
\drs(\ell_{x_n})\preceq(x_n,x_{n+1},\ldots)\preceq\dl(r_{x_n}),
\eea
then every finite subblock of $(x_1,x_2,\ldots)$ is $\Tl$-admissible.
\item[(b)] If for all $n\geq 1$ we have
\bea
\dr(\ell_{x_n})\preceq(x_n,x_{n+1},\ldots)\preceq\dls(r_{x_n}),
\eea
then every finite subblock of $(x_1,x_2,\ldots)$ is $\Tr$-admissible.
\end{itemize}
\end{lemma}
\begin{proof}
We only prove (a), as the proof of (b) is similar. Suppose that $(x_1,x_2,\ldots)$ satisfies the given condition and define $x^{(k)}:=\sum_{n=k}^\infty \frac{x_n}{(-\beta)^{n-k+1}}$. Assume that there exist integers $s(k),t(k)>k$ such that:
\bea 
x_k\cdots x_{s(k)-1} = \drs(\ell_{x_k},1)\cdots\drs(\ell_{x_k},s(k)-k),\\
(-1)^{s(k)-k+1}\left(\drs(\ell_{x_k},s(k)-k+1)-x_{s(k)}\right)<0,
\eea
and
\bea
x_k\cdots x_{t(k)-1} = \dl(r_{x_k},1)\cdots \dl(r_{x_k},t(k)-k),\\ 
(-1)^{t(k)-k+1}\left(x_{t(k)}-\dl(r_{x_k},t(k)-k+1)\right)<0.
\eea
If either $s(k)$ or $t(k)$ does not exist, then there is nothing to prove. Let $y$ be a point such that $\dl(y,i)=\drs(\ell_{x_k},i)$ for $1\leq i\leq s(k)-k+1$, then
\bea
x^{(k)}-\ell_{x_k} & > & x^{(k)}-y\\
 &=& \sum_{n=s(k)}^\infty \frac{x_n}{(-\beta)^{n-k+1}} - \frac{\Tl^{s(k)-k}(y)}{(-\beta)^{s(k)-k}}\\
 &>& \frac{1}{(-\beta)^{s(k)-k}}\left(x^{s(k)}-\Tl^{s(k)-k}(y)\right),
\eea
from which it follows that
\ba\label{eq:3.2}
x^{(k)}-\ell_{x_k} &>& \begin{cases}
\frac{x^{s(k)}-\ell_{x_{s(k)}}}{(-\beta)^{s(k)-k+1}}, & \text{if $s(k)-k+1$ is odd};\\
\frac{x^{s(k)}-r_{x_{s(k)}}}{(-\beta)^{s(k)-k+1}}, & \text{if $s(k)-k+1$ is even}.
\end{cases}
\ea
Similarly, one can show that
\ba\label{eq:3.3}
r_{x_k}-x^{(k)} &>& \begin{cases}
\frac{r_{x_{t(k)}}-x^{t(k)}}{(-\beta)^{t(k)-k+1}}, & \text{if $t(k)-k+1$ is odd};\\
\frac{\ell_{x_{t(k)}}-x^{t(k)}}{(-\beta)^{t(k)-k+1}}, & \text{if $t(k)-k+1$ is even}.\\
\end{cases}
\ea
By iteratively applying the bounds in \eqref{eq:3.2} and \eqref{eq:3.3} we get a sequence of bounds that approach zero (as the numerator is bounded and the denominator goes to infinity). It follows that $l_{x_k}<x^{(k)}<r_{x_k}$ for all $k\geq 1$, which implies $\dl\left(x^{(1)}\right)=(x_1,x_2,\ldots)$.
\end{proof}

Using these new objects, we can make the inequalities in Proposition \ref{prop:3.3} more strict and obtain an equivalence.
\begin{theorem}
The following hold:\label{thm:3.9}
\begin{itemize}
\item[(a)] The sequence $(x_1,x_2,\ldots)$ is $\Tl$-admissible if and only if for all $n\geq 1$:
\begin{itemize}
\item if $x_n=\lfloor\beta\rfloor$, then $\dn(\ell_{\lfloor\beta\rfloor})\preceq(x_n,x_{n+1},\ldots)\preceq\dl(r_{\lfloor\beta\rfloor})$;
\item if $x_n=a\neq\lfloor\beta\rfloor$, then $\drs(\ell_a)\prec(x_n,x_{n+1},\ldots)\preceq\dl(r_a)$.
\end{itemize}
\item[(b)] The sequence $(x_1,x_2,\ldots)$ is $\Tr$-admissible if and only if for all $n\geq 1$:
\begin{itemize}
\item if $x_n=0$, then $\dr(\ell_0)\preceq(x_n,x_{n+1},\ldots)\preceq\dn(r_0)$;
\item if $x_n=a\neq 0$, then $\dr(\ell_a)\preceq(x_n,x_{n+1},\ldots)\prec\dls(r_a)$.
\end{itemize}
\end{itemize}
\end{theorem}
\begin{proof}
This has been proven for $1<\beta<2$ in \cite[Theorem 3.1]{DK11}. We give the proof for completeness. We only prove (a), since the proof of (b) is similar. The "only if" part follows from Proposition \ref{prop:3.3} and Lemma \ref{lem:3.5}. 

To prove the "if" part, suppose that $(x_1,x_2,\ldots)$ satisfies the given inequalities. From Lemma \ref{lem:3.10} it follows that every finite subblock $(x_n,\ldots,x_{n+k})$ is $\Tl$-admissible. It is sufficient to check that $(x_n,x_{n+1},\ldots)\neq\drs(\ell_{x_n})$ for all $n\geq 1$ such that $x_n\neq\lfloor\beta\rfloor$. However, this follows directly from the given inequalities.
\end{proof}

Let $\T$ be a $(-\beta)$-transformation such that $\T$ restricted to the interval $\left[-\frac{\beta}{\beta+1},\frac{1}{\beta+1}\right)$ is the Ito-Sadahiro transformation. While our condition in Theorem \ref{thm:3.9} is different from the condition found by Ito and Sadahiro \cite[Theorem 10]{IS09}, the two actually agree. This is because their transformation implicitly specifies the cut points. Moreover, these cut points are all mapped to $-\frac{\beta}{\beta+1}$. The following example illustrates this:
\begin{example}
Consider the map of Example \ref{ex:2.3} restricted to the interval $\left[-\frac{\beta}{\beta+1},\frac{1}{\beta+1}\right)$. Our condition in Theorem \ref{thm:3.9}(a), when restricted to this interval, becomes:
\ba\label{eq:3.1}
(1,\overline{0})\preceq (x_n,x_{n+1},\ldots)\preceq (1,1,\overline{0}) & \vee & (0,0,1,\overline{0})\prec (x_n,x_{n+1},\ldots)\prec (0,1,\overline{0})
\ea
for all $n\geq 1$. On the other hand, by Ito and Sadahiro \cite[Theorem 10]{IS09} we have:
\bea
(1,\overline{0})\preceq (x_n,x_{n+1},\ldots)\prec(0,1,\overline{0})
\eea
for all $n\geq 1$, which suggests that the sequences corresponding to the cut point are redundant. To see why this is the case, suppose that $(x_1,x_2,\ldots)$ satisfies \eqref{eq:3.1} for all $n\geq 1$. Fix $k\geq 1$ and assume for now that $x_k=1$, then we have $(x_k,x_{k+1},\ldots)\preceq(1,1,\overline{0})$ from which it follows that $(1,\overline{0})\preceq(x_{k+1},x_{k+2},\ldots)$. This condition, however, is already satisfied which means that we can reduce the first part of \eqref{eq:3.1} to $(1,\overline{0})\preceq(x_k,x_{k+1},\ldots)$. Similarly, we can reduce the second part of \eqref{eq:3.1} whenever $x_k=0$ and get
\bea
\begin{cases}
(1,\overline{0})\preceq(x_n,x_{n+1},\ldots), & \text{whenever $x_n=1$};\\
(x_n,x_{n+1},\ldots)\prec(0,1,\overline{0}), & \text{whenever $x_n=0$},
\end{cases}
\eea
which in turn can be neatly written as
\bea
(1,\overline{0})\preceq (x_n,x_{n+1},\ldots)\prec(0,1,\overline{0}),
\eea
which is the result by Ito and Sadahiro.
\end{example}
\section{Shifts and graphs}
In Theorem \ref{thm:3.9} we gave a characterization of the shift-invariant set of $\T$-admissible sequences. This set will be denoted with $S_T$. In order to turn $S_T$ into a shift space, we need to consider its closure. This closure will be called the \emph{$(-\beta)$-shift (for the underlying map $\T$)} and will be denoted by $\Sn$. The context should make it clear what the underlying map $\T$ is. If we wish to emphasize whether $\T$ is left- or right-continuous, we may write $\Sl$ and $\Sr$ respectively. The most straightforward characterization of the $(-\beta)$-shift is the following.
\begin{lemma}\label{lem:4.1}
Let $\T$ be given and let $\boldsymbol{x}\in{\cal A}^\NN$. Then $\boldsymbol{x}\in\Sn$ if and only if $(\boldsymbol{x}_p,\ldots,\boldsymbol{x}_q)$ is $\T$-admissible for all $1\leq p\leq q$.
\end{lemma}
We use this lemma to prove the following much more useful characterization.
\begin{theorem}\label{thm:4.2}
Let $\T$ be given and let $\boldsymbol{x}\in{\cal A}^\NN$. The following hold:
\begin{enumerate}
\item[(a)] We have $\boldsymbol{x}\in\Sl$ if and only if $\drs(\ell_{x_n})\preceq(x_n,x_{n+1},\ldots)\preceq\dl(r_{x_n})$ for all $n\geq 1$.
\item[(b)] We have $\boldsymbol{x}\in\Sr$ if and only if $\dr(\ell_{x_n})\preceq(x_n,x_{n+1},\ldots)\preceq\dls(r_{x_n})$ for all $n\geq 1$.
\end{enumerate}
\end{theorem}
\begin{proof}
We only prove (a), as the proof of (b) is similar. 
The "if" part follows from Lemma \ref{lem:3.10} and Lemma \ref{lem:4.1}. Let $N\geq 1$ be arbitrary and fixed. If $(x_N,x_{N+1},\ldots)$ is $\Tl$-admissible, Theorem \ref{thm:3.9} applies. Thus, assume it is not $\Tl$-admissible. By Lemma \ref{lem:4.1}, every finite subblock $(x_N,\ldots,x_{N+k})$, where $k\geq 1$, is $\Tl$-admissible. Hence, we have
\bea
(x_N,\ldots,x_{N+k})\preceq\left(\dl(r_{x_N},1),\ldots,\dl(r_{x_N},k+1)\right)
\eea
which follows immediately and, by Lemma \ref{lem:3.5}, we also have
\bea
\left(\drs(\ell_{x_N},1),\ldots,\drs(\ell_{x_N},k+1)\right)\preceq (x_N,\ldots,x_{N+k}).
\eea
This proves the theorem.
\end{proof}
Based on this theorem, we can classify the shift space $\Sn$. The behaviour of these shift spaces depend on the sequences $\drs(\ell_a)$ and $\dl(r_a)$ (where $a\in{\cal A}$) if the underlying map is left-continuous and $\dr(\ell_a)$ and $\dls(r_a)$ if the underlying map is right-continuous. The sequences will be called \emph{boundary sequences}.

The next theorem states that eventually periodic boundary sequences are a necessary and sufficient condition for the shift space to be sofic. In order to prove this, we will give an algorithm, based on the algorithm in \cite{IS09}, that construct a labeled graph recognizing the shift. For now, we will assume that all boundary sequences are eventually periodic.

Assume that our shift space has a left-continuous underlying map. The shift space has at most $2(\lfloor\beta\rfloor+1)$ boundary sequences, two for each 
$a\in{\cal A}$ used by the underlying digit function: one corresponding to $\ell_a$ and the other to $r_a$. In what follows we will assume that all digits in 
$\cal A $ are used. Hence, we will need two sets for each digit, $m^\ell_a$ and $m^r_a$, which are subsets of $\ZZ_{\geq 0}$. These sets keep track of the (finite) memory of a machine that reads the sequence $(x_1,x_2,\ldots)$ one digit at a time. The meaning of $k\in m^\ell_a$ is that the current memory contains a finite subblock starting with $a$ that equals the prefix of the boundary sequence corresponding to $\ell_a$ and where the next digit needs to be matched against the $(k+1)$-th digit of the boundary sequence corresponding to $\ell_a$ (similarly for $m^r_a$). In fact, we can give an upper bound for each of these memory sets by using the fact that all boundary sequences are eventually periodic. Let the boundary sequence be eventually periodic with pre-periodic part of length $q\geq 0$ and periodic part of length $p\geq 1$, then the upper bounds, denoted by $U^\ell_a$ and $U^r_a$ respectively, are equal to
\bea
\begin{cases}
2p, & \text{if $q=0$};\\
2p+q-1, & \text{if $q\neq 0$ and $p$ is odd};\\
p+q-1, & \text{if $q\neq 0$ and $p$ is even}.
\end{cases}
\eea
These upper bounds tell us how many different prefixes we may expect.

Next, assume that we read a new digit of the sequence $(x_1,x_2,\ldots)$, say $d$. Our memory has now changed and hence we need to update our memory sets. If $k\in m^\ell_a$ and we read the digit $d$, we change the index $k$ into another index $m^\ell_a(k/d)$, which is defined as:
\ba\label{eq:2}
m^\ell_a(k/d) & := & \begin{cases}
k+1, & \text{if $k<U^\ell_a$ and $d=\drs(\ell_a,k+1)$};\\
1, & \text{if $k=U^\ell_a$, $d=\drs(\ell_a,k+1)$ and $q=0$};\\
q, & \text{if $k=U^\ell_a$, $d=\drs(\ell_a,k+1)$ and $q\neq 0$};\\
0, & \text{if $k\neq 0$ and $(-1)^{k+1}\left(\drs(\ell_a,k+1)-d\right)<0$};\\
0, & \text{if $k=0$ and $d\neq a$};\\
1, & \text{if $k=0$ and $d=a$};\\
F, & \text{otherwise}.
\end{cases}
\ea
Let us shortly explain what each of these seven cases mean. If our memory contains a subblock matching the prefix of the boundary sequence of $\ell_a$ but does not contain one complete period, then we check digit $d$ against the next digit of the prefix (case 1). If the boundary sequence is purely periodic and if our memory contains two complete periods (we need two complete periods in the case $p$ is odd), then move back to the beginning (case 2). If the boundary sequence is eventually periodic and our memory contains the maximum number of complete periods (one if $p$ is even, otherwise two), then return to the beginning of the periodic part (case 3). If our memory contains a subblock that, together with the digit $d$, can be accepted bacause of Theorem \ref{thm:4.2}, then accept it and "forget" about this block (case 4). If our memory does not contain the digit $a$ and if the new digit also is not $a$, do absolutely nothing (case 5). On the other hand, if the new digit equals $a$, we have a subblock of length 1 matching the prefix of equal length of the boundary sequence $\ell_a$ (case 6). If none of the above happens, then we are neither undecided (cases 1,2,3,5 and 6) nor can we accept any subblock (case 4), and hence we must reject it (case 7).

Similarly, we define
\ba\label{eq:3}
m^r_a(k/d) & := & \begin{cases}
k+1, & \textrm{if $k<U^r_a$ and $d=\dl(r_a,k+1)$};\\
1, & \textrm{if $k=U^r_a$, $d=\dl(r_a,k+1)$ and $q=0$};\\
q, & \textrm{if $k=U^r_a$, $d=\dl(r_a,k+1)$ and $q\neq 0$};\\
0, & \textrm{if $k\neq 0$ and $(-1)^{k+1}\left(d-\dl(r_a,k+1)\right)<0$};\\
0, & \textrm{if $k=0$ and $d\neq a$};\\
1, & \textrm{if $k=0$ and $d=a$};\\
F, & \textrm{otherwise}.
\end{cases}
\ea
We state the following result, which follows directly from equations \eqref{eq:2} and \eqref{eq:3}:
\begin{corollary}\label{cor:4.3}
Let $(z_1,\ldots,z_n)$ be our current memory containing no forbidden blocks. Then for some $a\in{\cal A}$ and $i\leq U^\ell_a$ (or $U^r_a$) either $m^\ell_a(i/d)$ or $m^r_a(i/d)$ equals $F$ if and only if $(z_1,\ldots,z_n,d)$ contains a forbidden block.
\end{corollary}
To construct a labeled graph recognizing the shift $\Sl$ whose boundary sequences are all eventually periodic, we perform the following steps:
\begin{enumerate}
\item[1.] Let ${\cal V}$ be the set of vertices where each vertex $v\in{\cal V}$ is labeled\\ $(m_0^\ell,m_0^r,\ldots,m_{\lfloor\beta\rfloor}^\ell,m_{\lfloor\beta\rfloor}^r)$ such that $m^\ell_a$ is a nonempty subset of\\ $\{0,1,\ldots,U^\ell_a\}$ and $m^r_a$ is a nonempty subset of $\{0,1,\ldots,U^r_a\}$.
\item[2.] For each vertex $v\in{\cal V}$ and $d\in{\cal A}$ draw an edge with label $d$ from vertex $v$ to vertex $w=(w_1,w_2,\ldots,w_{2\lfloor\beta\rfloor+2})$, where
\bea
w_k &=& \begin{cases}
\varphi_{\ell,(k-1)/2}(m^\ell_{(k-1)/2},d), & \text{if $k$ is odd};\\
\varphi_{\ell,(k-2)/2}(m^r_{(k-2)/2},d), & \text{if $k$ is even};
\end{cases}
\eea
and the maps $\varphi_{\ell,a}$ and $\varphi_{r,a}$ are defined as
\ba\label{eq:4}
\varphi_{\ell,a}(v,d) & := & \begin{cases}
F, & \text{if $F\in\bigcup_{i\in v} \left\{m^\ell_a(i/d)\right\}$};\\
\bigcup_{i\in v} \left\{m^\ell_a(i/d)\right\}\setminus\{0\}, & \text{if $\{0\}\subsetneq\bigcup_{i\in v} \left\{m^\ell_a(i/d)\right\}$}\\ & \text{and $F\notin\bigcup_{i\in v} \left\{m^\ell_a(i/d)\right\}$};\\
\{1\}\cup \bigcup_{i\in v} \left\{m^\ell_a(i/d)\right\}\setminus\{0\}, & \text{if $1,F\notin \bigcup_{i\in v} \left\{m^\ell_a(i/d)\right\}$}\\
 & \text{and $d=a$};\\
\bigcup_{i\in v} \left\{m^\ell_a(i/d)\right\}, & \textrm{otherwise}.
\end{cases}
\ea
The definition of $\varphi_{r,a}$ is nearly identical; simply replaces all instances of $\ell$ in \eqref{eq:4} with $r$.
\item[3.] The connected component (i.e., each vertex has at least one outgoing edge) containing the zero vertex is the labeled graph recognizing $\Sl$.
\end{enumerate}
Since our memory sets may contain more than one digit, we need to keep track of the way each of these indices react to the new digit $d$ and, should they arise, remove any inconsistencies. This is the job of $\varphi_{\ell,a}$ and $\varphi_{r,a}$. Let us explain the four cases in \eqref{eq:4} in more detail. If, because of the new digit $d$, our memory contains a forbidden subblock, automatically reject it (case 1). If we cannot reject it, then suppose our memory contains at least two subblocks on which we are undecided, but can accept some (not all) of them after we read the new digit $d$. In that case adding a $0$ to the memory set would be redundant (case 2). If the new digit equals $a$, then add $1$ to the memory set, as we have a new subblock (of length $1$) starting with $a$ (case 3). If none of these three cases apply, there are no inconsistencies (case 4).

In practice, one starts with the zero vertex and adds vertices along the way. Since none of the vertices carry the label $F$, we do not draw an edge if the update rule in \eqref{eq:4} implies that the edge should point towards such a vertex.
\begin{theorem}\label{thm:4.4}
The shift space $\Sn$ is sofic if and only if its boundary sequences are all eventually periodic.
\end{theorem}
\begin{proof}
Assume, without loss of generality, that the underlying map is left-continuous (in the remainder of the proof we will write $\Sl$). Let ${\cal G}$ be a right-resolving labeled graph recognizing $\Sl$ (recall \cite[Theorem 3.3.2]{LM95}) and let ${\cal L}$ be the labeling. Fix $a\in{\cal A}$ and consider $\drs(\ell_a)$ (the argument is similar for $\dl(r_a)$). There exists a path $\xi=e_1e_2\cdots$ in ${\cal G}$ such that $\left({\cal L}(e_1),{\cal L}(e_2),\ldots\right)=\drs(\ell_a)$. By Theorem \ref{thm:4.2}, $\drs(\ell_a)$ is the smallest sequence with respect to the order $\prec$ starting with $a$ and hence $\xi$ is the path that first chooses the edge with label $a$ and then the edge with the smallest possible label (with respect to $\prec$). Since ${\cal G}$ is finite, the path $\xi$ passes some vertex $v$ infinitely often. Hence, $\xi$ contains a loop of even length, which implies that for some $k,n\geq 1$ we have ${\cal L}(e_i)={\cal L}(e_{i+2k})$. It follows that $\drs(\ell_a)$ is eventualy periodic.

Conversely, let $\Sl$ be given, $\cal G$
the labeled graph that follows from our construction and let $L_S$ and 
$L_{\cal G}$ be the language of the shift space $\Sl$ and the edge shift on 
$\cal G $ respectively. By Corollary~\ref{cor:4.3} and the construction of 
$\cal G$ it immediately follows that $L_S\subset L_{\cal G}$. If $(a_1,\ldots,a_n,d)\notin L_S$ and $(a_1,\ldots,a_n)\in L_S$ (we may assume this without loss of generality), then from Corollary~\ref{cor:4.3} it follows that either $m^\ell_a(i/d)$ or $m^r_a(i/d)$ equals $F$ for some $i$ and $a$. Hence, by construction, there is a finite path $\zeta=(e_1,\ldots,e_n)$ such that ${\cal L}(e_i)=a_i$. Say the path $\zeta$ ends at vertex $v$, then there is no outgoing edge from $v$ with label $d$. For if it did exist, it would point to a vertex with label $F$ as one of its coordinates by \eqref{eq:4}. Such vertices, however, do not exist (recall step 1 of the construction). It follows that $L_S=L_{\cal G}$.
\end{proof}

\begin{remark}
The construction of the labeled graph is also valid if at least one boundary sequence is not eventually periodic. In this case, the upper bound $U^\ell_a$ or $U^r_a$ corresponding to this boundary sequence, as well as $p$ for this specific boundary sequence, should be equal to $\infty$ (as there is no periodicity to exploit). Using our construction, the number of vertices in the labeled graphs of these shifts might be countably infinite.
\end{remark}

Let us illustrate the results of this section with two examples.
\begin{example}\label{ex:4.5}
We continue the case of Example \ref{ex:2.3}. In Examples \ref{ex:3.2} and \ref{ex:3.8} we determined the boundary sequences and hence, by Theorem 4.2, a sequence belongs to the shift space $\Sn$ if and only if
\bea
(\overline{1,0})\preceq(x_n,x_{n+1},\ldots)\preceq(1,1,\overline{0}) & \vee & (0,0,1,\overline{0})\preceq(x_n,x_{n+1},\ldots)\preceq(\overline{0,1})
\eea
holds for all $n\geq 1$. We can simplify this as
\ba\label{eq:5}
(x_n,x_{n+1},\ldots)\preceq(1,1,\overline{0}) & \vee & (0,0,1,\overline{0})\preceq(x_n,x_{n+1},\ldots),
\ea
since the other two inequalities are always satisfied, as $(\overline{1,0})$ and $(\overline{0,1})$ are the smallest and the greatest sequences with respect to the alternate order respectively. It is useful to create tables stating all possible outcomes of $m^\ell_a(i/d)$ and $m^r_a(i/d)$ for all $a,d\in{\cal A}$ and all allowed indices $i$. In this specific case, we find:
\bea
\begin{tabular}{|c|c|c|}
$m_0^\ell(i/d)$ & 0 & 1\\
\hline
0 & 1 & 0\\
1 & 2 & 0\\
2 & 0 & 3\\
3 & 4 & 0\\
4 & 3 & $F$
\end{tabular}
& &
\begin{tabular}{|c|c|c|}
$m_1^r(i/d)$ & 0 & 1\\
\hline
0 & 0 & 1\\
1 & 0 & 2\\
2 & 3 & 0\\
3 & 2 & $F$
\end{tabular}
\eea
The entries labeled $F$ correspond to forbidden blocks, though not all forbidden blocks can be found explicitly this way. We see that $m^\ell_0(4/1)=F$, which means we can find a forbidden block by taking the prefix of length $4$ of $\drs(2-\sqrt{5})$ and adding a fifth digit to it, in this case $1$. So, $(0,0,1,0,1)$ is a forbidden block, which is clear from \eqref{eq:5}. Similarly, $m_1^r(3/1)=F$ tells us that $(1,1,0,1)$ is a forbidden block. Figure \ref{fig:3} shows the labeled graph recognizing the shift space.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.2cm,semithick]
\node[state] (00) {$\vectwo{0}{0}$};
\node[state] (10) [right of=00] {$\vectwo{1}{0}$};
\node[state] (01) [below of=00] {$\vectwo{0}{1}$};
\node[state] (120) [right of=10] {$\vectwo{1,2}{0}$};
\node[state] (31) [below of=120] {$\vectwo{3}{1}$};
\node[state] (140) [right of=31] {$\vectwo{1,4}{0}$};
\node[state] (1230) [above of=140] {$\vectwo{1,2,3}{0}$};
\node[state] (1240) [right of=1230] {$\vectwo{1,2,4}{0}$};
\node[state] (012) [below of=01] {$\vectwo{0}{1,2}$};
\node[state] (13) [right of=012] {$\vectwo{1}{3}$};
\node[state] (122) [right of=13] {$\vectwo{1,2}{2}$};
\node[state] (123) [right of=122] {$\vectwo{1,2}{3}$};

\path (00) edge node {0} (10)
           edge node [left] {1} (01)
      (10) edge node {0} (120)
           edge [bend left] node {1} (01)
      (01) edge [bend left] node {0} (10)
           edge node {1} (012)
      (120) edge [loop above] node {0} (120)
            edge node {1} (31)
      (31) edge node [below] {0} (140)
           edge node {1} (012)
      (140) edge node {0} (1230)
      (1230) edge [bend left] node {0} (1240)
             edge node {1} (31)
      (1240) edge [bend left] node {0} (1230)
      (012) edge node [below] {0} (13)
            edge [loop left] node {1} (012)
      (13) edge node [below] {0} (122)
      (122) edge [bend left] node {0} (123)
            edge node {1} (31)
      (123) edge [bend left] node {0} (122);
\end{tikzpicture}
\caption{A labeled graph recognizing the shift space given by \eqref{eq:5}.\label{fig:3}}
\end{figure}
\end{example}
\begin{example}\label{ex:4.6}
Now consider the map given in Example \ref{ex:3.4}. By Example \ref{ex:3.7}, $\drs(0)=(0,1,\overline{1,0})$, and thus a sequence belongs to the shift space generated by this map if and only if
\ba\label{eq:6}
(x_n,x_{n+1},\ldots)\preceq(1,\overline{1,0}) & \vee & (0,1,\overline{1,0})\preceq(x_n,x_{n+1},\ldots)
\ea
holds for all $n\geq 1$. Once again, we omitted two inequalities since they are redundant. We can proceed as in the previous example and create the following tables:
\bea
\begin{tabular}{|c|c|c|}
$m_0^\ell(i/d)$ & 0 & 1\\
\hline
0 & 1 & 0\\
1 & $F$ & 2\\
2 & 0 & 3\\
3 & 2 & 0\\
\end{tabular}
& &
\begin{tabular}{|c|c|c|}
$m_1^r(i/d)$ & 0 & 1\\
\hline
0 & 0 & 1\\
1 & 0 & 2\\
2 & 1 & 0\\
\end{tabular}
\eea
The tables now only reveal one forbidden block: $(0,0)$. As we will see in a later section, this is the only forbidden block. For the moment, assume we are not aware of this. We construct a labeled graph that recognizes the shift based on our lengthy exposition earlier. This graph is shown in Figure \ref{fig:4}.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.2cm,semithick]
\node[state] (00) {$\vectwo{0}{0}$};
\node[state] (10) [right of=00] {$\vectwo{1}{0}$};
\node[state] (01) [below of=00] {$\vectwo{0}{1}$};
\node[state] (012) [below of=01] {$\vectwo{0}{1,2}$};
\node[state] (11) [below of=10] {$\vectwo{1}{1}$};
\node[state] (21) [right of=11] {$\vectwo{2}{1}$};
\node[state] (212) [below of=21] {$\vectwo{2}{1,2}$};
\node[state] (312) [right of=212] {$\vectwo{3}{1,2}$};
\node[state] (121) [above of=312] {$\vectwo{1,2}{1}$};
\node[state] (2312) [above of=121] {$\vectwo{2,3}{1,2}$};

\path (00) edge node {0} (10)
           edge node [left] {1} (01)
      (10) edge [bend left] node {1} (21)
      (01) edge node {0} (10)
           edge node {1} (012)
      (012) edge node {0} (11)
            edge [loop left] node {1} (012)
      (11) edge [bend left] node {1} (212)
      (21) edge [bend left] node {0} (10)
           edge node {1} (312)
      (212) edge [bend left] node {0} (11)
            edge node {1} (312)
      (312) edge node {0} (121)
            edge [bend left] node {1} (012)
      (121) edge node [right] {1} (2312)
      (2312) edge [bend right] node [left] {0} (121)
             edge [bend left] node {1} (312);
\end{tikzpicture}
\caption{A labeled graph recognizing the shift space given by \eqref{eq:6}.\label{fig:4}}
\end{figure}
\end{example}
As in the case of expansions in positive base, whenever $\beta$ is Pisot we can improve Theorem \ref{thm:4.4} a little. Recall that a \emph{Pisot number} is a positive algebraic integer whose other conjugates lie in the unit circle in the complex plane. The following theorem shows why Pisot bases are nice to work with.
\begin{theorem}
Let $\beta$ be Pisot, $x\in I_{-\beta}$ and $\T$ be given and let $\dn(x)$ be the $(-\beta)$-expansion of $x$ generated by $\T$. If $x\in\QQ(\beta)$, then $\dn(x)$ is eventually periodic.
\end{theorem}
\begin{proof}
We will not give the complete proof here, as it is nearly identical to the proof of \cite[Theorem 24]{DMP11}. In our case, replace $[l,r)$ with $I_{-\beta}$ and note that we have the bound $|r_n|<\frac{\beta\cdot\lfloor\beta\rfloor}{\beta^2-1}$.
\end{proof}
As an immediate corollary, we have:
\begin{theorem}\label{thm:4.8}
Let $\beta$ be Pisot and $\Sn$ be given. Then $\Sn$ is sofic if and only if the cut points of the underlying map $\T$ all lie in $\QQ(\beta)$.
\end{theorem}

\section{Forbidden blocks}
Example \ref{ex:4.6} showed that, while technically correct, our construction of the labeled graph can yield us quite large graphs. However, by carefully looking at Examples \ref{ex:4.5} and \ref{ex:4.6} we see why the first one is only sofic and the latter is actually a shift of finite type. In the first example, the forbidden blocks contain both a part of the pre-periodic and a part of the periodic part of the boundary sequence, where in the second example the forbidden block only contained part of the pre-periodic part. This observation quickly leads us to a conjecture: a shift space of the form given in Theorem \ref{thm:4.2} is a shift of finite type if and only if its forbidden blocks only contain part of either pre-periodic or periodic parts of boundary sequences, but not both. Indeed, if the latter does happen, we can abuse the periodicity of the boundary sequences to generate infinitely many forbidden blocks that cannot be covered by a finite set (because of the pre-periodic part). Based on these observations, we state the following
\begin{theorem}\label{thm:5.1}
Let $\Sn$ be a sofic shift. Then $\Sn$ is a shift of finite type if and only if the periodic part of every eventually periodic boundary sequence is a purely periodic boundary sequence.
\end{theorem}
\begin{proof}
Once again, we assume that the underlying map is left-continuous and write $\Sl$ instead of $\Sn$. Let $\Sl$ be a shift of finite type. Every shift of finite type is sofic and hence by Theorem \ref{thm:4.4} we conclude that all boundary sequences are eventually periodic. Assume that there exists a left-boundary sequence (the proof is similar for right-boundary sequences) $(a_1,\ldots,a_k,\overline{a_{k+1},\ldots,a_{k+p}})$, where $k,p\geq 1$, whose periodic part does not equal some other boundary sequence. Moreover, assume that $k$ is odd (the proof is similar for $k$ even). By assumption, there exists a smallest integer $1\leq j\leq p$ such that there exists some $b\in{\cal A}$ for which we have $(-1)^{k+j}(b-a_{k+j})<0$. It follows that the block $(a_1,\ldots,a_{k+j-1},b)$ is forbidden. Moreover, the blocks $w^{(n)}:= a_1\cdots a_k(a_{k+1}\cdots a_{k+p})^{2n} a_{k+1}\cdots a_{k+j-1}b$ are forbidden for all $n\geq 0$.

Suppose that there exists some $1\leq i\leq j-1$ such that the subblock $a_{k+i}\cdots b$ of length at most $j$ is forbidden. Then the blocks $(a_{k+1}\cdots a_{k+p})^{2n}a_{k+1}\cdots a_{k+j-1}b$ are forbidden for all $n\geq 0$ and thus we conclude that
\bea
(\overline{a_{k+1}\cdots a_{k+p}})\prec (a_{k+1}\cdots a_{k+p})^{2n} a_{k+1}\cdots a_{k+j-1}b
\eea
holds for all $n\geq 1$. This, however, implies that $(\overline{a_{k+1},\ldots,a_{k+p}})$ is a right-boundary sequence, which contradicts our initial assumption. Hence, there exists some integer $1\leq m\leq k$ such that the blocks $a_m\cdots a_k(a_{k+1}\cdots a_{k+p})^{2n}a_{k+1}\cdots a_{k+j-1}b$ are forbidden for all $n\geq 0$, but any of their subblocks are admissible. Hence, $\Sn$ is not a shift of finite type.

Next, assume that all boundary sequences satisfy the property given in Theorem \ref{thm:5.1} and let $(a_1,a_2,\ldots)$ be an arbitrary but fixed left-boundary sequence (the proof is similar for right-boundary sequences). If it is purely periodic with period $p$, then the forbidden blocks are given by
\ba\label{eq:7}
\left\{ (x_1,\ldots,x_{2p})\in{\cal A}^{2p}:\ (x_1,\ldots,x_{2p})\prec (a_1,\ldots,a_{2p})\,\wedge\,x_1=a_1\right\}.
\ea
If it is eventually periodic with pre-periodic part of length $q$ and period $p$, then the set
\ba\label{eq:8}
\left\{ (x_1,\ldots,x_{q+1})\in{\cal A}^{q+1}:\ (x_1,\ldots,x_{q+1})\prec(a_1,\ldots,a_{q+1})\,\wedge\,x_1=a_1\right\}
\ea
is sufficient. To see why, let $(y_1,y_2,\ldots)$ be a sequence such that $y_1=a_1$ and $(y_1,y_2,\ldots)\prec(a_1,a_2,\ldots)$. Let $m$ be the smallest integer such that $y_i=a_i$ for $i<m$ and $(-1)^m(y_m-a_m)<0$ and assume that $m>q+1$. Moreover, assume that $q$ is odd (the argument is similar for $q$ even). Then $y_1\cdots y_{q+1}=a_1\cdots a_{q+1}$ and
\bea
(\overline{a_{q+1},\ldots,a_{q+p}})\prec(y_{k+1},y_{k+2},\ldots).
\eea
Since the purely periodic sequence on the left-hand side is another boundary sequence, it follows that the forbidden blocks of $(y_1,y_2,\ldots)$ are contained within the subsequence $(y_{q+1},y_{q+2},\ldots)$. But these forbidden blocks are already covered by a set of the form \eqref{eq:7}. Hence, it is sufficient to consider forbidden blocks of the form in \eqref{eq:8}. Since there are finitely many boundary sequences and since each of these boundary sequences only have a finite number of forbidden blocks, the shift space is a shift of finite type.
\end{proof}
We can use the result of this theorem to reduce our graphs quite a bit as follows. Consider any boundary sequence. If its periodic part is a boundary sequence of the same shift space, then remove this periodic part. If our memory contains the whole pre-periodic part of this boundary sequence, then accept it and forget about it (i.e., the new memory index in this specific case would be a zero). The following two examples illustrate this.
\begin{example}
Reconsider Example \ref{ex:4.6}. Since $(\overline{1,0})$ is a boundary sequence (the smallest with respect to $\prec$), we can forget about this periodic part. Moreover, this turns $(1,\overline{1,0})$ into the single digit boundary block $(1)$, which itself is redundant, and hence we are left with the following condition:
\bea
(0,1)\preceq(x_n,x_{n+1})
\eea
for all $n\geq 1$ such that $x_n=0$. Although not necessary at this point, we still fill in the table:
\bea
\begin{tabular}{|c|c|c|}
$m_0^\ell(i/d)$ & 0 & 1\\
\hline
0 & 1 & 0\\
1 & $F$ & 0\\
\end{tabular}
\eea
The resulting graph is shown in Figure \ref{fig:5}.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.2cm,semithick]
\node[state] (0) {$0$};
\node[state] (1) [right of=0] {$1$};

\path (0) edge [loop left] node {1} (0)
          edge [bend left] node {0} (1)
      (1) edge [bend left] node {1} (0);
\end{tikzpicture}
\caption{Another labeled graph recognizing the shift space of Example \ref{ex:4.6}.\label{fig:5}}
\end{figure}
\end{example}
The same approach can be applied to any shift space of the form in Theorem \ref{thm:4.2} as long as at least one eventually periodic boundary sequence has a periodic part equal to a periodic boundary sequence.
\begin{example}\label{ex:5.3}
Let $\beta=2$ and consider the left-continuous map with cut points $-\frac{5}{6}$ and $-\frac{1}{6}$. Theorem \ref{thm:4.2} tells us that $(x_1,x_2,\ldots)\in\Sn$ if and only if for all $n\geq 1$ we have:
\bea
\begin{array}{rrllll}
 & (\overline{2,0}) & \preceq & (x_n,x_{n+1},\ldots) & \preceq & (2,\overline{1}),\\
 & (1,\overline{0,2}) & \preceq & (x_n,x_{n+1},\ldots) & \preceq & (1,\overline{1,0}),\\
\textrm{or} & (0,\overline{0,1}) & \preceq & (x_n,x_{n+1},\ldots) & \preceq & (\overline{0,2}).
\end{array}
\eea
Careful inspection reveals that the boundary sequences ($\overline{2,0})$ and $(\overline{0,2})$ are redundant (the smallest and largest possible sequence with respect to $\prec$). Moreover, we may reduce $(1,\overline{0,2})$ to the single digit block $(1)$, which is once again redundant. We are left with:
\ba\label{eq:9}
\begin{cases}
(x_n,x_{n+1},\ldots) \preceq (2,\overline{1}), & \text{whenever $x_n=2$};\\
(x_n,x_{n+1},\ldots) \preceq (1,\overline{1,0}), & \text{whenever $x_n=1$};\\
(0,\overline{0,1}) \preceq (x_n,x_{n+1},\ldots), & \text{whenever $x_n=0$}.
\end{cases}
\ea
We create tables one more time:
\bea
\begin{tabular}{c|c|c|c}
$m_0^\ell(i/d)$ & 0 & 1 & 2\\
\hline
0 & 1 & 0 & 0\\
1 & 2 & 0 & 0\\
2 & 0 & 1 & $F$
\end{tabular}
&
\begin{tabular}{c|c|c|c}
$m_1^r(i/d)$ & 0 & 1 & 2\\
\hline
0 & 0 & 1 & 0\\
1 & 0 & 2 & $F$\\
2 & 1 & 0 & 0
\end{tabular}
&
\begin{tabular}{c|c|c|c}
$m_2^r(i/d)$ & 0 & 1 & 2\\
\hline
0 & 0 & 0 & 1\\
1 & 0 & 2 & $F$\\
2 & $F$ & 1 & 0
\end{tabular}
\eea
and use these to produce the labeled graph in Figure \ref{fig:6}.
\begin{figure}[b]
\centering
\begin{tikzpicture}[->,>=stealth',auto,node distance=3.5cm,semithick,scale=0.5]
  \node[state]         (000) {$\vecthree{0}{0}{0}$};
  \node[state]         (010) [right of=000] {$\vecthree{0}{1}{0}$};
  \node[state]         (100) [below of=010] {$\vecthree{1}{0}{0}$};
  \node[state]         (001) [below of=000] {$\vecthree{0}{0}{1}$};
  \node[state]         (012) [below of=001] {$\vecthree{0}{1}{2}$};
  \node[state]         (0122) [right of=012] {$\vecthree{0}{1,2}{2}$};
  \node[state]         (0121) [right of=0122] {$\vecthree{0}{1,2}{1}$};
  \node[state]         (0120) [right of=010] {$\vecthree{0}{1,2}{0}$};
  \node[state]         (1200) [right of=100] {$\vecthree{1,2}{0}{0}$};
  \node[state]         (110) [right of=1200] {$\vecthree{1}{1}{0}$};

  \path (000) edge node {0} (100)
              edge node {1} (010)
              edge node {2} (001)
        (010) edge node {1} (0120)
              edge node [left] {0} (100)
        (001) edge node {0} (100)
              edge node {1} (012)
        (100) edge [bend right] node [right] {1} (010)
              edge [bend left] node {2} (001)
              edge node {0} (1200)
        (012) edge [bend left=60] node [below] {1} (0121)
        (0121) edge [bend right] node {0} (110)
               edge [bend left] node {1} (0122)
        (0122) edge [bend left] node {1} (0121)
        (1200) edge [loop above] node {0} (1200)
               edge node {1} (110)
        (0120) edge [loop above] node {1} (0120)
               edge node [below left] {0} (110)
        (110) edge [bend right] node [above right] {1} (0120)
              edge [bend left] node {0} (1200);
\end{tikzpicture}
\caption{A labeled graph recognizing the shift from Example \ref{ex:5.3}.\label{fig:6}}
\end{figure}
\end{example}

\section{Discussion}
Our goal was to consider a large class of $(-\beta)$-transformations and to prove statements analogous to what Ito and Sadahiro for their $(-\beta)$-transformation. Our class of $(-\beta)$-transformations include transformations that, when restricted to the interval $\left[-\frac{\beta}{\beta+1},\frac{1}{\beta+1}\right)$, are the Ito-Sadahiro transformation. As to be expected, our results agree with results on their transformation (compare Theorem \ref{thm:3.9} and \ref{thm:4.4} with \cite[Theorem 10 \& 12]{IS09} and Theorem \ref{thm:5.1} with \cite[Theorem 4]{FL09}). While we only considered the canonical alphabet, there are many other alphabets to be considered. In fact, there is a rather large class of alphabets satisfying property i of Assumption \ref{ass:2.1} (compare with \cite[Proposition 2.1]{Ped04}) of which we assume the results in this paper will carry over.

Of the many open problems surrounding $(-\beta)$-expansions we want to highlight two. The first problem is based on the examples in sections 4 and 5 illustrating the output of our algorithm. Can this algorithm be improved upon? The second problem follows from \cite{IS09}:  given two sequences $\boldsymbol{x},\boldsymbol{y}\in{\cal A}^\NN$ (or any other alphabet), is there a $(-\beta)$-transformation such that $\boldsymbol{x}$ and $\boldsymbol{y}$ are boundary sequences of this transformation?

\begin{thebibliography}{10}
\bibitem{DK11} K. Dajani and C. Kalle, Transformations generating negative $\beta$-expansions, \emph{Integers} \textbf{11B} (2011).

\bibitem{DK03} K. Dajani and C. Kraaikamp, From greedy to lazy expansions and their driving dynamics, \emph{Expo. Math.} \textbf{20} (2002), 315--327.

\bibitem{DK04} K. Dajani and C. Kraaikamp, Random $\beta$-expansions, \emph{Ergodic Theory Dynam. Systems} \textbf{23} (2003), 461--479.

\bibitem{DV05} K. Dajani and M. de Vries, Measures of maximal entropy for random $\beta$-expansions, \emph{J. Eur. Math. Soc. (JEMS)} \textbf{7} (2005), 51--68.

\bibitem{DMP11} D. Dombek, Z. Mas\'{a}kov\'{a}, and E. Pelantov\'{a}, Number representation using generalized $(-\beta)$-transformation, \emph{Theoret. Comput. Sci.} \textbf{412} (2011), 6653--6665.

\bibitem{EJ91} P. Erd\H{o}s and I. Jo\'{o}, On the expansion $1=\sum q^{-n_i}$, \emph{Period. Math. Hungar.} \textbf{23} (1991), 27--30.

\bibitem{FL09} C. Frougny and A. C. Lai, On negative bases, in
{\it Proc. DLT 09},
Lecture Notes in Comp. Sci., Vol.\ 5583,  Springer,
2009, pp.\ 252--263.

\bibitem{IS09} S. Ito and T. Sadahiro, Beta-expansions with negative bases, \emph{Integers} \textbf{9} (2009), 239--259.

\bibitem{LM95} D. Lind and B. Marcus, \emph{An Introduction to Symbolic Dynamics and Coding}, Cambridge University Press, 1995.

\bibitem{Par60} W. Parry, On the $\beta$-expansions of real numbers, \emph{Acta. Math. Acad. Sci. Hung.} \textbf{11} (1960), 401--416.

\bibitem{Ped04} M. Pedicini, Greedy expansions and sets with deleted digits, \emph{Theoret. Comput. Sci.} \textbf{332} (2005), 313--336.

\bibitem{Ren57} A. R\'{e}nyi, Representations for real numbers and their ergodic properties, \emph{Acta. Math. Acad. Sci. Hung.} \textbf{8} (1957), 477--493.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 37B10; Secondary 11A63.

\noindent \emph{Keywords: } 
$(-\beta)$-expansions, sofic shift, shift of finite type.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 10 2011;
revised version received  January 11 2012.
Published in {\it Journal of Integer Sequences}, January 14 2012.

\bigskip
\hrule
\bigskip

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


\end{document}