2013 | OriginalPaper | Buchkapitel
Reversal on Regular Languages and Descriptional Complexity
verfasst von : Juraj Šebej
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 the problem stated as follows: which values in the range from log
n
to 2
n
may be obtained as the state complexity of the reverse of a regular language represented by a minimal deterministic automaton of
n
states? In the main result of this paper we use an alphabet of size 2
n
− 2 to show that the entire range of complexities may be produced for any
n
. This considerably improves an analogous result from the literature that uses an alphabet of size 2
n
. We also provide some partial results for the case of a binary alphabet.