Characterizing Follower and Extender Set Sequences

preprint2015arXivOpen access

Abstract

Given a one-dimensional shift XX, let ∣FX(ℓ)∣|F_X(\ell)| be the number of follower sets of words of length ℓ\ell in XX. We call the sequence {∣FX(ℓ)∣}ℓ∈N\{|F_X(\ell)|\}_{\ell \in \mathbb{N}} the follower set sequence of the shift XX. 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 lim sup⁡\limsup and lim inf⁡\liminf of these sequences may be achieved, so long as the lim inf⁡\liminf of the sequence is sufficiently large.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.