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. |