| Given a word w in the language of a one-dimensional shift space X, the follower set of w, denoted FX(w), is the set of all right-infinite sequences which follow w in some point of X. Extender sets are a generalization of follower sets (introduced in [5]) and are defined similarly. To a given shift space X, then, we may associate a follower set sequence {|FX( n)|} which records the number of distinct follower sets in X corresponding to words of length n. Similarly, we may define an extender set sequence {|EX(n)|}. The complexity sequence {phiX(n)} of a shift space X records the number of n-letter words in the language of X for each n. This thesis explores the relationship between the class of achievable follower and extender set sequences of one-dimensional shift spaces and the class of their complexity sequences.;Some surprising similarities suggest a connection may exist, for instance, both the complexity sequence and the extender set sequence are bounded if and only if there exists some n such that the value of the nth term of the sequence is at most n. This thesis, however, also demonstrates important differences among complexity sequences and follower and extender set sequences of one-dimensional shifts. In particular, we show that unlike complexity sequences, follower and extender set sequences need not be monotone increasing. Finally, we use the classical beta-shifts to demonstrate that, while many follower set sequences may not be realized as complexity sequences, up to possible increase by 1, any complexity sequence may be realized as a follower set sequence of some shift space.;[5] Steve Kass and Kathleen Madden. A sufficient condition for non-soficness of higher-dimensional subshifts. Proc. Amer. Math. Soc., 141(11):3803--3816, 2013. |
