2013 | OriginalPaper | Chapter
Kleene Star on Unary Regular Languages
Author : Kristína Čevorová
Published in: Descriptional Complexity of Formal Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study possible deterministic state complexities of languages obtained as the Kleene star of a unary language with state complexity
n
. We prove that for every
n
, depending on the parity of
n
, only 3 or 4 complexities from
n
2
− 4
n
+ 6 to
n
2
− 2
n
+ 2 are attainable. On the other hand, we show that all the complexities from 1 to
n
are attainable. In the end, we outline a connection to the Frobenius problem.