Chennai Mathematical Institute

Seminars




2.00 pm, Seminar Hall
CMI Silver Jubilee Lecture
An overview of the theory of varieties of languages

Pascal Weil
CNRS and LaBRI, University of Bordeaux, France.
19-02-15


Abstract

The theory of varieties (of languages) is an important tool for the classification of regular languages. Eilenbergs 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.





Google
Search WWW Search cmi.ac.in