Low-Latency Sliding Window Algorithms for Formal Languages
| Autor: | Ganardi, Moses, Jachiet, Louis, Lohrey, Markus, Schwentick, Thomas |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
68W27 68Q45 68P05 context-free languages Theory of computation → Grammars and context-free languages Formal Languages and Automata Theory (cs.FL) Streaming algorithms Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Computer Science - Formal Languages and Automata Theory Theory of computation → Streaming models Theory of computation → Regular languages regular languages |
| DOI: | 10.4230/lipics.fsttcs.2022.38 |
| Popis: | 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)$. Comment: A short version will be presented at the conference FSTTCS 2022 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|