An NP-hardness Result on the Monoid Frobenius Problem

Zhi Xu, J. Shallit

The following problem is NP-hard: given a regular expression $E$, decide if $E^{\ast }$ is not co-finite.