Estimados compañeros, estimadas compañeras:

El profesor Jorge Almeida (Universidade do Porto, Portugal) visitará el Departament de Matemàtiques entre el 31 de agosto y el 7 de septiembre de 2016. Es experto en teoría de semigrupos, autómatas y lenguajes formales. Durante su estancia impartirá dos charlas:

• Viernes 2 de septiembre, 12.00 h
  Seminario del Instituto Universitario de Matemática Pura y Aplicada
  Universitat Politècnica de València
  «Recent progress on concatenation hierarchies of star-free languages»
  Resumen:
  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.
• Martes 6 de septiembre, 12.00 h
  Seminario de Álgebra, Departament de Matemàtiques
  Universitat de València
  «Rauzy graphs and the free profinite semigroup»
  Resumen:
  Symbolic dynamical systems have been studied from many viewpoints, in particular in an attempt to classify them. Several algebraic and combinatorial structures have been associated to them. In the case of minimal systems, we have established a relationship between Rauzy graphs, which describe the successive reading of blocks of symbols of fixed length and certain profinite subgroups of the free profinite semigroup on the underlying set of symbols. More precisely, we have shown that these groups may be obtained as inverse limits of the profinite completions of the fundamental groups of the Rauzy graphs as the length of the blocks varies. This is joint work with Alfredo Costa (University of Coimbra).

Cordialmente,

—

Ramón.