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:


1. $a \prec \sigma^{n}(b) \preccurlyeq b$ for every $n \geq 0$;
2. $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. 



Graph presentation of Lexicographic shifts
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.


1. $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}$.
2. $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}$.
3. $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}$.
4. $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.


1. 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)$.
2. 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$.


