Classify shifts of finite type

Definitions and mathematical statement

For a square matrix $A$ with nonnegative integer entries, form the finite directed multigraph having $A_{ij}$ directed edges from $i$ to $j$. Let $X_A$ consist of all bi-infinite edge sequences in which the terminal vertex of each edge is the initial vertex of the next. The shift $\sigma_A((e_j)_j)=(e_{j+1})_j$ acts on this compact product space. Such edge shifts represent all two-sided shifts of finite type up to topological conjugacy.

The classification problem asks for usable complete invariants of these systems. Its decision version asks for an algorithm which, on every finite input pair $A,B$, halts and correctly decides whether a homeomorphism $H:X_A\to X_B$ exists with $H\sigma_A=\sigma_BH$. No irreducibility, mixing, or equal-size assumption is imposed on the input matrices.

Equivalently, one must decide strong shift equivalence over $\mathbb Z_+$: whether $A$ can be connected to $B$ by finitely many replacements $RS\leftrightarrow SR$ with nonnegative integer rectangular matrices $R,S$. The sizes of intermediate matrices are unrestricted. A procedure which only enumerates successful chains does not meet the decision requirement, since it must also terminate when no conjugacy exists. Counts of periodic points and entropy provide necessary invariants but do not constitute the requested complete classification. Conjugacy here preserves one application of the shift, without passing to higher powers.

Short English statement

Find a complete, effective classification of finite-type shifts, including an algorithm that always decides whether two presentations are conjugate.

Sources

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