Chennai Mathematical Institute

Silver Jubilee Events


CMI Silver Jubilee Lecture

Pascal Weil, LaBRI, University of Bordeaux, France

An overview of the theory of varieties of languages

Thursday, February 19, 2015

Abstract:

The theory of varieties (of languages) is an important tool for the classification of regular languages. Eilenberg’s theorem, in the mid-1970s, crystallized a series of earlier results, and established a connection between language theory and finite monoid theory. It provided an efficient engine for the characterization and decidability of many classes of languages, and a robust framework for a fine classification, especially of logically defined classes of languages. Several extensions of the theory were introduced in the 1990s, extending the domain of application of the theory (e.g. positive varieties). During the same period, it was realized that variety theory had deep topological foundations. I will give an overview of the theory as it stands now, in the light of results of Gehrke, Grigorieff and Pin in the last decade, which put the topological point of view at the center, and thus shed a unifying light over the previous results and extensions.