Sliding window property testing for regular languages

12/11/2019 - 09:45
Speaker: 
Seminar: 
מיקום: 
Abstract: 

In this talk, we discuss the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window n and a stream of symbols. At each time instant, we must decide whether the suffix of length n of the current stream (“the active window”) belongs to a given regular language.

Recent works showed that the space complexity of an optimal deterministic sliding window algorithm for this problem is either constant, logarithmic, or linear in the window size n; and either constant, double logarithmic, logarithmic, or linear in the randomized setting.

In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject if it is far from the language. We consider deterministic and randomized sliding window property testers with one-sided and two-sided errors. In particular, we show that for any regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.

 

The talk is based on a joint work with M. Ganardi, D. Hucke, and M. Lohrey accepted to ISAAC 2019.