ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
Kai Salomaa, Sheng Yü · International Journal of Foundations of Computer Science · 2007
We consider the state complexity of several combined operations. Those results show that the state complexity of a combined operation is in general very different from the composition of the state complexities of the participating individual operations. We also consider general estimation methods for the state complexity of combined operations. In particular, estimation through nondeterministic state complexity is studied. It is shown that the method is very promising for a large class of combined operations.