2026-07-22T15:57:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8485 2024-03-06T10:42:19Z ddc:004 open_access

Automata Theory on Sliding Windows Ganardi, Moses Hucke, Danny König, Daniel Lohrey, Markus Mamouras, Konstantinos regular languages sliding window algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moses Ganardi and Danny Hucke and Daniel König and Markus Lohrey and Konstantinos Mamouras 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.31 urn:nbn:de:0030-drops-84851 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.31 eng https://creativecommons.org/licenses/by/3.0/legalcode