Evènement pour le groupe Graphes et Logique

Date 2012-05-25  11:00-12:00
TitreSome operators that preserve the locality of a pseudovariety of semigroups.  
RésuméFinite semigroups are a useful algebraic tool to decide computational problems from automata theory, formal languages and logic. In this framework, the decidability of a property is quite often reduced to the decidability of (the membership in) a pseudovariety of semigroups. For example, a language of finite words can be expressed by a sentence of the first order fragment FO^2[<] if and only of its syntactic semigroup belongs to the pseudovariety DA, as shown by Thérien and Wilke. Frequently a pseudovariety is expressed in terms of more simple decidable pseudovarieties, using operations between them, like the Mal'cev product and the semidirect product. However, these operations do not always preserve decidability. In this context, an algebraic property of pseudovarieties called "locality" is useful. For example, Thérien and Wilke showed that the pseudovariety corresponding to FO^2[<,suc] is DA*D, which is decidable since Almeida proved DA is local. We study a family of Mal'cev operators of the form Z(m)_, showing that some of them preserve the locality of pseudovarieties. In the process, we deal with the localization operator L( ) and the semidirect product operator ( )*D, establishing some interplay between them. Among these operators we find K(m)_ and D(m)_. As an application, we deduce that the pseudovarieties in the hierarchies R_1, R_2, R_3... and L_1, L_2, L_3... of subpseudovarieties of DA, obtained from J by alternate application of the operators K(m)_ and D(m)_, are local when m>1. These pseudovarieties are interesting, since recently Kufleitner and Weil proved the decidability of the variety of languages expressed by the fragment of sentences of FO^2[<] with at most m alternating blocks of quantifiers in its parsing tree, by showing that this variety corresponds to the intersection between R_m and L_m. This is joint work with Ana Escada.  
Lieusalle 178 
OrateurAlfredo Costa 
UrlUniversity of Coimbra 

Aucun document lié à cet événement.

Retour à l'index