Computational Complexity of $k$-Block Conjugacy

Tyler Schrock, Rafael Frongillo

We consider several computational problems related to conjugacy between subshifts of finite type, restricted to $k$-block codes: verifying a proposed $k$-block conjugacy, deciding…