Adler's renewal question

Definitions and mathematical statement

A two-sided sofic shift $X\subset A^{\mathbb Z}$ is the set of label sequences of bi-infinite paths in a finite labelled directed graph. It is irreducible if any two words in its language can be joined by a finite intervening word. The alphabet is finite, the topology is the product topology, and the left shift is $(\sigma x)_i=x_{i+1}$.

For a finite set $\mathcal W$ of nonempty words over a finite alphabet $B$, the renewal shift $X(\mathcal W)$ consists of all bi-infinite concatenations of these words, with arbitrary placement of the origin. Precisely, $y\in X(\mathcal W)$ if there are integers $b_j\to\pm\infty$ as $j\to\pm\infty$, strictly increasing in $j$, such that $y_{[b_j,b_{j+1})}\in\mathcal W$ for every $j$.

The catalogue asks whether every irreducible sofic shift is conjugate to a renewal shift. That general assertion is false: Williams constructed a strictly sofic counterexample. Retain here Adler's remaining finite-type question, explicitly stated in the cited primary treatment:

Is every irreducible shift of finite type conjugate to some $X(\mathcal W)$? A shift is of finite type if a finite list of forbidden words defines it. The required conjugacy is a homeomorphism $H:X\to X(\mathcal W)$ with $H\sigma=\sigma H$. The alphabet and coordinates may change, but the generating word list must remain finite. Concatenation need not be unique. This retained subclass is a proper restriction of the historical sofic question, whose negative answer is not being presented as an unresolved target.

Short English statement

Can every irreducible shift of finite type be recoded as concatenations of finitely many words? The broader sofic assertion has a counterexample.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 4600049 (AMR-045-0049), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Boyle - Open Problems in Symbolic Dynamics (2008), Problem/Question/Conjecture 29.1. Original source indexed by AMR-045-0049. https://www.math.umd.edu/~mboyle/papers/openfinalsub3nov2007.pdf.
• S3 R. Johansen, On Flow Equivalence of Sofic Shifts, Problem5.3 and Example5.4, pp.71–72; recalls Williams, Notes on renewal systems (1990). https://www.math.ku.dk/bibliotek/arkivet/phd-theses/phd11rj.pdf.
• S4 R. Johansen, Is Every Irreducible Shift of Finite Type Flow Equivalent to a Renewal System?, introduction: conjugacy question and negative sofic result. https://arxiv.org/abs/1304.0888.