Characterizing follower and extender set sequences

ABSTRACT

Given a one-dimensional shift X, let |F_X(ℓ)| be the number of follower sets of words of length ℓ in X. We call the sequence the follower set sequence of the shift X. Extender sets are a generalization of follower sets, and we define the extender set sequence similarly. In this paper, we explore which sequences may be realized as follower set sequences and extender set sequences of one-dimensional sofic shifts. We show that any follower set sequence or extender set sequence of a sofic shift must be eventually periodic. We also show that, subject to a few constraints, a wide class of eventually periodic sequences are possible. In fact, any natural number difference in the and of these sequences may be achieved, so long as the of the sequence is sufficiently large.

KEYWORDS:

• Symbolic dynamics
• follower sets
• sofic

2010 Mathematics Subject Classification:

• Primary: 37B10

Acknowledgements

The author thanks his advisor, Dr Ronnie Pavlov, for many helpful conversations. The author would also like to thank the anonymous referee for useful comments and suggestions.

Disclosure statement

No potential conflict of interest was reported by the author.