2026-07-20T11:16:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6853 2024-03-06T10:39:02Z ddc:004 open_access

Querying Regular Languages over Sliding Windows Ganardi, Moses Hucke, Danny Lohrey, Markus streaming algorithms regular languages space complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moses Ganardi and Danny Hucke and Markus Lohrey 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.18 urn:nbn:de:0030-drops-68539 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.18 eng https://creativecommons.org/licenses/by/3.0/legalcode