Testing membership in direct powers of idempotent semigroups

Description

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.

Period	27 Feb 2015
Event title	AAA89 The 89th Workshop on General Algebra
Event type	Conference
Location	GermanyShow on map