论文标题
正式语言的低延迟滑动窗口算法
Low-Latency Sliding Window Algorithms for Formal Languages
论文作者
论文摘要
研究了针对常规语言和无上下文语言的低延迟滑动窗口算法，延迟是指用于单个窗口更新或查询的最差时间。对于每个常规语言$ l $，都表明存在一个恒定的延迟解决方案，该解决方案支持在窗口的两端（所谓的双向可变大小模型）上独立添加和删除符号。我们证明该结果扩展到所有明显的下降语言。对于确定性的1个点语言，我们提供了一个$ \ Mathcal {o}（\ log n）$延迟滑动窗口算法的双向变量尺寸模型，其中$ n $是指窗口大小。我们将这些结果与条件下限进行补充：存在固定的实时确定性无上下文的语言$ l $，因此，假设OMV（在线矩阵矢量乘法）cosienture，则没有延迟的$ l $ for latenency $ n^{1/2-ε} $的$ l $ for任何$>> 0 $ $ε> $ sling sling window（一个限制窗口）的滑动窗口算法。上述结果均指对数单词大小的单位成本RAM模型。对于普通语言，我们还使用单词大小$ \ MATHCAL {O}（1）$，$ \ MATHCAL {O}（\ log \ log \ log n）$和$ \ Mathcal {o}（\ log n）$。
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-ε}$ for any $ε>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)$.
