License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.15
URN: urn:nbn:de:0030-drops-95973
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9597/
Go to the corresponding LIPIcs Volume Portal

Ganardi, Moses ; Jez, Artur ; Lohrey, Markus

Sliding Windows over Context-Free Languages

pdf-format:
LIPIcs-MFCS-2018-15.pdf (0.4 MB)

Abstract

We study the space complexity of sliding window streaming algorithms that check membership of the window content in a fixed context-free language. For regular languages, this complexity is either constant, logarithmic or linear [Moses Ganardi et al., 2016]. We prove that every context-free language whose sliding window space complexity is log_2(n) - omega(1) must be regular and has constant space complexity. Moreover, for every c in N, c >= 1 we construct a (nondeterministic) context-free language whose sliding window space complexity is O(n^(1/c)) \ o(n^(1/c)). Finally, we give an example of a deterministic one-counter language whose sliding window space complexity is Theta((log n)^2).

BibTeX - Entry

@InProceedings{ganardi_et_al:LIPIcs:2018:9597,
  author =	{Moses Ganardi and Artur Jez and Markus Lohrey},
  title =	{{Sliding Windows over Context-Free Languages}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9597},
  URN =		{urn:nbn:de:0030-drops-95973},
  doi =		{10.4230/LIPIcs.MFCS.2018.15},
  annote =	{Keywords: sliding windows, streaming algorithms, context-free languages}
}

Keywords: sliding windows, streaming algorithms, context-free languages
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

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