Affordable Access

Querying Regular Languages over Sliding Windows

Authors
Publication Date
Source
Dagstuhl Research Online Publication Server
Keywords
  • Streaming Algorithms, Regular Languages, Space Complexity
  • Data Processing Computer Science
External links

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments