Testing membership in direct powers of idempotent semigroups
Sprache des Vortragstitels:
Englisch
Original Tagungtitel:
AAA89 The 89th Workshop on General Algebra
Sprache des Tagungstitel:
Englisch
Original Kurzfassung:
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.