The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal
Yuan Gao, Kai Salomaa, Sheng Yü · Fundamenta Informaticae · 2008
The state complexity of two combined operations, star of catenation and star of reversal, on regular languages is considered in this paper. Tight bounds are obtained for both combined operations. The results clearly show that the state complexity of a combined operation can be very different from the composition of the state complexities of its participating individual operations. A new approach for research in automata and formal language theory is also explained.