State Complexity of Combined Operations with Union, Intersection, Star and Reversal
Yuan Gao, Sheng Yü · Fundamenta Informaticae · 2012
In this paper, we study the state complexities of four combined operations: L* 1 ∪ L2 , L* 1 ∩ L2 , LR 1 ∪ L2 , and LR 1 ∩ L2 . The tight bounds for all these combined operations on regular languages are obtained and proved. We show that, as usual, t