Testing membership in direct powers of idempotent semigroups
Sprache des Vortragstitels:
AAA89 The 89th Workshop on General Algebra
Sprache des Tagungstitel:
Let S be a finite semigroup. We are interested in the following problem: If we are given tuples a1,...,ak,b in S^n, can we generate b by a1,...,ak using componentwise multiplication?
For arbitrary semigroups this membership problem is always in PSPACE. In
this talk we focus on idempotent semigroups and present several results on the complexity. In particular, we deal with the question when the problem is in P.