2011 | OriginalPaper | Buchkapitel
State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal
verfasst von : Yuan Gao, Sheng Yu
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
In this paper, we study the state complexities of union and intersection combined with star and reversal, respectively. We obtain the exact bounds for these combined operations on regular languages and show that, as usually, they are different from the mathematical compositions of the state complexities of their individual participating operations.