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.FSTTCS.2016.18
URN: urn:nbn:de:0030-drops-68539
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6853/
Go to the corresponding LIPIcs Volume Portal

Ganardi, Moses ; Hucke, Danny ; Lohrey, Markus

Querying Regular Languages over Sliding Windows

pdf-format:
LIPIcs-FSTTCS-2016-18.pdf (0.5 MB)

Abstract

We study the space complexity of querying regular languages over data streams in the sliding window model. The algorithm has to answer at any point of time whether the content of the sliding window belongs to a fixed regular language. A trichotomy is shown: For every regular language the optimal space requirement is either in Theta(n), Theta(log(n)), or constant, where $n$ is the size of the sliding window.

BibTeX - Entry

@InProceedings{ganardi_et_al:LIPIcs:2016:6853,
  author =	{Moses Ganardi and Danny Hucke and Markus Lohrey},
  title =	{{Querying Regular Languages over Sliding Windows}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6853},
  URN =		{urn:nbn:de:0030-drops-68539},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.18},
  annote =	{Keywords: streaming algorithms, regular languages, space complexity}
}

Keywords: streaming algorithms, regular languages, space complexity
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

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