Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.15
URN: urn:nbn:de:0030-drops-95973
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9597/
Ganardi, Moses ; Jez, Artur ; Lohrey, Markus
Sliding Windows over Context-Free Languages
| pdf-format: |
|
Abstract
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).
BibTeX - Entry
@InProceedings{ganardi_et_al:LIPIcs:2018:9597,
author = {Moses Ganardi and Artur Jez and Markus Lohrey},
title = {{Sliding Windows over Context-Free Languages}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {15:1--15:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-086-6},
ISSN = {1868-8969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9597},
URN = {urn:nbn:de:0030-drops-95973},
doi = {10.4230/LIPIcs.MFCS.2018.15},
annote = {Keywords: sliding windows, streaming algorithms, context-free languages}
}
| Keywords: | sliding windows, streaming algorithms, context-free languages | |
| Seminar: | 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 27.08.2018 |
