Regular Languages in the Sliding Window Model

Moses Ganardi, Danny Hucke, Markus Lohrey +2

We study the space complexity of the following problem: For a fixed regular language $L$, we receive a stream of symbols and want to test membership of a sliding window of size $n$…