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.STACS.2018.31
URN: urn:nbn:de:0030-drops-84851
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8485/
Go to the corresponding LIPIcs Volume Portal

Ganardi, Moses ; Hucke, Danny ; König, Daniel ; Lohrey, Markus ; Mamouras, Konstantinos

Automata Theory on Sliding Windows

pdf-format:
LIPIcs-STACS-2018-31.pdf (0.6 MB)

Abstract

In a recent paper we analyzed the space complexity of streaming algorithms whose goal is to decide membership of a sliding window to a fixed language. For the class of regular languages we proved a space trichotomy theorem: for every regular language the optimal space bound is either constant, logarithmic or linear. In this paper we continue this line of research: We present natural characterizations for the constant and logarithmic space classes and establish tight relationships to the concept of language growth. We also analyze the space complexity with respect to automata size and prove almost matching lower and upper bounds. Finally, we consider the decision problem whether a language given by a DFA/NFA admits a sliding window algorithm using logarithmic/constant space.

BibTeX - Entry

@InProceedings{ganardi_et_al:LIPIcs:2018:8485,
  author =	{Moses Ganardi and Danny Hucke and Daniel K{\"o}nig and Markus Lohrey and Konstantinos Mamouras},
  title =	{{Automata Theory on Sliding Windows}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8485},
  URN =		{urn:nbn:de:0030-drops-84851},
  doi =		{10.4230/LIPIcs.STACS.2018.31},
  annote =	{Keywords: regular languages, sliding window algorithms}
}

Keywords: regular languages, sliding window algorithms
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

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