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.ISAAC.2019.6
URN: urn:nbn:de:0030-drops-115023
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11502/
Go to the corresponding LIPIcs Volume Portal

Ganardi, Moses ; Hucke, Danny ; Lohrey, Markus ; Starikovskaya, Tatiana

Sliding Window Property Testing for Regular Languages

pdf-format:
LIPIcs-ISAAC-2019-6.pdf (0.5 MB)

Abstract

We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window n and a stream of symbols. At each time instant, we must decide whether the suffix of length n of the current stream ("the active window") belongs to a given regular language.
Recent works [Moses Ganardi et al., 2018; Moses Ganardi et al., 2016] showed that the space complexity of an optimal deterministic sliding window algorithm for this problem is either constant, logarithmic or linear in the window size n and provided natural language theoretic characterizations of the space complexity classes. Subsequently, [Moses Ganardi et al., 2018] extended this result to randomized algorithms to show that any such algorithm admits either constant, double logarithmic, logarithmic or linear space complexity.
In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We show that for every regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.

BibTeX - Entry

@InProceedings{ganardi_et_al:LIPIcs:2019:11502,
  author =	{Moses Ganardi and Danny Hucke and Markus Lohrey and Tatiana Starikovskaya},
  title =	{{Sliding Window Property Testing for Regular Languages}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11502},
  URN =		{urn:nbn:de:0030-drops-115023},
  doi =		{10.4230/LIPIcs.ISAAC.2019.6},
  annote =	{Keywords: Streaming algorithms, approximation algorithms, regular languages}
}

Keywords: Streaming algorithms, approximation algorithms, regular languages
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019

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