Lectures in the spring semester 2013 PDF Print

Lectures take place at the Institute of Mathematics and Statistics, No.8 building within the Faculty of Science, Kotlarska 2, Brno

Wednesday, June 12, 2013, at 2:00 p.m. in M2:

Ondřej Klíma
Varieties of Regular Languages in Straubing-Thérien hierarchy

Abstract:

A regular language is star-free if it can be constructed from finite languages using Boolean operations and concatenations. Within the class of all star-free languages, two important hierarchies were defined: the dot-depth hierarchy, introduced in 1971, and its natural variant, the Straubing-Thérien hierarchy, introduced in 1981. The basic question concerning these hierarchies is to algorithmically calculate the minimal level in the hierarchy to which a given star-free language belongs. This question turned out to be very difficult. Finding an effective characterization of languages of the second level in the Straubing-Thérien hierarchy is one of the most intriguing open problems in the theory of regular languages, and it has been one of the main driving forces for the development of the algebraic theory of regular languages. The algebraic approach is based on studying properties of a regular language through the properties of its syntactic monoid/semigroup.

In this talk we overview some motivations, ideas, known results and also our contribution to the research on Straubing-Thérien hierarchy of star-free languages and the algebraic theory of regular languages in general.

Last Updated on Thursday, 30 May 2013 13:22