2026-07-24T01:45:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9131 2024-03-06T10:43:26Z ddc:004 open_access

Randomized Sliding Window Algorithms for Regular Languages Ganardi, Moses Hucke, Danny Lohrey, Markus sliding windows regular languages randomized complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moses Ganardi and Danny Hucke and Markus Lohrey 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.127 urn:nbn:de:0030-drops-91317 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.127 eng https://creativecommons.org/licenses/by/3.0/legalcode