NON-UNIQUENESS AND RADIUS OF CYCLIC UNARY NFAs
Michael Domaratzki, Keith Ellul, Jeffrey O. Shallit, MING-WEI WANG · International Journal of Foundations of Computer Science · 2005
In this paper we study some properties of cyclic unary regular languages. We find a connection between the uniqueness of the minimal NFA for certain cyclic unary regular languages and a Diophantine equation studied by Sylvester. We also obtain some results on the radius of unary languages. We show that the nondeterministic radius of a cyclic unary regular language L is not necessarily obtained by any of the minimal NFAs for L. We give a class of examples which demonstrates that the nondeterministic radius of a regular language cannot necessarily even be approximated by the minimal radius of its minimal NFAs.