Graph presentation of Lexicographic shifts Consider a finite alphabet $\{0,1, \ldots, n-1\}$. Let  $\Sigma_n = \mathop{\prod}\limits_{j=1}^{\infty}\{0, \ldots n-1\}$ be the set of infinite one sided sequences and $\prec$ the lexicographic order defined in $\Sigma_n$. Given $a, b \in \Sigma_n$ with $a \prec b$ it is possible to define the lexicographic subshift corresponding to $a,b$ by $$\Sigma_{a,b} = \{x \in \Sigma^n : a \preccurlyeq \sigma^{n}(x) \preccurlyeq b \hbox{ for every } n \geq 0\}.$$ Also, we ask that $a$ and $b$ satisfy:


*

*$a \prec \sigma^{n}(b) \preccurlyeq b$ for every $n \geq 0$;

*$a \preccurlyeq \sigma^{n}(a) \prec b$ for every $n \geq 0$.


A particular case of this kind of subshifts is when $a = 0^{\infty}$, which is a $\beta$-shift. For these cases, it is known that a $\beta$-shift can be represented by a countable state directed graph, and there is a construction of such graph. (See for example: V. Climenhaga and D. J. Thompson. Intrinsic ergodicity beyond speciﬁcation: $\beta$-shifts, $S$-gap shifts, and their factors. Israel J. Math., 192:785–817, 2012).
Does there exist a similar construction for a lexicographic subshift? If so, can you provide me a reference for it? I tried to find a construction without success. 
 A: Just as the $\beta$-shift arises as the coding space for the transformation $x\mapsto \beta x$ (mod 1), so the shifts you describe arise as coding spaces for $x\mapsto \alpha + \beta x$ (mod 1).  The characteristic sequences $a,b$ correspond to the codings of 0 and 1, respectively.
In particular, you can describe the subshift in terms of a graph -- this was done for arbitrary piecewise monotonic interval maps by Hofbauer, and the key references are:
F. Hofbauer, "On intrinsic ergodicity of piecewise monotonic transformations with positive entropy", Israel J. Math. 34 (1979), no. 3, 213-237, MR 0570882, and part II (same title and journal), 38 (1981), no. 1-2, 107-115.
There are also a couple papers by Hofbauer and Keller from 1982 that deal with these classes of transformations.  Because the transformations they deal with are much more general than just $x\mapsto \alpha + \beta x$, it may take some work to extract the exact situation you want from what is shown there.  I'll give a summary at the bottom of my understanding of the construction (without proofs).
Another paper that may be relevant is
B. Faller and C.-E. Pfister, "A point is normal for almost all maps $\beta x + \alpha$ mod 1 or generalized $\beta$-transformations", ETDS 29 (2009), no. 5, 1529-1547, MR2545016.
I don't have the actual paper there in front of me at the moment, so I don't remember whether or not they go into details about the graph that codes the shift.
Here's a quick summary of the construction that can be extracted from Hofbauer's work.  Given a $\beta$-shift $\Sigma_\beta$, let $z$ be the $\beta$-expansion of $1$, so that the $\beta$-shift is all sequences for which every tail is lexicographically dominated by $z$.  You build the graph for $\Sigma_\beta$ by putting a vertex at each $0,1,2,3,\dots$, labeling the edge from $n$ to $n+1$ with the symbol $z_n$, and labeling edges from $n$ to $0$ with the symbols $0,1,\dots,z_n -1$ (if $z_n>0$).  
Now given an infinite sequence $x$, the way that you test whether $x\in \Sigma_\beta$ is to see whether $x$ codes a path starting at the origin.  Let $k(n)$ denote the vertex which this path has reached after following the labels $x_0,x_1,\dots, x_n$.  This can be interpreted as follows: $x_{n-k}\cdots x_n$ matches the first $k$ symbols of the characteristic sequence $z$, and so the remainder of $x$ needs to be tested starting at the vertex $k$, not the vertex $0$.
Now for $x\mapsto \alpha + \beta x$ mod 1, you can do the following.  Take the vertex set $\mathbb{N}^2$ (instead of $\mathbb{N}$).  As you follow a sequence $x$ to see whether it belongs to the shift space, we interpret "$x_1\cdots x_n$ ends at $(i,j)$" to mean that the last $i$ symbols of $x$ are the first $i$ symbols of $a$, and the last $j$ symbols of $x$ are the first $j$ symbols of $b$.  Then you need to compare $x_{n+1}$ to $a_{i+1}$ and $b_{j+1}$.  One of the following things happens.


*

*$x_{n+1} = a_{i+1} = b_{j+1}$.  Then you move to $(i+1,j+1)$, and the edge connecting the two vertices is labeled with this common value $a_{i+1} = b_{j+1}$.

*$x_{n+1} = a_{i+1} < b_{j+1}$.  Then the last $i+1$ symbols of $x_1\cdots x_{n+1}$ are the first $i+1$ symbols of $a$, but $x_1\cdots x_{n+1}$ doesn't end with any initial segment of $b$, so you move to $(i+1,0)$.  Thus you get an edge from $(i,j)\to(i+1,0)$ labeled with $a_{i+1}$.

*$x_{n+1} = b_{j+1} > a_{i+1}$.  As in the previous case, you get an edge $(i,j)\to (0,j+1)$ labeled with $b_{j+1}$.

*$a_{i+1} < x_{n+1} < b_{j+1}$.  Then $x_1\cdots x_{n+1}$ doesn't end with any initial segment of either $a$ or $b$, so you're back to $(0,0)$.  Thus you get an edge from $(i,j) \to (0,0)$ labeled with $x_{n+1}$.
Let's summarise all that.  The vertices of the graph are elements of $\mathbb{N}^2$, and the outgoing edges from $(i,j)$ follow one of two patterns.


*

*If $a_i = b_j$, then there is a single outgoing edge from $(i,j)$, labeled with the common value, going to $(i+1,j+1)$.

*If $a_i < b_j$, then there is an edge $(i,j)\to (i+1,0)$ labeled with $a_i$, an edge $(i,j)\to (0,j+1)$ labeled with $b_j$, and for each $a_i < c < b_j$ there is an edge $(i,j)\to (0,0)$ labeled with $c$.
Note that not all vertices may be accessible from the original vertex $(0,0)$, and so you actually are only concerned with a subset of $\mathbb{N}^2$.
Note also that there are two "distinguished rays" in the graph.  One of these corresponds to incrementing $i$ at every step, and is labeled with the sequence $a$.  The other corresponds to incrementing $j$ at every step, and is labeled with the sequence $b$.  This corresponds to the characteristic sequence $z$ that determines the $\beta$-shift and appears in the graph as a ray to $\infty$.
