Property testing regular languages

Speaker(s)

Szymon Toruńczyk

Affiliation

Uniwersytet Warszawski

Date

March 19, 2008, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Property testing is concerned with the following type of problems: Let L be a property of a class of objects. A property tester for L is an algorithm, which, given an input object w, uses a small number of (possibly random) queries about w to determine with high probability whether w has the property L or whether it is far from having it. I will present a result of Alon et al. stating that membership of a word w in a given regular language L is testable with a constant (dependent on L but not on w) number of queries to w. I will also discuss a result of Magniez and Rougemont on testability of membership in regular languages of trees.

---