State Complexity of Combined Operations with Union, Intersection, Star and Reversal
Titel:
State Complexity of Combined Operations with Union, Intersection, Star and Reversal
Auteur:
Gao, Yuan Yu, Sheng
Verschenen in:
Fundamenta informaticae
Paginering:
Jaargang 116 (2012) nr. 1-4 pagina's 79-92
Jaar:
2012-05-16
Inhoud:
In this paper, we study the state complexities of four combined operations: L*1 ∪ L2, L*1 ∩ L2, LR1 ∪ L2, and LR1 ∩ L2. The tight bounds for all these combined operations on regular languages are obtained and proved. We show that, as usual, they are different from the mathematical compositions of the state complexities of their individual participating operations.
Tijdschrift beschrijving