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.
In @cite_23 Fijalkow defines the online space complexity of a language @math . His definition is equivalent to the space complexity of the language @math in the standard streaming model described above. Among other results, Fijalkow presents a probabilistic automaton @math such that the language accepted by @math (with threshold @math ) needs space @math in the streaming model. Streaming a language @math in the standard model is also related to the concept of automaticity @cite_34 . For a language @math , the automaticity @math of @math is the function @math , where @math is the minimal number of states of a DFA @math such that for all words @math of length at most @math : @math if and only if @math . Clearly, every regular language @math has constant automaticity. Karp @cite_1 proved that for every non-regular language @math , @math for infinitely many @math . This implies that for every non-regular language @math , membership checking in the standard streaming model is not possible in space @math .
@cite_34 @cite_1 @cite_23
2000920814 2293632979
Any sequential machine M represents a function f M from input sequences to output symbols. A function f is representable if some finite-state sequential machine represents it. The function f M is called an n-th order approximation to a given function f if f M is equal to f for all input sequences of length less than or equal to n . It is proved that, for an arbitrary nonrepresentable function f , there are infinitely many n such that any sequential machine representing an n th order approximation to f has more than n 2 + 1 states. An analogous result is obtained for two-way sequential machines and, using these and related results, lower bounds are obtained for two-way sequential machines and, using these and related results, lower bounds are obtained on the amount of work tape required online and offline Turing machines that compute nonrepresentable functions. In this paper, we define the online space complexity of languages, as the size of the smallest abstract machine processing words sequentially and able to determine at every point whether the word read so far belongs to the language or not. The first part of this paper motivates this model and provides examples and preliminary results.