  In a recent paper we analyzed the space complexity of streaming algorithms
whose goal is to decide membership of a sliding window to a fixed language. For
the class of regular languages we proved a space trichotomy theorem: for every
regular language the optimal space bound is either constant, logarithmic or
linear. In this paper we continue this line of research: We present natural
characterizations for the constant and logarithmic space classes and establish
tight relationships to the concept of language growth. We also analyze the
space complexity with respect to automata size and prove almost matching lower
and upper bounds. Finally, we consider the decision problem whether a language
given by a DFA/NFA admits a sliding window algorithm using logarithmic/constant
space.
