2026-07-25T03:08:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9597 2024-03-06T10:44:30Z ddc:004 open_access

Sliding Windows over Context-Free Languages Ganardi, Moses Jez, Artur Lohrey, Markus sliding windows streaming algorithms context-free languages We study the space complexity of sliding window streaming algorithms that check membership of the window content in a fixed context-free language. For regular languages, this complexity is either constant, logarithmic or linear [Moses Ganardi et al., 2016]. We prove that every context-free language whose sliding window space complexity is log_2(n) - omega(1) must be regular and has constant space complexity. Moreover, for every c in N, c >= 1 we construct a (nondeterministic) context-free language whose sliding window space complexity is O(n^(1/c)) \ o(n^(1/c)). Finally, we give an example of a deterministic one-counter language whose sliding window space complexity is Theta((log n)^2). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moses Ganardi and Artur Jez and Markus Lohrey 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.15 urn:nbn:de:0030-drops-95973 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.15 eng https://creativecommons.org/licenses/by/3.0/legalcode