Randomized sliding window algorithms for regular languages.

A sliding window algorithm receives a stream of symbols and has to output ateach time instant a certain value which only depends on the last $n$ symbols.If the algorithm is randomized, then at each time instant it produces anincorrect output with probability at most $\epsilon$, which is a constant errorbound. This work proposes a more relaxed definition of correctness which isparameterized by the error bound $\epsilon$ and the failure ratio $\phi$: Arandomized sliding window algorithm is required to err with probability at most$\epsilon$ at a portion of $1-\phi$ of all time instants of an input stream.This work continues the investigation of sliding window algorithms for regularlanguages. In previous works a trichotomy theorem was shown for deterministicalgorithms: the optimal space complexity is either constant, logarithmic orlinear in the window size. The main results of this paper concerns threenatural settings (randomized algorithms with failure ratio zero andrandomized/deterministic algorithms with bounded failure ratio) and providenatural language theoretic characterizations of the space complexity classes.