文章基本信息

标题：Sliding Windows over Context-Free Languages
本地全文：下载
作者：Moses Ganardi ; Artur Jez ; Markus Lohrey 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：117
页码：1-15
DOI：10.4230/LIPIcs.MFCS.2018.15
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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).
关键词：sliding windows; streaming algorithms; context-free languages