AUTOMATA THEORY ON SLIDING WINDOWS

arXiv:1702.04376v2 [cs.FL] 5 Jan 2018

MOSES GANARDI, DANNY HUCKE, DANIEL KÖNIG, MARKUS LOHREY,
AND KONSTANTINOS MAMOURAS
Abstract. 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.

1. Introduction
1.1. Streaming algorithms. Streaming algorithms process an input sequence
a1 a2 · · · am from left to right and have at time t only direct access to the current data value at . Such algorithms have received a lot of attention in recent years,
see [1] for a broad introduction. The general goal of streaming algorithms is to
avoid the explicit storage of the whole data stream. Ideally, a streaming algorithm
works in constant space, in which case it reduces to a deterministic finite automaton
(DFA), but polylogarithmic space with respect to the input length might be acceptable, too. These small space requirements are motivated by the current explosion in
the size of the input data, which makes random access to the input often infeasible.
Such a scenario arises for instance when searching in large databases (e.g., genome
databases or web databases), analyzing internet traffic (e.g. click stream analysis),
and monitoring networks.
The first papers on streaming algorithms as we know them today are usually
attributed to Munro and Paterson [34] and Flajolet and Martin [20], although the
principle idea goes back to the work on online machines by Hartmanis, Lewis and
Stearns from the 1960’s [33, 38]. Extremely influential for the area of streaming
algorithms was the paper of Alon, Matias, and Szegedy [3].
1.2. The standard model and sliding window model. Two variants of streaming algorithms can be found in the literature:
• In the standard model the algorithm reads an input stream a1 a2 · · · am of
data values from left to right. At time instant t it has to output the value
f (a1 a2 · · · at ) for a certain function f .
• In the sliding window model the algorithm works on a sliding window. At
time instant t, the active window is a certain suffix at−n+1 at−n+2 · · · at of
a1 a2 · · · at and the algorithm has to output f (at−n+1 at−n+2 · · · at ).
For many applications the sliding window model is more appropriate. Quite often
data items in a stream are outdated after a certain time, and the sliding window
model is a simple way to model this. The typical application is the analysis of a time
series as it may arise in medical monitoring, web tracking, or financial monitoring.
In all these applications, data items are usually no longer important after a certain
1

2

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

time. Two variants of the sliding window model can be found in the literature; see
e.g. [4]:
• Fixed-size model: The size of the sliding window is a fixed constant (the
window size). In other words: at each time instant a new data value ai
arrives and the oldest data value from the sliding window expires.
• Variable-size model: The sliding window at−n+1 at−n+2 · · · at is determined
by an adversary. At every time instant the adversary can either remove the
first data value from the sliding window (expiration of a value), or add a
new data value at the right end (arrival of a new value).
In the seminal paper of Datar et al. [17], where the fixed-size sliding window model
was introduced, the authors show how to maintain the number of 1’s in a sliding
window of fixed size n over the alphabet {0, 1} in space 1ε · log2 n if one allows a
multiplicative error of 1 ± ε. A matching lower bound is proved as well in [17]. For
the upper bound, Datar et al. introduced a new data structure called exponential
histograms. Histogram techniques and variants have been used to approximate a
large variety of statistical data over sliding windows. Let us mention the work
on computation of the variance and k-median [5], quantiles [4], and entropy [9]
over sliding windows. Other computational problems that have been considered for
the sliding window model include optimal sampling [10], various pattern matching
problems [11, 13, 14, 15], database querying (e.g. processing of join queries [25])
and graph problems (e.g. checking for connectivity and computation of matchings,
spanners, and spanning trees [16]). Further references on the sliding window model
can be found in the surveys [1, Chapter 8] and [8].
1.3. Language recognition in the streaming model. A natural problem that
has been suprisingly neglected for the streaming model is language recognition.
The goal is to check whether an input string belongs to a given language L. Let
us quote Magniez, Mathieu, and Nayak [32]: “Few applications [of streaming] have
been made in the context of formal languages, which may have impact on massive
data such as DNA sequences and large XML files. For instance, in the context
of databases, properties decidable by streaming algorithm have been studied [36,
35], but only in the restricted case of deterministic and constant memory space
algorithms.” For Magniez et al. this was the starting point to study language
recognition in the streaming model. Thereby they restricted their attention to
the above mentioned standard streaming model. Note that in the standard model
the membership problem for a regular language is trivial to solve: One simply
has to simulate a DFA on the stream and thereby only store the current state of
the DFA. In [32] the authors present a randomized streaming algorithm for the
(non-regular)
Dyck language Ds with s pairs of parenthesis that works in space
√
O( n log n) and time polylog(n) per symbol. Further investigations on streaming
language recognition for various subclasses of context-free languages can be found
in [6, 7, 21, 28, 29, 35, 36]. Let us emphasize that all these papers exclusively deal
with the standard streaming model. Language recognition problems for the sliding
window model have been completely neglected so far. This was the starting point
for our previous paper [22].
1.4. Querying regular languages in the sliding window model. As mentioned above, the membership problem for a regular language L has a trivial constant space solution in the standard streaming model: One simply simulates a DFA
for L on the data stream by storing the current state. This solution does not work
for the sliding window model. The problem is the removal of the left-most symbol
from the sliding window. In order to check whether the active window belongs to a
certain language L one has to know this first symbol in general. In such a case one

AUTOMATA THEORY ON SLIDING WINDOWS

3

has to store the whole window content using O(n) bits (where n is the window size).
A simple regular language where this phenomenon arises is the language a{a, b}∗
of all words that start with a. The point is that by repeatedly checking whether
the sliding window content belongs to a{a, b}∗ , one can recover the exact content of
the sliding window, which implies that every sliding window algorithm for testing
membership in a{a, b}∗ has to use n bits of storage (where n is the window size).
For a function s(n) let Freg (s(n)) be the class of all languages L with the following
property: For every window size n there exists an algorithm that reads a data
stream, uses only space s(n) and correctly decides at every time instant whether
the active window (the last n symbols from the stream) belongs to L. Note that
this is a non-uniform model: for every window size n we use a separate algorithm.
The class Vreg (s(n)) of languages that have variable-size sliding window algorithm
with space complexity s(n) is defined similarly, see page 7 for details. Our main
result from [22] is a space trichotomy for regular languages:
(i) Vreg (o(n)) = Freg (o(n)) = Freg (O(log n)) = Vreg (O(log n))
(ii) Freg (o(log n)) = Freg (O(1))
(iii) Vreg (o(log n)) = Vreg (O(1)) = all trivial languages (empty and universal languages)
Each of the three cases is characterized in terms of the syntactic homomorphism
and the left Cayley graph of the syntactic monoid of the regular language. The
precise characterizations are a bit technical; see [22] for the details.
In this paper we continue our investigation of sliding-window algorithms for
regular languages. As a first contribution, we present very natural characterizations
of the above classes in (i) and (ii): The languages in (i) are exactly the languages
that are reducible with a Mealy machine (working from right to left) to a regular
language of polynomial growth. Note that the regular languages of polynomial
growth are exactly the bounded regular languages [40]. A language L is bounded
if L ⊆ w1∗ w2∗ · · · wn∗ for words w1 , w2 , . . . , wn . In addition, we show that the class
(i) is the Boolean closure of regular left ideals (regular languages L with Σ∗ L ⊆ L)
and regular length languages (regular languages where |u| = |v| implies that u ∈ L
iff v ∈ L). The class (ii) is characterized as the Boolean closure of suffix-testable
languages (languages L where membership in L only depends on a suffix of constant
length) and regular length languages. A natural example for the classes above is
the problem of testing whether the sliding window contains a fixed pattern w as a
factor (as a suffix) since we can check membership of the left ideal Σ∗ wΣ∗ (or of
the suffix-testable language Σ∗ w).
We also consider the sliding-window space complexity of regular languages in
a uniform setting, where the size m (number of states) of an automaton for the
regular language is also taken into account. In [22], we asked whether for DFAs
of size m that accept languages in Freg (O(log n)) = Vreg (O(log n)), there exists a
sliding-window streaming algorithm with space complexity poly(m)·log n. Here, we
give a negative answer by proving a lower bound of the form Ω(2m ·log n). Moreover,
we also show almost matching upper bounds.
Finally, we prove that one can test in nondeterministic logspace and hence in
deterministic polynomial time whether for a given DFA A the language L(A) belongs to the above class (i) (resp., (ii)). For NFAs these problems become Pspacecomplete.
1.5. Related work. In [19] Fijalkow defines the online space complexity of a language L. His definition is equivalent to the space complexity of the language L
in the standard streaming model described above. Among other results, Fijalkow

4

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

presents a probabilistic automaton A such that the language accepted by A (with
threshold 1/2) needs space Ω(n) in the streaming model.
Streaming a language L in the standard model is also related to the concept of
automaticity [37]. For a language L ⊆ Σ∗ , the automaticity AL of L is the function
n 7→ AL (n), where AL (n) is the minimal number of states of a DFA A such that
for all words w of length at most n: w ∈ L if and only if w ∈ L(A). Clearly, every
regular language L has constant automaticity. Karp [27] proved that for every nonregular language L, AL (n) ≥ (n + 3)/2 for infinitely many n. This implies that
for every non-regular language L, membership checking in the standard streaming
model is not possible in space o(log n).
2. Preliminaries
Throughout this paper we use log x as an abbreviation for ⌊log2 x⌋. Note that
if w1 , w2 , w3 , . . . is the length-lexicographic enumeration of all words from {0, 1}∗
then |wi | ≤ log i. We use the following well-known bounds for binomial coefficients,
where e is Euler’s constant:
k
 k   
n
e·n
n
≤
, for all 1 ≤ k ≤ n.
≤
k
k
k

Assume that u1 , . . . , uk ∈ {0, 1}+ are non-empty bit strings of total length n =
Pk
i=1 |ui |. To encode the tuple (u1 , . . . , uk ) we use a simple block code: We encode
each bit in ui except the first one by the mapping 0 7→ 00, 1 7→ 01. The first bit
in each ui is encoded by the mapping 0 7→ 10, 1 7→ 11. Then, the resulting bit
strings are concatenated, which results in an encoding with 2n bits. In the rest of
the paper, we will use this encoding without mentioning it explicitly. In fact, more
succinct encodings exist.
Let Σ≤n = {w ∈ Σ∗ : |w| ≤ n}. A prefix of a word w ∈ Σ∗ is a word u ∈ Σ∗ with
∗
w = uv for some v ∈ Σ∗ . The set of all prefixes
S of w ∈ Σ is denoted by Pref(w).
∗
For a language L ⊆ Σ we define Pref(L) = w∈L Pref(w) to be the set of prefixes
of words in L.
The reversal of a word x = a1 · · · an is defined as xR = an · · · a1 and the reversal
of a language L is LR = {xR : x ∈ L}. The reversal of a function τ : Σ∗ → Γ∗ is
defined as τ R (x) = τ (xR )R . Thus, τ (u) = v if and only if τ R (uR ) = v R .

2.1. Automata. We use standard definitions from automata theory. A nondeterministic finite automaton (NFA) is a tuple A = (Q, Σ, I, ∆, F ) where Q is a finite
set of states, Σ is an alphabet, I ⊆ Q is the set of initial states, ∆ ⊆ Q × Σ × Q is
the transition relation and F ⊆ Q is the set of final states. A deterministic finite
automaton (DFA) A = (Q, Σ, q0 , δ, F ) has a single initial state q0 ∈ Q instead of
I and a transition function δ : Q × Σ → Q instead of the transition relation ∆. A
deterministic automaton has the same format as a DFA, except that the state set
Q is not required to be finite. If A is deterministic, the transition function δ is extended to a function δ : Q × Σ∗ → Q in the usual way and we define A(x) = δ(q0 , x)
for x ∈ Σ∗ . The language accepted by A is denoted by L(A).
The Myhill-Nerode congruence ∼L of a language L ⊆ Σ∗ is the equivalence
relation on Σ∗ defined by x ∼L y if and only if
∀z ∈ Σ∗ : xz ∈ L ⇐⇒ yz ∈ L,

which is a right congruence on Σ∗ , i.e. x ∼L y implies xz ∼L yz for all x, y, z ∈ Σ∗ .
For a word x ∈ Σ∗ the left quotient x−1 L is {z ∈ Σ∗ : xz ∈ L}. Thus, x ∼L y if and
only if x−1 L = y −1 L. If A is a deterministic automaton for a language L ⊆ Σ∗ , then
A(x) = A(y) implies x ∼L y. Furthermore, L is recognized by the deterministic
automaton A = (Q, Σ, q0 , δ, F ) with state set Q = Σ∗ /∼L , transition function

AUTOMATA THEORY ON SLIDING WINDOWS

5

δ([x]∼L , a) = [xa]∼L , initial state q0 = [ε]∼L and final states F = {[x]∼L : x ∈ L},
which is the minimal deterministic automaton for L (up to isomorphism).
For an NFA A we denote with AD the corresponding deterministic power set
automaton (restricted to those states that are reachable from the initial state) and
with AR the NFA obtained from A by reversing all transitions and swapping the
set of initial states and the set of final states. Moreover, we define ARD = (AR )D .
Thus, L(AR ) = L(ARD ) = L(A)R . If an NFA A has m states, then both AD and
ARD have at most 2m states.
A language L ⊆ Σ∗ is recognized by a monoid M , if there exists a homomorphism
h : Σ∗ → M and a set F ⊆ M such that h−1 (F ) = L. The syntactic congruence
≡L of L is defined by x ≡L y if and only if
∀u, v ∈ Σ∗ : uxv ∈ L ⇐⇒ uyv ∈ L.
It refines ∼L , i.e., x ≡L y implies x ∼L y. The syntactic monoid of a language L is
the quotient monoid Σ∗ /≡L and the mapping h : Σ∗ → Σ∗ /≡L , h(x) = [x]≡L is the
syntactic homomorphism of L. It is known that a language is regular if and only if
its syntactic monoid is finite.
2.2. Streaming algorithms. A data stream is just a finite sequence of data values.
We make the assumption that these data values are from a finite set Σ. Thus, a
data stream is a finite word w = a1 a2 · · · am ∈ Σ∗ . A streaming algorithm reads
the symbols of a data stream from left to right. At time instant t the algorithm
has only access to the symbol at and the internal storage, which is encoded by a
bit string. The goal of the streaming algorithm is to compute a certain function
f : Σ∗ → A into some domain A, which means that at time instant t the streaming
algorithm outputs the value f (a1 a2 · · · at ). In this paper, we only consider the
Boolean case A = {0, 1}; in other words, the streaming algorithm tests membership
of a fixed language. Furthermore, we abstract away from the actual computation
and only analyze the space requirement. Formally, a streaming algorithm over Σ is
a deterministic (possibly infinite) automaton A = (S, Σ, s0 , δ, F ), where the states
are encoded by bit strings. We describe this encoding by an injective function
enc : S → {0, 1}∗. The space function space(A, ·) : Σ∗ → N specifies the space used
by A on a certain input: For w ∈ Σ∗ let space(A, w) = max{|enc(A(u))| : u ∈
Pref(w)}. We also say that A is a streaming algorithm for the accepted language
L(A).

3. Sliding window streaming models
In the above streaming model, the output value of the streaming algorithm at
time t depends on the whole past a1 a2 · · · at of the data stream. However, in many
practical applications one is only interested in the relevant part of the past. Two
formalizations of “relevant past” can be found in the literature:
• Only the suffix of a1 a2 · · · at of length n is relevant. Here, n is a fixed constant. This streaming model is called the fixed-size sliding window model.
• The relevant suffix of a1 a2 · · · at is determined by an adversary. In this
model, at every time instant the adversary can either remove the first symbol from the active window (expiration of a data value), or add a new
symbol at the right end (arrival of a new data value). This streaming
model is also called the variable-size sliding window model.
In the following two paragraphs, we formally define these two models.

6

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

3.1. Fixed-size sliding windows. Given a word w = a1 a2 · · · am ∈ Σ∗ and a
window length n ≥ 0, we define lastn (w) ∈ Σn by
(
am−n+1 am−n+2 · · · am , if n ≤ m,
lastn (w) =
an−m a1 · · · am ,
if n > m,

which is called the active window. Here a ∈ Σ is an arbitrary symbol, which fills the
initial window. A sequence A = (An )n≥0 is a fixed-size sliding window algorithm for
a language L ⊆ Σ∗ if each An is a streaming algorithm for {w ∈ Σ∗ : lastn (w) ∈ L}.
Its space complexity is the function fA : N → N ∪ {∞} where fA (n) is the maximum
encoding length of a state in An .
Note that for every language L and every n the language {w ∈ Σ∗ : lastn (w) ∈ L}
is regular, which ensures that An can be chosen to be a DFA and hence fA (n) < ∞
for all n ≥ 0. The trivial fixed-size sliding window algorithm for L is the sequence
b
B = (Bn )n≥0 , where Bn is the DFA with state set Σn and transitions au −
→ ub
n−1
for a, b ∈ Σ, u ∈ Σ
. States of Bn can be encoded with O(log |Σ| · n) bits. By
minimizing each Bn , we obtain an optimal fixed-size sliding window algorithm A
for L. Finally, we define FL (n) = fA (n). Thus, FL is the space complexity of an
optimal fixed-size sliding window algorithm for L. Notice that FL is not necessarily
monotonic. For instance, take L = {au : u ∈ {a, b}∗, |u| odd}. Then, we have
FL (2n) ∈ Θ(n) and FL (2n + 1) ∈ O(1). The above trivial algorithm B yields
FL (n) ∈ O(n) for every language L.
Note that the fixed-size sliding window is a non-uniform model: for every window
size we have a separate streaming algorithm and these algorithms do not have to
follow a common pattern. Working with a non-uniform model makes lower bounds
stronger. In contrast, the variable-size sliding window model that we discuss next is
a uniform model in the sense that there is a single streaming algorithm that works
for every window length.

3.2. Variable-size sliding windows. For an alphabet Σ we define the extended
alphabet Σ = Σ ∪ {↓}. In the variable-size model the active window wnd(u) ∈ Σ∗
∗
for a stream u ∈ Σ is defined by
• wnd(ε) = ε
• wnd(ua) = wnd(u) · a for a ∈ Σ
• wnd(u ↓) = ε if wnd(u) = ε
• wnd(u ↓) = v if wnd(u) = av for a ∈ Σ
A variable-size sliding window algorithm for a language L ⊆ Σ∗ is a streaming
∗
algorithm A for {w ∈ Σ : wnd(w) ∈ L}. Its space complexity is the function
vA : N → N ∪ {∞} mapping each window length n to the maximum number of bits
used by A on inputs producing an active window of size at most n. Formally, it is
the function
∗

vA (n) = max{space(A, u) : u ∈ Σ , |wnd(v)| ≤ n for all v ∈ Pref(u)},

which is a monotonic function.1

Lemma 3.1. For every language L ⊆ Σ∗ there exists a variable-size sliding window algorithm A such that vA (n) ≤ vB (n) for every variable-size sliding window
algorithm B for L and every n.
Proof. Let A = (S, Σ, s0 , δ, F ) be the minimal deterministic automaton for {w ∈
∗
Σ : wnd(w) ∈ L}. The state set S can be finite or infinite. It has the property
1The definition of v (n) slightly deviates from the one given in [22], namely v′ (n) =
A
A
∗

′ (k) and
max{|enc(A(u))| : u ∈ Σ , |wnd(u)| = n}. One easily sees that vA (n) = maxk≤n vA
′ (n) for monotonic functions v ′ (n).
hence vA (n) = vA
A

AUTOMATA THEORY ON SLIDING WINDOWS

7

that the active window determines the current state, i.e. A(x) = A(wnd(x)) for all
∗
x ∈ Σ . For n ≥ 0 let Sn ⊆ S be the set of states reachable in A from the initial
state s0 by a word over Σ of length at most n. By the aforementioned property all
∗
words x ∈ Σ with |wnd(x)| ≤ n lead to a state A(x) = A(wnd(x)) ∈ Sn . Now
one can define an encoding such that the space complexity of A is log |Sn |: Define
an enumeration of S by starting with s0 , then listing (in any order) all states from
S1 \ S0 , followed by the states from S2 \ S1 , and so one. Then we encode the i-th
state from this list by the i-th bit string in length-lexicographical order.
Now let B be any variable-size sliding window algorithm for L. Let Tn be the
set of states reachable in B from the initial state by a word of length at most
n. By reading a word of length at most n, the window length never exceeds n.
Therefore, the encoding length of any t ∈ Tn is bounded by vB (n), which implies
|Tn | ≤ 2vB (n)+1 −1. We get log |Tn | ≤ vB (n). Since A is minimal we have |Sn | ≤ |Tn |
and therefore vA (n) ≤ vB (n).

We define VL (n) = vA (n), where A is a space optimal variable-size sliding window
algorithm for L from Lemma 3.1. Since any algorithm in the variable-size model
yields an algorithm in the fixed-size model, we have FL (n) ≤ VL (n).
3.3. Space complexity classes and closure properties. For a function s : N →
N we define the classes F(s) and V(s) of all languages L ⊆ Σ∗ which have a fixedsize (variable-size, respectively) sliding window algorithm with space complexity
bounded by s(n). For a class C of S
functions (here, it will be always an O-class,
Θ-class or o-class) we define X(C) = s∈C X(s) for X ∈ {F, V}.
Several times we will make use of the simple fact that for both the fixed-size and
the variable-size model, space classes form a Boolean algebra:
Lemma 3.2. Let X ∈ {F, V }. If L ⊆ Σ∗ is a Boolean combination of languages
Pk
L1 , . . . , Lk ⊆ Σ∗ , then XL (n) ≤ 2 i=1 XLi (n). In particular, for any function
s(n), the classes F(O(s)) and V(O(s)) form Boolean algebras.
Proof. Run the sliding window-algorithms for L1 , . . . , Lk in parallel and encode the
tuple of k states by a single bit string. The output bits of the individual algorithms
determine the output of the total algorithm.

A Mealy machine M = (Q, Σ, Γ, q0 , δ) consists of a finite set of states Q, an input
alphabet Σ, an output alphabet Γ, an initial state q0 ∈ Q and the transition function
δ : Q × Σ → Q × Γ. For every q ∈ Q the machine computes a length-preserving
transduction τq : Σ∗ → Γ∗ in the usual way: τq (ε) = ε and if δ(p, a) = (q, b) then
τp (au) = b τq (u). We call τqR0 the ←-transduction computed by M. Thus, a ←transduction is computed by a Mealy machine that works on an input word from
right to left. If L is regular and τ is a ←-transduction, then τ (L) and τ −1 (L) are
regular as well. A ←-transduction τ is called a ←-reduction from K ⊆ Σ∗ to L ⊆ Γ∗
if x ∈ K if and only if τ (x) ∈ L for all x ∈ Σ∗ .
Lemma 3.3. Let X ∈ {F, V }. If K is ←-reducible to L via a Mealy machine with
d states, then XK (n) ≤ 2d · XL (n). In particular, for any function s(n) the classes
F(O(s)) and V(O(s)) are closed under ←-reductions.
Proof. We only give the proof for the variable-size model; analogous arguments
hold for the fixed-size model. Let A be an optimal variable-size sliding window
algorithm for L. Recall from the proof of Lemma 3.1 that A(w) = A(wnd(w)) for
∗
all streams w ∈ Σ . Let M = (Q, Σ, Γ, q0 , δ) be a Mealy machine such that τqR0 is
a ←-reduction from K to L. Let Q = {q0 , . . . , qd−1 } be the state set of M.

8

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

We claim that there exists a sliding window algorithm B which given an input
∗
stream w ∈ Σ maintains an encoding of the tuple
B(w) = (A(τqR0 (wnd(w))), . . . , A(τqRd−1 (wnd(w)))).
• On input ↓ we can compute
B(w ↓) = (A(τqR0 (wnd(w)) ↓), . . . , A(τqRd−1 (wnd(w)) ↓))
from B(w).
• Given an input symbol a ∈ Σ, compute δ(qi , a) = (pi , bi ) for all 0 ≤ i ≤ d−1.
Since
τqRi (wnd(wa)) = τpRi (wnd(w)) bi
we can compute
B(wa) = (A(τpR0 (wnd(w)) b0 ), . . . , A(τpRd−1 (wnd(w)) bd−1 )).
• The active window belongs to L if and only if A(τqR0 (wnd(w))) is final in A.
The above variable-size sliding window algorithm has space complexity 2d·VL (n): If
∗
w = Σ is such that |wnd(u)| ≤ n for all u ∈ Pref(w), then also |τqRi (wnd(u))| ≤ n
for all u ∈ Pref(w), 0 ≤ i ≤ d − 1. Hence, |A(τqRi (wnd(u)))| ≤ VL (n) for all
u ∈ Pref(w), 0 ≤ i ≤ d − 1. Thus, every tuple B(a1 · · · at ) can be encoded with at
most 2d · VL (n) bits.

3.4. Space trichotomy for regular languages. In [22] we proved a trichotomy
theorem on sliding window algorithms for regular languages. We identified a partition of the class of regular languages into three classes which completely characterize the sliding window space complexity in both the fixed-size and the variable-size
model. One can easily see that the syntactic monoid of a language does not determine its space complexity: Z2 is the syntactic monoid of both languages K = “even
length” and L = “even number of a’s” over {a, b} but VK (n) = O(log n) whereas
FL (n) = Θ(n). The definition of the mentioned three classes is given in terms of
the syntactic homomorphism and the left Cayley graph of the syntactic monoid of
the regular language, see [22].
For X ∈ {F, V} and a class C of functions we abbreviate X(C) ∩ REG by Xreg (C),
where REG is the class of all regular languages.
Theorem 3.4 ([22]). The following holds:
• Vreg (o(n)) = Freg (o(n)) = Freg (O(log n)) = Vreg (O(log n))
• Freg (o(log n)) = Freg (O(1))
• Vreg (o(log n)) = Vreg (O(1)) = all trivial languages (empty and universal
languages)
Strictly speaking, [22, Theorem 7] only claims VL (n) ∈
/ O(1) for all languages
∅ ( L ( Σ∗ . However, the proof of [22, Theorem 7] does imply the stronger bound
VL (n) ∈
/ o(log n). This statement will also be reproved in the following section.
Let us comment on a subtle point. When making statements about the space
complexity functions VL (n) and FL (n) it is in general important to fix the underlying alphabet. For instance according to point (iii) from Theorem 3.4 we have
VL (n) ∈ O(1) for the language L = {a}∗ if the underlying alphabet is {a}. On the
other hand, if the underlying alphabet is {a, b} then VL (n) 6∈ O(1) (in fact, L then
belongs to Vreg (Θ(log n))).

AUTOMATA THEORY ON SLIDING WINDOWS

9

4. Variable-size space complexity and language growth
In this section we reprove the space trichotomy (Theorem 3.4) for the variablesize model. For this we relate the function VL (n) to the growth of a certain derived
language and then use the well known results about the growth of regular languages.
We need the following definition. For a language L ⊆ Σ∗ define the mapping
ψL : Σ∗ → (Σ∗ /∼L )∗ by:
ψL (a1 · · · an ) = [a1 · · · an ]∼L [a2 · · · an ]∼L · · · [an ]∼L .

Notice that ψL is a length-preserving mapping from Σ∗ to the set of words over the
alphabet Σ∗ /∼L . Although Σ∗ /∼L may be infinite (namely for non-regular L), the
image ψL (Σ≤n ) has at most |Σ|n+1 − 1 elements for each n ≥ 0.

Theorem 4.1. For every language ∅ ( L ( Σ∗ we have VL (n) = log |ψL (Σ≤n )|.

Proof. We first exhibit a variable-size sliding window algorithm A with space com∗
plexity log |ψL (Σ≤n )|. The idea is that on input w ∈ Σ the algorithm A is in
state A(w) = ψL (wnd(w)). Consider an active window a1 · · · an ∈ Σ∗ . Three
observations are crucial:
• The state ψL (a2 · · · an ) can be obtained from the state ψL (a1 · · · an ) by
removing the first ∼L -class [a1 · · · an ]∼L .
• From the state ψL (a1 · · · an ) and a symbol a ∈ Σ one can obtain the state
ψL (a1 · · · an a) = [a1 · · · an a]∼L [a2 · · · an a]∼L · · · [an a]∼L [a]∼L , since ∼L is a
right-congruence.
• The first ∼L -class in ψL (a1 · · · an ) determines whether a1 · · · an ∈ L.
These remarks define a variable-size sliding window algorithm for L with state set
ψL (Σ∗ ). It remains to define the binary encoding of the states, This is done similarly
to the proof of Lemma 3.1: List ψL (Σ∗ ) by starting with ψL (ε) = ε, followed by
all states from ψL (Σ) (in any order), followed by all states from ψL (Σ2 ), and so on.
The i-th state in this list is encoded by the i-th bit string in length-lexicographical
order. Under this encoding the above variable-size sliding window algorithm has
space complexity log |ψL (Σ≤n )|.
Conversely, consider a variable-size sliding window algorithm A for L with space
complexity vA (n). We have to show that vA (n) ≥ log |ψL (Σ≤n )|. Let x =
a1 a2 · · · am ∈ Σ∗ be an input word of length m ≤ n. Notice that |enc(A(x))| ≤
v(m) ≤ v(n) by the monotonicity of v.
We first show that A(x) determines m = |x|. Assume that ε ∈ L (the case that
ε∈
/ L is analog), and let y ∈
/ L where |y| is chosen minimally. Starting from A(x)
we read y into A, followed by an infinite sequence of ↓. We obtain a run
y

↓

↓

↓

↓

→ ...
→ s3 −
→ s2 −
→ s1 −
A(x) −
→ s0 −

where sm is not final and for all i > m the state si is final, by minimality of |y|.
Clearly this run determines m.
We now show that A(x) uniquely determines ψL (a1 · · · am ). By the above argument, we know that A(x) determines the window length m. Furthermore, A(x)
determines every equivalence class [ak · · · am ]∼L for 1 ≤ k ≤ m: Starting from
A(x) we read k − 1 times ↓ into A. Then, the active window is ak · · · am . We can
determine the left quotient (ak · · · am )−1 L = {z ∈ Σ∗ : ak · · · am z ∈ L} by reading
each word z into A and testing whether ak · · · am z ∈ L. The left quotient in turn
determines [ak · · · am ]∼L .
To sum up, we have shown that every value ψL (x) for x ∈ Σ≤n can be encoded by a bit string of length at most v(n), namely enc(A(x)). Since there are
|ψL (Σ≤n )| such values, it follows that 2v(n)+1 − 1 ≥ |ψL (Σ≤n )|, which implies
v(n) ≥ log |ψL (Σ≤n )|.


10

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

Note that Theorem 4.1 does not hold for L = ∅ or L = Σ∗ . In these cases, we
have VL (n) = 0 and log |ψL (Σ≤n )| = log(n + 1).
We can use Theorem 4.1 to reprove the space trichotomy for regular languages
in the variable-size sliding window model. For this, we need the following simple
lemma:
Lemma 4.2. If L ⊆ Σ∗ is regular, then ψL is a ←-transduction. In particular,
ψL (Σ∗ ) and ψL (L) are regular. Furthermore ψL is a ←-reduction from L to ψL (L).

Proof. Let h : Σ∗ → M be the syntactic homomorphism of L into the syntactic
monoid M of L. Since the syntactic congruence refines the Myhill-Nerode congruence, there exists a function ν : M → Σ∗ /∼L such that [x]∼L = ν(h(x)) for all
x ∈ Σ∗ . Define the Mealy machine with the state set M and transitions
δ(m, a) = (h(a) · m, ν(h(a) · m))

for all m ∈ M , a ∈ Σ. This Mealy machine computes the ←-transduction ψL .
If ψL (x) = ψL (y) then either both or none of the words x, y belong to L. This
proves that ψL is indeed a reduction from L to ψL (L).

The growth of a language L ⊆ Σ∗ is the function g(n) = |{x ∈ L : |x| ≤ n}|.
Since the growth of every regular language is either Θ(nd ) for some integer d ≥ 0
or Ω(rn ) for some r > 1 [24, Section 2.3], Theorem 4.1 and Lemma 4.2 reprove the
trichotomy theorem for variable-size windows: For every regular language L, VL (n)
is either in O(1), Θ(log n) or Θ(n). Furthermore, since |ψL (Σ≤n )| ≥ n + 1 we have
VL (n) ∈ Ω(log n) for every non-trivial language L.

Theorem 4.3. If L ⊆ Σ∗ has growth g(n), then FL (n) ∈ O(log g(n) + log n).

Proof. Let n ≥ 0 be a window size and let w1 , . . . , wm be an arbitrary enumeration
of L ∩ Σn where m ≤ g(n). Assume that w = a1 · · · an ∈ Σ∗ is the active window.
The algorithm stores the longest suffix v = ai · · · an of w such that v is a prefix of
a word wj ∈ L ∩ Σn . Notice that v can be encoded by the binary encoded number
j using log g(n) bits and the binary encoded number i using log n bits. Of course,
there may exist several words wj having v as a prefix; in this case the concrete
choice of wj does not matter. This information clearly suffices to check whether
the active window belongs to L. Moreover, we can update the information: If
an+1 ∈ Σ is the next symbol from the stream, then we distinguish the following
cases:
• If i > 1 and ai · · · an an+1 is a prefix of a word from L ∩ Σn , say wj ′ ,
1 ≤ j ′ ≤ m, then we replace i, j by i − 1, j ′ .
• Otherwise let i < i′ ≤ n + 1 be minimal such that ai′ · · · an an+1 is a prefix
of a word from L ∩ Σn , say wj ′ , 1 ≤ j ′ ≤ m. We replace i, j by i′ , j ′ .
The correctness of this algorithm is straightforward.

5. Logspace sliding-window algorithms
In this section, we give a new and more natural characterization of languages
in Vreg (O(log n)). Moreover, we analyze the influence of the size of the automaton
on the O-constant. In [22] we gave the space bound O(mm · (m · log(m) + log(n)))
if the regular language is given by a DFA with m states. Below, we improve this
bound to O(2m · m · log(n)).
Let B = (Q, Σ, q0 , δ, F ) be a DFA. A strongly connected component (SCC for
short) of B is an inclusion-maximal subset C ⊆ Q such that for all p, q ∈ C there
exist words u, v ∈ Σ∗ such that δ(p, u) = q and δ(q, v) = p. The crucial property that enables logspace sliding-window algorithms is captured by the following
definition:

AUTOMATA THEORY ON SLIDING WINDOWS

11

Definition 5.1. Let B = (Q, Σ, q0 , δ, F ) be a DFA. An SCC C ⊆ Q is well-behaved
if for all q ∈ C and u, v ∈ Σ∗ with |u| = |v| and δ(q, u), δ(q, v) ∈ C we have:
δ(q, u) ∈ F if and only if δ(q, v) ∈ F . If every SCC in B which is reachable from
q0 is well-behaved, then B is called well-behaved.
It turns out that L ∈ Vreg (O(log n)) if and only if LR can be accepted by a
well-behaved DFA, and we will prove this fact below. Thereby we determine the
dependence of the constant in the O(log n) bound with respect to the size of an
automaton (DFA or NFA) for L.
Let B be a well-behaved DFA and let ρ be a run in B, which does not necessarily
start in the initial state. Let C1 , . . . , Ck be the sequence of pairwise different SCCs
that are visited by ρ in that particular order. The path summary of ρ is the sequence
(p1 , ℓ1 , p2 , ℓ2 , . . . , pk , ℓk ) where pi is the first state in Ci visited by ρ, and ℓi ≥ 0 is
the number of symbols read in ρ from the first occurrence of pi until the first state
from Ci+1 (or until the end for pk ). The number of different path summaries of runs
of length n in a DFA B with m states can be bounded by (e is Euler’s constant)





m
n+m−1
n+m
e · (n + m)
(1) mm ·
≤ mm ·
≤ mm ·
≤ em · (n + m)m .
m−1
m
m
Here, (i) mm is the number of sequences of m states (we can repeat the last state in
a path summary so that we have exactly m states) and (ii) n+m−1
is the number
m−1
of ordered partitions of n into m summands.

Theorem 5.2. Let L ⊆ Σ∗ be regular and let A be a finite automaton for L with
m states. Assume that B = ARD is well-behaved. There are constants cm , dm that
only depend on m such that the following holds:
• If A is a DFA then VL (n) ≤ (2m · m + 1) · log n + cm for n large enough.
• If A is an NFA then VL (n) ≤ (4m + 1) · log n + dm for n large enough.
Proof. A set D ⊆ Σ∗ distinguishes L if for all x, y ∈ Σ∗ with x 6∼L y there exists
z ∈ D such that exactly one of the words xz and yz belongs to L. If A is a DFA
with m states, then there are at most m distinct left quotients x−1 L. Since every
family of m sets has a distinguishing set of size at most m − 1 [18], we get a set D
of size at most m − 1 that distinguishes L. If A is an NFA with m states, we can
clearly choose |D| ≤ 2m − 1 by determinizing A.
For a window content w = a1 · · · an we define a 0-1-matrix Aw : D ×{1, . . . , n} →
{0, 1} by Aw (z, i) = 1 iff ai · · · an z ∈ L. Notice that the i-th column Aw (·, i)
determines [ai · · · an ]∼L , and vice versa, for all 1 ≤ i ≤ n. In particular, the matrix
Aw determines ψL (w) and vice versa. Thus, |ψL (Σ≤n )| = |{Aw : w ∈ Σ≤n }|. By
Theorem 4.1, it therefore suffices to bound |{Aw : w ∈ Σ≤n }|.
We can encode each row Aw (z, ·) of Aw succinctly as follows. Consider one row
indexed by z ∈ D. Let ρz be the run of B on the word (wz)R and ρ̃z be the subrun
of ρz which only reads the suffix wR of (wz)R . One can reconstruct Aw (z, ·) from
the path summary of ρ̃z . Thus Aw can be encoded by |D| many path summaries.
With (1) and the fact that B has at most 2m states, we get the bound
|{Aw : w ∈ Σ≤n }| ≤

n
X
i=0

m

e2

|D|

m

· (i + 2m )2

|D|

Hence, for the DFA case (where |D| ≤ m − 1) we have
VL (n)

m

≤ (n + 1) · e2

|D|

= log |ψL (Σ≤n )|
≤ log(n + 1) + 2m · m · (log e + log(n + 2m ))
≤ (2m · m + 1) · log n + cm

m

· (n + 2m )2

|D|

.

12

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

for n large enough, where cm can be chosen as 1 + 2m · m · log e + m2 · 2m . The
calculation for the NFA case (where |D| ≤ 2m − 1) is analogous.

Finally, we show a linear space lower bound for the case that the reversal of L
is recognized by a non-well-behaved DFA.
Theorem 5.3. Let L ⊆ Σ∗ be a regular language and B be a DFA which recognizes
LR and which is not well-behaved. Then VL (n) ∈ Ω(n) and FL (n) ∈ O(n) \ o(n).

Proof. Let q0 be the initial state of B. Since B is not well-behaved, there are states
p, p0 , p1 and words u, u0 , v0 , u1 , v1 ∈ Σ∗ such that |u0 | = |v0 |, p0 is not final, p1 is
v1
u1
v0
u
u0
p. We can ensure that |u1 | = |v1 |:
p1 −→
p and p −→
p0 −→
final and q0 −
→ p, p −→
If k = |u0 v0 | and ℓ = |u1 v1 |, we replace v0 by v0 (u0 v0 )ℓ−1 and v1 by v1 (u1 v1 )k−1 .
For any α = α1 · · · αn ∈ {0, 1}∗ we define the word
w(α) = u uα1 vα1 · · · uαn vαn .

Notice that the length of w(α) is |u| + kℓ|α| ∈ O(|α|). Let α 6= β be two bit
strings of length n which differ in position i, say αi = 1 and βi = 0. Then B
accepts u uα1 vα1 · · · uαi but rejects u uβ1 vβ1 · · · uβi , which are prefixes of w(α) and
w(β), respectively, of the same length. In particular, ψL (w(α)R ) 6= ψL (w(β)R ).
Therefore, for any n ≥ 0, the language ψL (Σ∗ ) contains at least 2n words of length
O(n). By Theorem 4.1 and monotonicity of VL (n), this implies VL (n) = Ω(n). By
Theorem 3.4 we also know that FL (n) ∈ O(n) \ o(n).

From Theorem 5.2 and Theorem 5.3 we obtain:
Corollary 5.4. Let X ∈ {F, V}. A regular language L ⊆ Σ∗ belongs to X(O(log n))
if and only if LR is recognized by a well-behaved DFA.
5.1. Alternative Characterizations of Vreg (O(log n)). In the following we will
give two further very natural characterizations of the languages in Vreg (O(log n)) =
Freg (O(log n)) that we will also need in Section 7.
A language L ⊆ Σ∗ is called a left ideal (right ideal) if Σ∗ L ⊆ L (LΣ∗ ⊆ L).
A language L ⊆ Σ∗ is called a length language if for all n ∈ N, either Σn ⊆ L or
L ∩ Σn = ∅. Clearly, L is a length language iff LR is a length language, and L is
left ideal iff LR is a right ideal. In this section we will prove the following theorem.
Theorem 5.5. Let L ⊆ Σ∗ be regular. The following statements are equivalent:
(1) L ∈ F(O(log n))
(2) L ∈ V(O(log n))
(3) LR is recognized by a well-behaved DFA.
(4) L is ←-reducible to a regular language of polynomial growth.
(5) L is a Boolean combination of regular left ideals and regular length languages.
The equivalence of points 1. and 2. was already shown in [22], and the equivalence
of 2. and 3. was shown in the last section. The implication from 2. to 4. follows from
Theorem 4.1 and Lemma 4.2. In the rest of the section, we prove the directions
from 5. to 3., and from 4. to 5.
We start with two simple observations, which prove the direction from 5. to 3.
Lemma 5.6. If a regular language L ⊆ Σ∗ is a right ideal or a length language,
then the minimal DFA for L is well-behaved.
Proof. If A is the minimal DFA for a length language then for all states q and all
u, v ∈ Σ∗ with |u| = |v|, we have: δ(q, u) ∈ F if and only if δ(q, v) ∈ F .
If A is the minimal DFA for a right ideal, then for all final states q and all u ∈ Σ∗ ,
the state δ(q, u) is final as well. Hence, for every SCC C either all states of C are
final or all states of C are non-final.


AUTOMATA THEORY ON SLIDING WINDOWS

13

Lemma 5.7. The class of languages L ⊆ Σ∗ recognized by well-behaved DFAs is
closed under Boolean operations.
Proof. If A is well-behaved then the complement automaton A is also well-behaved.
Given two well-behaved DFAs A1 , A2 , we claim that the product automaton A1 ×A2
recognizing the intersection language is also well-behaved. Consider an SCC S of
A1 ×A2 which is reachable from the initial state and let (p1 , p2 ), (q1 , q2 ), (r1 , r2 ) ∈ S
such that
u
v
(p1 , p2 ) −
→ (q1 , q2 ) and (p1 , p2 ) −
→ (r1 , r2 )
u

for some words u, v ∈ Σ∗ with |u| = |v|. Since for i ∈ {1, 2} we have pi −
→ qi and
v
→ ri , and {pi , ri , qi } is contained in an SCC of Ai (which is also reachable from
pi −
the initial state), we have
(q1 , q2 ) is final

⇐⇒
⇐⇒

⇐⇒

q1 and q2 are final
r1 and r2 are final
(r1 , r2 ) is final,

and therefore A1 × A2 is well-behaved.



It remains to show the implication from 4. to 5.
Lemma 5.8. The class of Boolean combinations of regular left ideals and regular
length languages is closed under pre-images of ←-transductions.

Proof. For any function τ : Σ∗ → Γ∗ and K, L ⊆ Γ∗ we have τ −1 (K ∪ L) =
τ −1 (K) ∪ τ −1 (L) and τ −1 (Γ∗ \ L) = Σ∗ \ τ −1 (L). Now assume that τ is a ←transduction. Since it is length-preserving, the τ -pre-image of a length language
is again a length language. Finally, τ -pre-images of left ideals are left ideals again
because τ −1 (Γ∗ L) = Σ∗ τ −1 (L).


It remains to prove that every regular language of polynomial growth is a Boolean
combination of regular left ideals and regular length languages. Since a language L
and its reversal LR have the same growth, we can instead show that every regular
language of polynomial growth is a Boolean combination of regular right ideals
and regular length languages. The idea is to decompose every regular language of
polynomial growth as a finite union of languages recognized by so called linear cycle
automata.
In the following we will allow partial DFAs A = (Q, Σ, q0 , δ, F ) where δ : Q×Σ →
Q is a partial function. An SCC C of a partial DFA A = (Q, Σ, q0 , δ, F ) is called a
cycle if for every p ∈ C there exists at most one a ∈ Σ such that δ(p, a) ∈ C. Note
that a singleton SCC C = {p} such that δ(p, a) 6= p whenever δ(p, a) is defined is
a cycle, too. Such a cycle is called trivial. A partial DFA A = (Q, Σ, q0 , δ, F ) is a
linear cycle automaton if
• for all p, q ∈ Q there exists at most one symbol a ∈ Σ such that δ(p, a) = q,
• every SCC C of A is a (possibly trivial) cycle,
• there is an enumeration C1 , . . . , Ck of the SCCs of A such that there is
exactly one transition from Ci to Ci+1 for 1 ≤ i ≤ k − 1, and there is no
transition from Ci to Cj for j > i + 1,
• q0 belongs to C1 ,
• |F | = 1 and the unique final state belongs to Ck .
Lemma 5.9. If L is a regular language with polynomial growth, then L is a finite
union of languages recognized by linear cycle automata.
Proof. Let A = (Q, Σ, q0 , δ, F ) be the minimal DFA for a regular language L ⊆ Σ∗
of polynomial growth. We first remove from A all states from which no state in

14

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

F is reachable; then A becomes a partial DFA. By [24, Lemma 2] for every q ∈ Q
there exists a word uq ∈ Σ∗ such that the language {w ∈ Σ∗ : δ(q, w) = q} is a
subset of u∗q . Thus, for every SCC C of A and every state q ∈ C there is at most
one symbol a ∈ Σ with δ(q, a) ∈ C.
A path description is a sequence
P = (p1 , C1 , q1 , a1 , p2 , C2 , q2 , a2 , . . . , pk , Ck , qk )
where C1 , . . . , Ck is a chain in the partial ordering on the set of SCCs of A, p1 = q0 ,
pi , qi ∈ Ci for all 1 ≤ i ≤ k, δ(qi , ai ) = pi+1 for all 1 ≤ i < k and qk ∈ F . Clearly
there are only finitely many path descriptions. To every accepting run of A we
can assign a path description, which indicates the SCCs traversed in the run and
the transitions that lead from one SCC to the next SCC. We can write L(A) as a
finite union of languages over all path descriptions. For every path description P ,
we take the set of all words accepted by a run of A whose path description is P .
Consider a single path description P = (p1 , C1 , q1 , a1 , p2 , C2 , q2 , a2 , . . . , pk , Ck , qk )
and let B be the restriction of A to the SCCs Ci . Furthermore all transitions between two distinct SCCs are removed except for the transitions (qi , ai , pi+1 ). Finally,
qk becomes the only final state of B. Then B is indeed a linear cycle automaton. 
Lemma 5.10. Let A be a linear
Ss cycle automaton. There are linear cycle automata
A1 , . . . , As such that L(A) = i=1 L(Ai ) and in each Ai each non-trivial cycle has
the same length.
Proof. Let m1 , . . . , mk be the lengths of each non-trivial cycle (SCC) in A and m
be the least common multiple of m1 , . . . , mk . The language L(A) is the finite union
of all languages accepted by linear cycle automata that are obtained from A by
doing the following replacement for every non-trivial cycle
a

am

a

−1

am

i
2
1
q1
q3 · · · qmi −1 −−−i−→ qmi −−→
q2 −→
C : q1 −→

of A. W.l.o.g. assume that q1 is either the initial state of A or the target state of
m
(we
the unique transition entering C. Choose an arbitrary number 0 ≤ di < m
i
then take the finite union over all such choices). We replace C by a path P of
length di mi followed by cycle C ′ of length m, having the form
w di

P : q1′ −−→ q1 ,

a

a

am−1

a

2
1
→ q1 ,
q3 · · · qm−1 −−−→ qm −−m
q2 −→
C ′ : q1 −→

where a1 a2 · · · am = (a1 a2 · · · ami )m/mi . All states on the path P except for q1 are
new and also all states qmi +1 , . . . , qm are new. If q1 is the initial state of A then q1′
is the new initial state. Otherwise, the unique transition entering C is redirected
to the new state q1′ . The union of the languages recognized by all automata of this
form is L(A).

Lemma 5.11. Let A be a linear cycle automaton in which each non-trivial cycle
has the same length. Then L(A) is a Boolean combination of regular right ideals
and regular length-languages.
Proof. Let L ⊆ Σ∗ be the language recognized by A. There are numbers p, q ≥ 0
such that each word in L has length p + qn for some n ≥ 0. Here q is the uniform
length of the non-trivial cycles in A. We claim that L is the intersection of the
three languages
• LΣ∗ , which is a regular right ideal,
• {x ∈ Σ∗ : Pref(x) ⊆ Pref(L)}, which is the complement of a regular right
ideal,
• Σp (Σq )∗ , which is a length language.

AUTOMATA THEORY ON SLIDING WINDOWS

2
0

0
0

1

1
0

15

t>s
2

2

···

0, 1

s
t<s

t

···

k
0, . . . , k − 1

Figure 1. An automaton for Lk . Omitted transitions lead to a
sink state. All states are final, except from the sink state.
Clearly L is contained in the described intersection. Conversely, consider a word x
in the intersection. We have x = yz where y ∈ L. Hence, |y| = p + qn for some n.
Since |x| = p + qn′ for some n′ , the length |z| is divided by q. Since y ∈ L, A(y) is
the unique final state of A, which belongs to the unique maximal SCC C of A. If
C is non-trivial, then it is a cycle of length q and also A(yz) is the final state, i.e.,
x ∈ L. If C is trivial, then y, yz ∈ L implies z = ε and x is also accepted by A. 
This concludes the proof for the direction from 4. to 5.
5.2. Lower bounds. Recall that the space bound in Theorem 5.2 is exponential
in the number m of automaton states. In the following we show that this bound
is tight, already for the fixed-size sliding window model. For k ≥ 0 we define the
language Lk ⊆ {0, . . . , k}∗ by
• L0 = 0+ , and
• Lk = Lk−1 ∪ Lk−1 k {0, . . . , k − 1}∗ for k ≥ 1.

Observe that a word a1 · · · an ∈ {0, . . . , k}∗ belongs to Lk if and only if n ≥ 1,
a1 = 0 and for each 1 ≤ i ≤ n it holds that ai = 0 or ai 6= max1≤j≤i−1 aj . We
can construct a DFA Ak for Lk with k + 3 states, which stores the maximum value
seen so far in its state, see Fig. 1.
To prove that each Lk belongs to V(O(log n)), we show that Lk is a Boolean
combination of regular left ideals. Given a word x = a1 · · · an ∈ Σ∗ and a language
L ⊆ Σ∗ , a position 1 ≤ i ≤ n is an L-alternation point, if exactly one of the
words ai · · · an and ai+1 · · · an belongs to L. Denote by altL (x) the number of
L-alternation points in x.
Lemma 5.12. Let L ⊆ Σ∗ be regular. Then L is a Boolean combination of at most
k regular left ideals if and only if altL (x) ≤ k for all x ∈ Σ∗ .
Proof. If L is a Boolean combination of regular left ideals L1 , . . . , Lk , then each
L-alternation point in a word is an Li -alternation point for some 1 ≤ i ≤ k. Since
Li is a left ideal, each word has at most one Li -alternating point and we obtain
altL (x) ≤ k for all x ∈ Σ∗ .
Conversely, assume that altL (x) ≤ k for all x ∈ Σ∗ . Without loss of generality
assume ε ∈ L, which ensures that x ∈ L if and only if altL (x) is even. If ε 6∈ L,
then x ∈ L if and only if altL (x) is odd, and we can argue similarly as below.
We define Pi = {x ∈ Σ∗ : altL (x) ≥ i} for i ≥ 0 and write L as
[
L=
(Pi \ Pi+1 ).
0≤i≤k even

Each Pi is a left ideal because prolonging a word on the left only increases the
number of L-alternation points. Furthermore, each Pi is regular: by enriching a
DFA for L with a counter up to i, a DFA can verify that the input x satisfies
altL (x) ≥ i. Using the fact that P0 = Σ∗ and Pi = ∅ for all i > k, we can write L

16

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

as
L=

(

(Σ∗ \ P1 ) ∪ (P2 \ P3 ) ∪ · · · ∪ (Pk−2 \ Pk−1 ) ∪ Pk , if k is even
(Σ∗ \ P1 ) ∪ (P2 \ P3 ) ∪ · · · ∪ (Pk−1 \ Pk ),
if k is odd.

This proves that L is a Boolean combination of the regular left ideals P1 , . . . , Pk ,
which concludes the proof.

Lemma 5.13. For all k ≥ 0 and x ∈ N∗ we have altLk (x) ≤ 2k+2 − 2. Moreover,
VLk (n) ≤ (2k+3 · (k + 3) + 1) · log n + ck for n large enough, where ck only depends
on k.
Proof. We prove the lemma by induction on k ≥ 0. Clearly each word has at most
2 alternation points with respect to L0 = 0+ . Now let k ≥ 1 and x ∈ N∗ . If all
occurring numbers in x are at most k − 1, then altLk (x) = altLk−1 (x) and the claim
follows by induction. Otherwise consider the last occurrence of a number ≥ k and
factorize x = yℓz where y ∈ N∗ , ℓ ≥ k and z ∈ {0, . . . , k − 1}∗ . If ℓ > k, then the
first |y| positions of x cannot contain Lk -alternation points and we get
altLk (x) ≤ 1 + altLk (z) = 1 + altLk−1 (z) ≤ 2k+1 − 1 ≤ 2k+2 − 2.

Now assume x = ykz. By the definition of Lk each Lk -alternation point in x is
either (i) an Lk−1 -alternation point in y, (ii) an Lk−1 -alternation point in z, or (iii)
position |y| + 1 (i.e., the last position, where k occurs). Hence we have
altLk (x) ≤ 1 + altLk−1 (y) + altLk−1 (z) ≤ 1 + (2k+1 − 2) + (2k+1 − 2) ≤ 2k+2 − 2.

From Theorems 5.2 and 5.5 and Lemma 5.12 we obtain VLk (n) ≤ (2k+3 · (k + 3) +
1) · log n + ck for n large enough, where ck only depends on k.

Theorem 5.14. For each k ≥ 1 there exists a language Lk ⊆ {0, . . . , k}∗ recognized
by a DFA with k + 3 states such that FLk (n) ≥ (2k − 1) · log n − c′k , where c′k only
depends on k.
Proof. Of course, we take the languages Lk considered in this section. We define
the languages Z0 = 0∗ and Zk = Zk−1 k Zk−1 for k ≥ 1. An example word from
Z3 is 0010002100300010020010. The crucial fact about words x ∈ Zk that we are
using is the following: Every suffix of x that starts with 0 belongs to Lk and every
suffix of x that starts with a > 0 does not belong to Lk . The former follows by
induction on k; the latter holds since words in Lk start with 0.
Fix some k ≥ 1 and let B = (Bn )n≥0 be a fixed-size sliding window algorithm
for Lk where Sn is the state space
 of Bn . Let us consider window size n. We claim
that Bn distinguishes all 2kn−1 words in Zk of length n.

Claim. Let x, y ∈ Zk such that |x| = |y| = n and x 6= y. Then Bn (x) 6= Bn (y).

In order to get a contradiction, consider two words x, y ∈ Zk with |x| = |y| = n,
x 6= y, and Bn (x) = Bn (y). Thus, we can write x = zau and y = zbv with
a, b ∈ {0, . . . , k}, a 6= b. We must have a = 0 and b > 0 or vice versa. Assume
that a = 0 and b > 0. Thus, au ∈ Lk and bv 6∈ Lk . Hence, we have wnd(x0|z| ) =
au0|z| ∈ Lk and wnd(y0|z| ) = bv0|z| 6∈ Lk . But if Bn (x) = Bn (y), then also
Bn (x0|z| ) = Bn (y0|z| ), which yields a contradiction.

The above claim implies that Bn has at least 2kn−1 many states. Hence, the space
complexity of B is at least
2k −1
 2k −1



n
n
n
≥
log
= (2k − 1) · (log n − k).
log k
≥ log
2k − 1
2k
2 −1
This concludes the proof.



AUTOMATA THEORY ON SLIDING WINDOWS

17

6. Constant space algorithms
Theorem 4.1 implies that VL (n) ≥ log n if ∅ 6= L 6= Σ∗ . Thus, only trivial
languages have a constant-space variable-size streaming algorithm. This changes
in the fixed-size window model. In [22] we characterized those regular languages L
in F(O(1)) in terms of the left Cayley graph of the syntactic monoid of L. Here we
give a more natural characterization that will be used in the next section.
A language L ⊆ Σ∗ is called k-suffix testable if for all x, y ∈ Σ∗ and z ∈ Σk we
have
xz ∈ L ⇐⇒ yz ∈ L.
Equivalently, L is a Boolean combination of languages of the form Σ∗ w where w ∈
Σ≤k . We call L suffix testable if it is k-suffix testable for some k ≥ 0. Clearly, every
finite language is suffix testable: if L ⊆ Σ≤k then L is (k + 1)-suffix testable. The
class of suffix testable languages corresponds to the variety D of definite monoids
[39].
Recall the languages
(2)

Ln := {w ∈ Σ∗ : lastn (w) ∈ L}

recognized by a family of streaming algorithms in the fixed-size model. The main
result of this section is:
Theorem 6.1. A regular language L ⊆ Σ∗ belongs to F(O(1)) if and only if L is a
finite Boolean combination of suffix testable languages and regular length languages.
The following definitions are useful, which are also studied in [23]. For two
languages K, L ⊆ Σ∗ , we denote by K△L = (K \ L) ∪ (L \ K) the symmetric
difference of K and L. We define the distance d(K, L) by
(
sup{|u| : u ∈ K△L} + 1, if K 6= L,
d(K, L) =
0,
if K = L.
Notice that d(K, L) < ∞ if and only if K△L is finite. For a DFA A = (Q, Σ, q0 , δ, F )
and a state p ∈ Q, we define Ap = (Q, Σ, p, δ, F ). For two states p, q ∈ Q, we define
the distance d(p, q) = d(L(Ap ), L(Aq )). It is known that d(p, q) < ∞ implies
d(p, q) ≤ |Q|, see [23, Lemma 1].

Lemma 6.2. Let L ⊆ Σ∗ be regular and A = (Q, Σ, q0 , δ, F ) be its minimal DFA.
We have:
(i) d(p, q) ≤ k if and only if δ(p, z) = δ(q, z) for all p, q ∈ Q and z ∈ Σk .
(ii) L is k-suffix testable if and only if d(p, q) ≤ k for all p, q ∈ Q.
(iii) If there exists k ≥ 0 such that L is k-suffix testable, then L is |Q|-testable.

Proof. The proof of (i) is an easy induction: If k = 0, the statement is d(p, q) = 0
iff p = q, which is true because A is minimal. For the induction step, we have
d(p, q) ≤ k + 1 iff d(δ(p, a), δ(q, a)) ≤ k for all a ∈ Σ iff δ(p, z) = δ(q, z) for all
z ∈ Σk+1 .
For (ii), assume that L is k-suffix testable and consider two states p = A(x) and
q = A(y). If z ∈ L(Ap )△L(Aq ), then |z| < k because xz ∈ L iff yz ∈
/ L and L is
k-suffix testable.
Now assume that d(p, q) ≤ k for all p, q ∈ Q and consider x, y ∈ Σ∗ , z ∈ Σk .
Since d(A(x), A(y)) ≤ k, (i) implies A(xz) = A(yz), and in particular xz ∈ L iff
yz ∈ L. Therefore, L is k-suffix testable.
Point (iii) follows from (ii) and the above mentioned results from [23, Lemma 1].


Theorem 6.3. For any L ⊆ Σ∗ and n ≥ 0, the language Ln from (2) is (2FL (n)+1 −
1)-suffix testable.

18

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

Proof. Let (An )n≥0 be an optimal fixed-size sliding window algorithm for L where
An = (Sn , Σ, sn , δn , Fn ), which is the minimal DFA for Ln . For every n, the
language Ln is n-suffix testable because
Ln = {w ∈ Σ≤n−1 : lastn (w) ∈ L} ∪ Σ∗ (L ∩ Σn ).
By Lemma 6.2(iii) every language Ln is |Sn |-suffix testable. Together with FL (n) =
log |Sn | this proves the claim for Ln .

Corollary 6.4. A language L ⊆ Σ∗ belongs to F(O(1)) if and only if there exists
a k ≥ 0 such that Ln is k-suffix testable for all n ≥ 0.
Proof. The left-to-right direction follows from Theorem 6.3. If each Ln is k-suffix
testable, then the streaming algorithm for window length n only needs to maintain
the last k symbols to test membership of a word of length n in Ln , or equivalently
in L.

Proof of Theorem 6.1. First, let L ⊆ Σ∗ be a regular language in F(O(1)). By
Theorem 6.3 there exists k ≥ 0 such that Ln is k-suffix testable for all n ≥ 0. We
write L as the Boolean combination
[
[
((Lz −1 ) Σk ∩ Σ∗ z)
(Lz −1 ) z = (L ∩ Σ≤k−1 ) ∪
L = (L ∩ Σ≤k−1 ) ∪
z∈Σk

−1

z∈Σk

∗

where Lz = {x ∈ Σ : xz ∈ L} is the regular right quotient of L by z. The set
L ∩ Σ≤k−1 is finite and hence suffix testable. It remains to show that each Lz −1 is
a length language. Consider two words x, y ∈ Σ∗ of the same length |x| = |y| = n.
Since |xz| = |yz| = n + k and Ln+k is k-suffix testable we have xz ∈ L iff yz ∈ L,
and hence x ∈ Lz −1 iff y ∈ Lz −1 .
For the other direction note that:
• if L is a length language or suffix testable language then clearly L ∈ F(O(1)),
and
• F(O(1)) is closed under Boolean operations by Lemma 3.2.
This proves the theorem.

We give another characterization of the regular languages in F(O(1)), which
yields a decision procedure in the next section.
Proposition 6.5. Let L ⊆ Σ∗ be regular and A = (Q, Σ, q0 , δ, F ) be its minimal
DFA. Then L ∈ F(O(1)) if and only if for all x, y ∈ Σ∗ with |x| = |y| and z ∈ Σ|Q|
we have A(xz) = A(yz).
Proof. Assume that L ∈ F(O(1)). By Corollary 6.4 there exists k ≥ 0 such that
each Ln is k-suffix testable. Let x, y ∈ Σ∗ with |x| = |y| = n. For all z ∈ Σk we have
xz ∈ Ln+k iff yz ∈ Ln+k . Thus, xz ∈ L iff yz ∈ L and hence d(A(x), A(y)) ≤ k.
This implies d(A(x), A(y)) ≤ |Q|. By Lemma 6.2(i) we have A(xz) = A(yz) for all
z ∈ Σ|Q| .
Conversely, assume that A(xz) = A(yz) for all x, y ∈ Σ∗ with |x| = |y| and
z ∈ Σ|Q| . This means that one can simulate the automaton on the active window
by only storing the last |Q| many symbols and hence in space O(1).

7. Deciding space complexity in the sliding window model
In this section, we consider the complexity of the following decision problems:
• Dfa(1): Given a DFA A, does L(A) ∈ F(O(1)) hold?
• Nfa(1): Given an NFA A, does L(A) ∈ F(O(1)) hold?
• Dfa(log n): Given a DFA A, does L(A) ∈ F(O(log n)) = V(O(log n)) hold?

AUTOMATA THEORY ON SLIDING WINDOWS

19

• Nfa(log n): Given an NFA A, does L(A) ∈ F(O(log n)) = V(O(log n))
hold?
It is straightforward to show that membership in V(O(1)) for a regular language that
is given by a DFA (resp., an NFA) is NL-complete (resp., Pspace-complete): By
Theorem 3.4 one has to check whether L(A) = ∅ or L(A) = Σ∗ , and universality for
DFAs (resp., NFAs) is NL-complete (resp., Pspace-complete). In Section 7.1 (resp.,
Section 7.2) we show that Dfa(1) and Dfa(log n) (resp., Nfa(1) and Nfa(log n))
are NL-complete (resp., Pspace-complete).
7.1. The DFA case. We start with the NL-hardness for the DFA case:
Theorem 7.1. Dfa(1) and Dfa(log n) are NL-hard.
Proof. We reduce from the NL-complete reachability problem in finite directed
graphs. Given a finite directed graph G = (V, E) and two vertices s, t ∈ V , the
question is whether there exists a path from s to t. We can assume that s 6= t
and that each vertex v ∈ V has exactly two successors va , vb ∈ V . Let A =
(V ∪ {⊥}, {a, b, c}, s, δ, {t}) be a DFA where


vx if v ∈ V \ {t}, x ∈ {a, b},
δ(v, x) = t
if v = t, x ∈ {a, b, c},


⊥ otherwise.

Since s 6= t, we can write L(A) as K {a, b, c}∗ for some K ⊆ {a, b}+. Furthermore,
there exists a path from s to t in G if and only if K 6= ∅. If K = ∅, then L(A) = ∅
belongs to F(O(1)) and to V(O(log n)). If K 6= ∅, then we claim that L(A) =
K {a, b, c}∗ does not belong to V(O(log n)). Consider a variable-size sliding window
algorithm M for L(A). Fix an arbitrary word x ∈ K and let k = |x|. Moreover, let
n ≥ 0 and consider the set {x, ck }n of size 2n . Let us read two distinct words from
{x, ck }n into two instances of M. We can write these words as uxw and vck w for
some u, v, w ∈ {a, b, c}∗ with |u| = |v|. By removing the first |u| = |v| many symbols
from the window, we obtain the active windows xw ∈ L(A) and ck w ∈
/ L(A) and
therefore M(uxw) 6= M(vck w). Hence, M must contain at least 2n many states
that are reachable by words of length kn. This implies that L(A) ∈
/ V(o(n)).


Theorem 7.2. Dfa(1) is NL-complete.
Proof. Let us first assume that the input DFA A is minimal. Later, we will argue
how to handle the general case. Since nondeterministic logspace is closed under
complement, it suffices to decide whether L(A) ∈
/ F(O(1)). By Proposition 6.5
this is the case if and only if there exist words x, y, z ∈ Σ∗ such that |x| = |y|,
|z| = |Q| and A(xz) 6= A(yz). The existence of such words can be easily verified in
nondeterministic logspace: One simulates A on two words of the same length (the
words x, y), and thereby only stores the current state pair. At every time instant,
the algorithm can nondeterministically decide to continue the simulation from the
current state pair (p, q) with a single word (the word z) for |Q| steps. The algorithm
accepts if at the end the two states are distinct.
The general case, where A is not minimal is handled as follows: Assume that
A = ({1, . . . , k}, Σ, 1, δ, F ) is the input DFA. It is known that DFA equivalence is
in NL[12]. Hence, one can test in nondeterministic logspace, whether two states
p, q ∈ Q are equivalent (in the sense that δ(p, w) ∈ F iff δ(q, w) ∈ F for all w ∈ Σ∗ ).
We will use this problem as an NL-oracle in the above NL-algorithm for minimal
DFAs. More precisely, let A′ = (Q, Σ, 1, δ ′ , F ′ ) be the minimal DFA for A, where
we assume that Q is the set of all states q ∈ {1, . . . , k} such that there is no state
p < q that is equivalent to q. We run the NL-algorithm above for minimal DFAs
on A′ without explicitly constructing A′ . If we have to compute a successor state

20

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

δ ′ (q, a) (where q ∈ Q) we compute, using the above NL-oracle the smallest state
that is equivalent to δ(q, a).
The above argument shows that Dfa(1) belongs to NLNL . Finally, we use the
well-known identity NL = NLNL [26].

In the rest of the section, we show that one can also decide in nondeterministic
logspace whether L ∈ V(O(log n)) (or equivalently L ∈ F(O(log n))). As in the
proof of Theorem 7.2 we can assume that L is given by its minimal DFA A.
For words u, x0 , x1 ∈ Σ∗ we define
Q(u, x0 , x1 ) = {A(ux) : x ∈ {x0 , x1 }∗ },

which is the set of states of A reachable from the initial state by first reading u and
then an arbitrary product of copies of x0 and x1 .
Lemma 7.3. We have VL (n) ∈ Θ(n) if and only if there are words u0 , u1 , v0 , v1 ∈
Σ∗ such that |u0 | = |u1 | ≥ 1 and Q(u0 , v0 u0 , v1 u1 ) ∩ Q(u1 , v0 u0 , v1 u1 ) = ∅.
Proof. Let B be the minimal DFA for LR . If VL ∈ Θ(n), then B is not well-behaved,
i.e., there are words u, u0 , u1 , v0 , v1 ∈ Σ∗ such that

• |u0 | = |u1 |,
• B(uu0v0 ) = B(u) = B(uu1v1 ),
• B(uu0) ∈
/ F and B(uu1 ) ∈ F (and thus u0 , u1 ∈ Σ+ ).
Setting K = {u0 v0 , u1 v1 }∗ we get uKu0 ∩ LR = ∅ and uKu1 ⊆ LR . Hence for
all w0 ∈ uR0 K R and w1 ∈ uR1 K R we have w0 6∼L w1 . Since A is minimal, this
implies {A(w) : w ∈ uR0 K R } ∩ {A(w) : w ∈ uR1 K R } = ∅, i.e., Q(uR0 , v0R uR0 , v1R uR1 ) ∩
Q(uR1 , v0R uR0 , v1R uR1 ) = ∅.
Next, assume that Q(u0 , v0 u0 , v1 u1 ) ∩ Q(u1 , v0 u0 , v1 u1 ) = ∅ and |u0 | = |u1 | ≥ 1
for words u0 , u1 , v0 , v1 . We clearly have u0 6= u1 and hence v0 u0 6= v1 u1 . Further,
we can choose numbers p, q ≥ 1 such that (v0 u0 )p and (v1 u1 )q have the same length.
We redefine v0 to be (v0 u0 )p−1 v0 and v1 to be (v1 u1 )q−1 v1 . Thus, |v0 u0 | = |v1 u1 |.
Moreover, the new resulting sets Q(ui , v0 u0 , v1 u1 ) are contained in the original sets,
and are therefore also disjoint. Let c = |v0 u0 | = |v1 u1 | ≥ 1.
Now consider a variable-size sliding window algorithm M for L and let n be
arbitrary. We claim that for all w0 , w1 ∈ {v0 u0 , v1 u1 }n with w0 6= w1 , we have
M(w0 ) 6= M(w1 ). This is because after removing a suitable number of symbols,
the active windows contain words x0 ∈ u0 {v0 u0 , v1 u1 }∗ and x1 ∈ u1 {v0 u0 , v1 u1 }∗ ,
respectively. By assumption, reading x0 and x1 in the minimal DFA A leads to
different states. Hence there exists a word z ∈ Σ∗ such that x0 z ∈ L if and only if
x1 z ∈
/ L. Thus, we must have M(x0 ) 6= M(x1 ) and therefore M(w0 ) 6= M(w1 ).
Since {v0 u0 , v1 u1 }n consists of 2n many words, there exists w ∈ {v0 u0 , v1 u1 }n
such that the encoding of M(w) has length at least n. Since |w| = cn, we have
VL (n) ≥ ⌊n/c⌋.

We call a tuple (u0 , u1 , w0 , w1 ) of words critical, if |u0 | = |u1 | ≥ 1, ui is a suffix
of wi for all i ∈ {0, 1} and Q(u0 , w0 , w1 ) ∩ Q(u1 , w0 , w1 ) = ∅. Clearly, the condition
from Lemma 7.3 is equivalent to the existence of a critical tuple.
Lemma 7.4. If there exists a critical tuple, then there exists a critical tuple (u0 , u1 , w0 , w1 )
such that Q(u0 , w0 , w1 ) and Q(u1 , w0 , w1 ) have each size at most three.
Proof. Let h : Σ∗ → M be the canonical homomorphism into the transition monoid
M of A, which right acts on Q via Q × M → Q, (q, m) 7→ q · m = m(q). Assume
that (u0 , u1 , w0 , w1 ) is a critical tuple. Notice that
Q(ui , w0 , w1 ) = {A(ui ) · m : m ∈ {h(w0 ), h(w1 )}∗ }

AUTOMATA THEORY ON SLIDING WINDOWS

p0

w0

w0
p
u0

w0
w1

w0

u1

w1
p1

w1

r0

w0

w0

r
w1

21

w1
r1

w1

Figure 2. A critical tuple (u0 , u1 , w0 , w1 ).
where X ∗ denotes the submonoid of M generated by a set X ⊆ M . It suffices to
define a new critical tuple (u0 , u1 , x0 , x1 ) with the property that h(xi )·h(xj ) = h(xj )
for all i, j ∈ {0, 1}. This implies {h(x0 ), h(x1 )}∗ = {1, h(x0 ), h(x1 )}, and hence,
Q(ui , x0 , x1 ) contains at most three elements for both i ∈ {0, 1}.
Notice that if (u0 , u1 , w0 , w1 ) is critical, then also (u0 , u1 , y0 w0 , y1 w1 ) is critical
for all y0 , y1 ∈ {w0 , w1 }∗ . Let ω ≥ 1 be a number such that mω is idempotent for
all m ∈ M . By choosing e0 = (h(w0 )ω h(w1 )ω )ω h(w0 )ω and e1 = (h(w0 )ω h(w1 )ω )ω
we indeed obtain ei ej = ej for all i, j ∈ {0, 1}. Hence we define x0 = (w0ω w1ω )ω w0ω
and x1 = (w0ω w1ω )ω .

Lemma 7.5. Given a minimal DFA A, one can test in nondeterministic logspace
whether A has a critical tuple.
Proof. Let A = (Q, Σ, q0 , δ, F ) be a minimal DFA. Fig. 2 illustrates the structure
we need to detect in A. To do so, we reduce to testing emptiness of one-counter
automata, which is known to be decidable in nondeterministic logspace [30]. For
two states p, r ∈ Q let Ap,r = (Q, Σ, p, δ, {r}), i.e., the automaton A with initial
state p and final state r, and let L(p, r) = L(Ap,r ).
The algorithm iterates over all disjoint sets {p, p0 , p1 }, {r, r0 , r1 } ⊆ Q. For i ∈
{0, 1} let Ai be a DFA for the language
L(p, pi ) ∩ L(p0 , pi ) ∩ L(p1 , pi ) ∩ L(r, ri ) ∩ L(r0 , ri ) ∩ L(r1 , ri ).

Now consider the language

{v0 # u0 # v1 # u1 : vi ui ∈ L(Ai ) for i ∈ {0, 1}, |u0 | = |u1 | ≥ 1,
u0 ∈ L(q0 , p), u1 ∈ L(q0 , r)}

for which one can construct in logspace a one-counter automaton. The counter is
used to verify the constraint |u0 | = |u1 |. The language above is empty if and only
if A has a critical tuple.

Lemma 7.3, Lemma 7.5 and Theorem 3.4 together imply:
Corollary 7.6. Dfa(log n) is NL-complete.
7.2. The NFA case. In this section, we show that the problems Nfa(1) and
Nfa(log n) are both Pspace-complete. The upper bounds follow easily from Theorem 7.2
and Corollary 7.6 and the following fact (see [31, Lemma 1]): If a mapping f can
be computed by a Turing-machine with a polynomially bounded work tape (the
output can be of exponential size) and L is a language that can be decided in polylogarithmic space, then f −1 (L) belongs to Pspace. Note that from a given NFA A

22

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

one can compute an equivalent DFA using polynomially bounded work space: One
iterates over all subsets of the state set of A; the current subset is stored on the
work tape. For every subset and input symbol one then writes the corresponding
transition of the DFA on the output tape.
Theorem 7.7. Nfa(1) is Pspace-complete.
Proof. By the above remark it suffices to establish Pspace-hardness of Nfa(1). For
this we will reduce the NFA universality problem to Nfa(1). The NFA universality
problem is Pspace-complete [2]. W.l.o.g. consider the alphabet Σ = {a, b}. For an
NFA A = (Q, Σ, I, ∆, F ) we define ρ(A) to be the automaton that results from A
by adding a new initial state q̄ with an a-labeled self-loop and a b-labeled transition
from every state of F to q̄. The only final state of ρ(A) is q̄. More formally, we
define ρ(A) as follows:
ρ(A) = (Q ∪ {q̄}, Σ, I ∪ {q̄}, ∆ ∪ {(q, b, q̄) | q ∈ F } ∪ {(q̄, a, q̄)}, {q̄}).

Notice that the ρ-construction implies L(ρ(A)) = a∗ ∪ L(A) b a∗ . It is then easy
to verify that L(A) = Σ∗ iff L(ρ(A)) = Σ∗ . If L(A) = Σ∗ then clearly L(ρ(A)) =
Σ∗ ∈ F (1). Conversely, assume that L(ρ(A)) = a∗ ∪ L(A) b a∗ belongs to F (1). By
Theorem 6.1 there exists a number k ∈ N such that a∗ ∪ L(A) b a∗ is a Boolean
combination of k-suffix testable languages and regular length languages. Let x ∈
{a, b}n be any word of length n. Since an+1+k ∈ L(ρ(A)) and xbak share the same
k-suffix and are of the same length, we also know that xbak ∈ L(ρ(A)) and hence
x ∈ L(A). This proves that A is universal.
We have thus established that the polynomial-time (in fact, log-space) construction A 7→ ρ(A) reduces the universality problem for NFAs to Nfa(1).

Theorem 7.8. Nfa(log n) is Pspace-complete.
Proof. It remains to show that Nfa(log n) is Pspace-hard, which can be shown
by reducing the NFA universality problem to Nfa(log n). W.l.o.g. the alphabet of
the input automaton is Σ = {a, b}, and we also consider the extended alphabet
Γ = {a, b, c}. For an NFA A = (Q, Σ, I, ∆, F ) we define ρ(A) to be the automaton
that results from A by adding a new initial and final state q̄ with a- and b-labeled
self-loops, a c-labeled transition from every state of F to q̄, and a c-labeled transition
from q̄ to every state of A. The only final state of ρ(A) is q̄. More formally, we
define
ρ(A) = (Q ∪ {q̄}, Γ, I ∪ {q̄}, ρ(∆), {q̄}), where

ρ(∆) = ∆ ∪ {(q, c, q̄) | q ∈ F } ∪ {(q̄, c, q) | q ∈ Q} ∪ {(q̄, x, q̄) | x ∈ {a, b}}.
The automaton σ(A) results from A be adding a new initial and final state q̄ with
a- and b-labeled self-loops, a c-labeled transition from q̄ to each initial state of A,
and a c-labeled transition from every state of A to q̄. The only initial state of σ(A)
is q̄. More formally, we define σ(A) as follows:
σ(A) = (Q ∪ {q̄}, Γ, {q̄}, σ(∆), F ∪ {q̄}), where

σ(∆) = ∆ ∪ {(q̄, c, q) | q ∈ I} ∪ {(q, c, q̄) | q ∈ Q} ∪ {(q̄, x, q̄) | x ∈ {a, b}}.
Then, we have ρ(A)R = σ(AR ), which is also equal to
ρ(A)R = (Q ∪ {q̄}, Γ, {q̄}, ρ(∆)R , I ∪ {q̄}) with

ρ(∆)R = ∆R ∪ {(q̄, c, q) | q ∈ F } ∪ {(q, c, q̄) | q ∈ Q} ∪ {(q̄, x, q̄) | x ∈ {a, b}}.
Notice that for a deterministic A (over the alphabet Σ), the automaton σ(A) (over
the alphabet Γ) is also deterministic. For a nondeterministic automaton A that
satisfies additionally the condition that the state ∅ is not reachable from the initial

AUTOMATA THEORY ON SLIDING WINDOWS

23

state of AD (that is, AD does not have the state ∅), we have that σ(A)D ∼
= σ(AD )
(identifying q̄ with {q̄}). So,
σ(ARD ) ∼
= σ(AR )D = ρ(A)RD

under the previously mentioned condition for AR , which can be satisfied w.l.o.g.
by adding an initial non-final state to AR with a- and b-labeled self-loops (that is,
by adding a final non-initial state to A with a- and b-labeled self-loops). So, for a
nondeterministic automaton A the claim is:
L(A) = Σ∗

⇔

L(ARD ) = Σ∗

⇔
⇔

the DFA σ(ARD ) ∼
= ρ(A)RD is well-behaved
L(ρ(A)) ∈ V(O(log n)).

⇔

L(σ(ARD )) = Γ∗

The proof of the third equivalence uses the fact that σ(ARD ) consists of a single SCC.
The left-to-right direction is immediate. For the right-to-left direction, observe that
the initial and final state q̄ of the DFA σ(ARD ) has a- and b-labeled self-loops, i.e.,
Σ∗ ⊆ L(σ(ARD )). Thus, for every n there is a word of length n that is accepted from
the initial state q̄. But σ(ARD ) is well-behaved, which implies that all strings of
any length must be accepted from q̄, i.e., L(σ(ARD )) = Γ∗ . So, we have established
that the polynomial-time (in fact, log-space) construction A 7→ ρ(A) reduces the
universality problem for NFAs to Nfa(log n).

References
[1] Charu C. Aggarwal. Data Streams - Models and Algorithms. Springer, 2007.
[2] Albert R. Meyer and Larry J. Stockmeyer. The Equivalence Problem for Regular Expressions
with Squaring Requires Exponential Space. In 13th Annual Symposium on Switching and
Automata Theory, College Park, Maryland, USA, October 25-27, 1972, pages 125–129, 1972.
[3] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the
frequency moments. J. Comput. Syst. Sci., 58(1):137–147, 1999.
[4] Arvind Arasu and Gurmeet Singh Manku. Approximate counts and quantiles over sliding
windows. In Proceedings of PODS 2004, pages 286–296. ACM, 2004.
[5] Brian Babcock, Mayur Datar, Rajeev Motwani, and Liadan O’Callaghan. Maintaining variance and k-medians over data stream windows. In Proceedings of PODS 2003, pages 234–243.
ACM, 2003.
[6] Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma. Streaming algorithms for language recognition problems. Theoretical Computer Science, 494:13–23, 2013.
[7] Ajesh Babu, Nutan Limaye, and Girish Varma. Streaming algorithms for some problems
in log-space. In Proceedings of the 7th Annual Conference on Theory and Applications of
Models of Computation, TAMC 2010, volume 6108 of Lecture Notes in Computer Science,
pages 94–104. Springer, 2010.
[8] Vladimir Braverman. Sliding window algorithms. In Encyclopedia of Algorithms, pages 2006–
2011. Springer, 2016.
[9] Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science FOCS
2007, pages 283–293. IEEE Computer Society, 2007.
[10] Vladimir Braverman, Rafail Ostrovsky, and Carlo Zaniolo. Optimal sampling from sliding
windows. J. Comput. Syst. Sci., 78(1):260–272, 2012.
[11] Dany Breslauer and Zvi Galil. Real-time streaming string-matching. ACM Trans. Algorithms,
10(4):22:1–22:12, 2014.
[12] Sang Cho and Dung T. Huynh. The parallel complexity of finite-state automata problems.
Information and Computation, 97(1):1–22, 1992.
[13] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana A. Starikovskaya.
Dictionary matching in a stream. In Proceedings of ESA 2015, volume 9294 of Lecture Notes
in Computer Science, pages 361–372. Springer, 2015.
[14] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana A. Starikovskaya.
The k -mismatch problem revisited. In Proceedings of SODA 2016, pages 2039–2052. SIAM,
2016.

24

M. GANARDI, D. HUCKE, D. KÖNIG, M. LOHREY, AND K. MAMOURAS

[15] Raphaël Clifford and Tatiana A. Starikovskaya. Approximate hamming distance in a stream.
In Proceedings of ICALP 2016, volume 55 of LIPIcs, pages 20:1–20:14. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2016.
[16] Michael S. Crouch, Andrew McGregor, and Daniel Stubbs. Dynamic graphs in the slidingwindow model. In Proceedings of ESA 2013, volume 8125 of Lecture Notes in Computer
Science, pages 337–348. Springer, 2013.
[17] Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM J. Comput., 31(6):1794–1813, 2002.
[18] A. Policriti F. Parlamento and K. Rao. Witnessing differences without redundancies. Proceedings of the American Mathematical Society, 125(2):587–594, 1997.
[19] Nathanaël Fijalkow. The online space complexity of probabilistic languages. In Proceedings
of the International Symposium on Logical Foundations of Computer Science, LFCS 2016,
volume 9537 of Lecture Notes in Computer Science, pages 106–116. Springer, 2016.
[20] Philippe Flajolet and G. Nigel Martin. Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci., 31(2):182–209, 1985.
[21] Nathanaël François, Frédéric Magniez, Michel de Rougemont, and Olivier Serre. Streaming
property testing of visibly pushdown languages. In Proceedings of the 24th Annual European Symposium on Algorithms, ESA 2016, volume 57 of LIPIcs, pages 43:1–43:17. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
[22] Moses Ganardi, Danny Hucke, and Markus Lohrey. Querying regular languages over sliding
windows. In Proceedings of FSTTCS 2016, volume 65 of LIPIcs, pages 18:1–18:14. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
[23] Pawel Gawrychowski and Artur Jez. Hyper-minimisation Made Efficient. In Proceedings of the
34th International Symposium on Mathematical Foundations of Computer Science, MFCS
2009, volume 5734 of Lecture Notes in Computer Science, pages 356–368. Springer, 2009.
[24] Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, and Jeffrey Shallit. Finding the
growth rate of a regular or context-free language in polynomial time. International Journal
on Foundations of Computer Science, 21(4):597–618, 2010.
[25] Lukasz Golab and M. Tamer Özsu. Processing sliding window multi-joins in continuous
queries over data streams. In Proceedings of VLDB 2003, pages 500–511. Morgan Kaufmann,
2003.
[26] Neil Immerman. Nondeterministic space is closed under complementation. SIAM Journal on
Computing, 17(5):935–938, 1988.
[27] Richard M. Karp. Some bounds on the storage requirements of sequential machines and turing
machines. J. ACM, 14(3):478–489, 1967.
[28] Christian Konrad and Frédéric Magniez. Validating XML documents in the streaming model
with external memory. ACM Trans. Database Syst., 38(4):27:1–27:36, 2013.
[29] Andreas Krebs, Nutan Limaye, and Srikanth Srinivasan. Streaming algorithms for recognizing
nearly well-parenthesized expressions. In Proceedings of the 36th International Symposium
on Mathematical Foundations of Computer Science, MFCS 2011, volume 6907 of Lecture
Notes in Computer Science, pages 412–423. Springer, 2011.
[30] Michel Latteux. Langages á un compteur. Journal of Computer and System Sciences,
26(1):14–33, 1983.
[31] Markus Lohrey and Christian Mathissen. Isomorphism of regular trees and words. Information and Computation, 224:71–105, 2013.
[32] Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized expressions in the streaming model. SIAM J. Comput., 43(6):1880–1905, 2014.
[33] Philip M. Lewis II, Richard Edwin Stearns, and Juris Hartmanis. Memory bounds for recognition of context-free and context-sensitive languages. In Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, pages 191–202. IEEE Computer
Society, 1965.
[34] J. Ian Munro and Mike Paterson. Selection and sorting with limited storage. Theor. Comput.
Sci., 12:315–323, 1980.
[35] Luc Segoufin and Cristina Sirangelo. Constant-memory validation of streaming XML documents against dtds. In Proceedings of the 11th International Conference on Database Theory,
ICDT 2007, volume 4353 of Lecture Notes in Computer Science, pages 299–313. Springer,
2007.
[36] Luc Segoufin and Victor Vianu. Validating streaming XML documents. In Proceedings of
the 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems,
PODS 2002, pages 53–64. ACM, 2002.
[37] Jeffrey Shallit and Yuri Breitbart. Automaticity I: properties of a measure of descriptional
complexity. J. Comput. Syst. Sci., 53(1):10–25, 1996.

AUTOMATA THEORY ON SLIDING WINDOWS

25

[38] Richard Edwin Stearns, Juris Hartmanis, and Philip M. Lewis II. Hierarchies of memory
limited computations. In Proceedings of the 6th Annual Symposium on Switching Circuit
Theory and Logical Design, pages 179–190. IEEE Computer Society, 1965.
[39] Howard Straubing. Finite semigroup varieties of the form V ∗ D. Journal of Pure and Applied
Algebra, 36:53–94, 1985.
[40] Andrew Szilard, Sheng Yu, Kaizhong Zhang, and Jeffrey Shallit. Characterizing regular languages with polynomial densities. In Proceedings of the 17th International Symposium on
Mathematical Foundations of Computer Science, MFCS 1992, volume 629 of Lecture Notes
in Computer Science, pages 494–503. Springer, 1992.

Universität Siegen, Germany, {ganardi,hucke,koenig,lohrey}@eti.uni-siegen.de
University of Pennsylvania, Philadelphia, USA, mamouras@seas.upenn.edu

