The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words

Abstract

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