Property-testing for regular languages

Corto Mascle ( Max Planck Institute for Software Systems )

Property testing studies how to determine whether a given structure satisfies a property in sublinear time using randomisation. This talk provides an introduction to the area, with a particular focus on testing whether a word belongs to a regular language. I will present a trichotomy for regular languages, with each class associated with an optimal property-testing complexity, and discuss the main algorithmic and automata-theoretic tools used to establish these results.