  Low-latency sliding window algorithms for regular and context-free languages
are studied, where latency refers to the worst-case time spent for a single
window update or query. For every regular language $L$ it is shown that there
exists a constant-latency solution that supports adding and removing symbols
independently on both ends of the window (the so-called two-way variable-size
model). We prove that this result extends to all visibly pushdown languages.
For deterministic 1-counter languages we present a $\mathcal{O}(\log n)$
latency sliding window algorithm for the two-way variable-size model where $n$
refers to the window size. We complement these results with a conditional lower
bound: there exists a fixed real-time deterministic context-free language $L$
such that, assuming the OMV (online matrix vector multiplication) conjecture,
there is no sliding window algorithm for $L$ with latency $n^{1/2-\epsilon}$
for any $\epsilon>0$, even in the most restricted sliding window model (one-way
fixed-size model). The above mentioned results all refer to the unit-cost RAM
model with logarithmic word size. For regular languages we also present a
refined picture using word sizes $\mathcal{O}(1)$, $\mathcal{O}(\log\log n)$,
and $\mathcal{O}(\log n)$.

Formal Languages and Automata Theory;Data Structures and Algorithms