A polynomial time algorithm to compute the Abelian kernel of a finite monoid (Q1402910)

The Abelian kernel of a finite monoid \(M\) is the intersection of all \(\tau^{-1}(1)\) where \(\tau\) is a relational morphism from \(M\) into a finite Abelian group. The first author had previously presented an algorithm to compute the Abelian kernel [Semigroup Forum 56, No. 3, 339-361 (1998; Zbl 0909.20050)], but its complexity is exponential in both the size \(m\) of the monoid and a given number \(k\) for a set of generators. In the present paper an improved algorithm is presented which for fixed \(k\) is polynomial in~\(m\), although with a large exponent even for small~\(k\). The algorithm to detect if an element \(x\) of~\(M\) lies in the Abelian kernel searches for short paths from \(1\) to~\(x\) in the Cayley graph of~\(M\) with respect to the given \(k\) generators whose label is zero in the free Abelian group.