License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.38
URN: urn:nbn:de:0030-drops-174301
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17430/
Go to the corresponding LIPIcs Volume Portal

Ganardi, Moses ; Jachiet, Louis ; Lohrey, Markus ; Schwentick, Thomas

Low-Latency Sliding Window Algorithms for Formal Languages

pdf-format:
LIPIcs-FSTTCS-2022-38.pdf (0.8 MB)

Abstract

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 ?(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 ?(1), ?(log log n), and ?(log n).

BibTeX - Entry

@InProceedings{ganardi_et_al:LIPIcs.FSTTCS.2022.38,
  author =	{Ganardi, Moses and Jachiet, Louis and Lohrey, Markus and Schwentick, Thomas},
  title =	{{Low-Latency Sliding Window Algorithms for Formal Languages}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{38:1--38:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17430},
  URN =		{urn:nbn:de:0030-drops-174301},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.38},
  annote =	{Keywords: Streaming algorithms, regular languages, context-free languages}
}

Keywords: Streaming algorithms, regular languages, context-free languages
Collection: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI