2013 | OriginalPaper | Buchkapitel
Kleene Star on Unary Regular Languages
verfasst von : Kristína Čevorová
Erschienen in: Descriptional Complexity of Formal Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.