Classify one-sided sofic shifts

Definitions and mathematical statement

Let $G$ be a finite directed graph whose edges carry symbols from a finite alphabet $A$. The labels of its right-infinite paths define a one-sided sofic shift $X_G\subset A^{\mathbb N_0}$, with $\sigma X_G\subset X_G$; the one-sided shift need not be onto. Different labelled graphs may define identical spaces or conjugate systems even when their numbers of vertices differ.

The problem is to classify these systems up to topological conjugacy. Thus one seeks complete invariants or a usable criterion, from finite labelled graph presentations $G,H$, for the existence of a homeomorphism $\Phi:X_G\to X_H$ with \[ \Phi\sigma_G=\sigma_H\Phi. \] In particular, decide whether there is an algorithm which terminates on every pair of input presentations and answers that existence question correctly.

A one-sided conjugacy and its inverse are finite-window codes using only present and future coordinates. Neither map may use negative coordinates from a chosen two-sided extension. Consequently, passing to the two-sided natural extension is not itself a complete answer to this classification problem. The class includes reducible sofic shifts as well as irreducible ones; no mixing assumption is imposed. The input graphs present label sequences, so a graph isomorphism condition would be unnecessarily restrictive. The requested invariants must recognize dynamical conjugacy across arbitrary finite presentations of the same one-sided system.

Short English statement

Classify one-sided sofic shifts under homeomorphisms that preserve the shift, preferably by a decision procedure from their labelled graphs.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 4600033 (AMR-045-0033), 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 21.1. Original source indexed by AMR-045-0033. https://www.math.umd.edu/~mboyle/papers/openfinalsub3nov2007.pdf.