Visita del profesor Jorge Almeida (31/08-07/09/2016)

Ago ’16Sep
317

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.

 

Paper “On fixed points of the lower set operator” published in Internat. J. Algebra Comput.

The following paper has been published:

El siguiente artículo ha sido publicado:

El següent article ha sigut publicat:

J. Almeida, A. Cano, O. Klíma, J.-É. Pin

On fixed points of the lower set operator

Internat. J. Algebra Comput., 25(1-2) (2015), 259–292

http://dx.doi.org/10.1142/S021819671540010X

Abstract

Lower subsets of an ordered semigroup form in a natural way an ordered semigroup. This lower set operator gives an analogue of the power operator already studied in semigroup theory. We present a complete description of the lower set operator applied to varieties of ordered semigroups. We also obtain large families of fixed points for this operator applied to pseudovarieties of ordered semigroups, including all examples found in the literature. This is achieved by constructing six types of inequalities that are preserved by the lower set operator. These types of inequalities are shown to be independent in a certain sense. Several applications are also presented, including the preservation of the period for a pseudovariety of ordered semigroups whose image under the lower set operator is proper.Read More: http://www.worldscientific.com/doi/10.1142/S021819671540010X

2010 Mathematics subject classificationPrimary: 20M07, Secondary: 20M35

Keywords: Ordered semigroups; pseudovarieties; lower sets; power operator; inequalities; pseudoidentities