El Profesor Jorge Almeida impartirá el día 2 de septiembre, a las 12 horas, una conferencia en el Seminario del IUMPA, titulada “Recent progress on concatenation hierarchies of star-free languages”. Se adjunta más abajo el abstract.

Estáis todos invitados.


A celebrated theorem of Schützenberger (1965) states that a language can be expressed in the letters using only finite union, complementation, and concatenation (the so-called star-free languages) if and only if its syntactic semigroup has only trivial subgroups. On the other hand, McNaughton and Papert (1971) showed that such languages are precisely those that may be defined by first order sentences, where words are viewed as finite linear orders with predicates for each letter to express that the letter appears in a specific position. The combination of the two theorems provides an algorithm to decide when a regular language admits such a definition. A further ingredient was given by W. Thomas (1982), who showed that the analogue of the arithmetical hierarchy in this context, determined by the alternation of quantifiers, is intimately connected with the alternation of the closures under union, intersection, and concatenation, versus union and complementation, a hierarchy first introduced by Brzozowski (1971). The major open problem in this area is whether one can compute the minimum number of quantifier alternations needed to define a given star-free language. The purpose of the talk is to survey recent progress on this topic.