Systems of Equations Satisfied in All Commutative Finite Semigroups

摘要

The following problem is considered: check if a system of equations has a solution in every commutative finite semigroup. It is shown that the problem is decidable, and NP-complete. The problem is related with the pumping lemma for regular languages.