Membership testing in commutative transformation semigroups

Given a finite set X of states, a finite set of commuting transformations of X (generators), and another transformation f of X, we analyze the complexity of deciding whether f can be obtained by composition of the generators. Looking first at the action of a commutative semigroup of transformations of a finite set, we obtain an algorithm for membership testing, valid for arbitrary commutative semigroups. We then show that the complexity of the problem varies with the threshold of the semigroup: polynomial-time (NC 3 in parallel) with threshold zero or one, and NP-complete otherwise.

Authors

• Martin Beaudry

Keywords

No keywords are indexed for this paper.