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.ICALP.2018.127
URN: urn:nbn:de:0030-drops-91317
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9131/
Go to the corresponding LIPIcs Volume Portal

Ganardi, Moses ; Hucke, Danny ; Lohrey, Markus

Randomized Sliding Window Algorithms for Regular Languages

pdf-format:
LIPIcs-ICALP-2018-127.pdf (0.5 MB)

Abstract

A sliding window algorithm receives a stream of symbols and has to output at each time instant a certain value which only depends on the last n symbols. If the algorithm is randomized, then at each time instant it produces an incorrect output with probability at most epsilon, which is a constant error bound. This work proposes a more relaxed definition of correctness which is parameterized by the error bound epsilon and the failure ratio phi: a randomized sliding window algorithm is required to err with probability at most epsilon at a portion of 1-phi of all time instants of an input stream. This work continues the investigation of sliding window algorithms for regular languages. In previous works a trichotomy theorem was shown for deterministic algorithms: the optimal space complexity is either constant, logarithmic or linear in the window size. The main results of this paper concerns three natural settings (randomized algorithms with failure ratio zero and randomized/deterministic algorithms with bounded failure ratio) and provide natural language theoretic characterizations of the space complexity classes.

BibTeX - Entry

@InProceedings{ganardi_et_al:LIPIcs:2018:9131,
  author =	{Moses Ganardi and Danny Hucke and Markus Lohrey},
  title =	{{Randomized Sliding Window Algorithms for Regular Languages}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{127:1--127:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9131},
  URN =		{urn:nbn:de:0030-drops-91317},
  doi =		{10.4230/LIPIcs.ICALP.2018.127},
  annote =	{Keywords: sliding windows, regular languages, randomized complexity}
}

Keywords: sliding windows, regular languages, randomized complexity
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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