  We solve open problems concerning the Kleene star $L^*$ of a finite set $L$
of words over an alphabet $\Sigma$. The \emph{Frobenius monoid} problem is the
question for a given finite set of words $L$, whether the language $L^*$ is
cofinite. We show that it is PSPACE-complete. We also exhibit an infinite
family of sets $L$ such that the length of the longest words not in $L^*$ (when
$L^*$ is cofinite) is exponential in the length of the longest words in $L$ and
subexponential in the sum of the lengths of words in $L$. The \emph{factor
universality} problem is the question for a given finite set of words $L$,
whether every word over $\Sigma$ is a factor (substring) of some word from
$L^*$. We show that it is also PSPACE-complete. Besides that, we exhibit an
infinite family of sets $L$ such that the length of the shortest words not
being a factor of any word in $L^*$ is exponential in the length of the longest
words in $L$ and subexponential in the sum of the lengths of words in $L$. This
essentially settles in the negative the longstanding Restivo's conjecture
(1981) and its weak variations. All our solutions base on one shared
construction, and as an auxiliary general tool, we introduce the concept of
\emph{set rewriting systems}. Finally, we complement the results with upper
bounds.
