Evènement pour le groupe Séminaire Méthodes Formelles


Date 2018-02-06  11:00-12:00
TitreThe Complexity of Decision Problems for Recognizing Morphisms 
RésuméWe discuss the complexity of decision problems on regular languages represented by morphisms to finite semigroups. There are two canonical ways of specifying the semigroup: giving its multiplication table or an implicit description as the subsemigroup of a transformation semigroup (generated by the images of the given morphism). For both representations, we will consider * the membership problem, * the emptiness/universality/inclusion/equivalence problems, * the intersection non-emptiness problem, and their restrictions to a certain classes of finite semigroups. Complexity results and open problems will be presented. 
Lieu178 
OrateurLukas Fleischer 
Emailhttp://www.fmi.uni-stuttgart.de/ti/team/fleischer/ 
UrlStuttgart University 



Aucun document lié à cet événement.

Retour
Retour à l'index