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. 
OrateurLukas Fleischer 
UrlStuttgart University 

Aucun document lié à cet événement.

Retour à l'index