Subshifts with Slowly Growing Numbers of Follower Sets

Abstract

For any subshift, define $F_X(n)$ to be the collection of distinct follower sets of words of length $n$ in $X$. Based on a similar result of the second and third authors, we conjecture that if there exists an $n$ for which $|F_X(n)|\le n$, then $X$ is sofic. In this paper, we prove several results related to this conjecture, including verifying it for $n\le 3$, proving that the conjecture is true for a large class of coded subshifts, and showing that if there exists $n$ for which $|F_X(n)|\le {\log }_2(n+1)$, then $X$ is sofic.

12 pages, no figures, AMS Contemporary Math Conference Proceedings