What is it about?
We solve a bunch of open problems connected to finite automata, including settling in the negative the longstanding Restivo's conjecture from 1981. All our solutions base on one shared construction, and as an auxiliary general tool, we introduce the concept of set rewriting systems.
Featured Image
Photo by Antoine Dautry on Unsplash
Why is it important?
This paper essentially settles in the negative the longstanding Restivo's conjecture (1981) and its weak variations.
Perspectives
Writing this article was a great pleasure as it has co-authors with whom I have had long standing collaborations. It was written as part of my masters thesis and I didn't expect I'd manage to solve such a longstanding problem.
Maksymilian Mika
Read the Original
This page is a summary of: The Frobenius and Factor Universality Problems of the Kleene Star of a Finite Set of Words, Journal of the ACM, March 2021, ACM (Association for Computing Machinery),
DOI: 10.1145/3447237.
You can read the full text:
Contributors
The following have contributed to this page
