Property testing regular languages

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

Uniwersytet Warszawski

Termin

19 marca 2008 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---