文章基本信息

标题：Querying Regular Languages over Sliding Windows
本地全文：下载
作者：Moses Ganardi ; Danny Hucke ; Markus Lohrey 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：65
页码：18:1-18:14
DOI：10.4230/LIPIcs.FSTTCS.2016.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：streaming algorithms; regular languages; space complexity