Estimation of state complexity of combined operations
It appears that the state complexity of each combined operation has its own special features. Thus, it is important and practical to obtain good estimates for some commonly used general cases. In this paper, we consider the state complexity of combined Boolean operations and give an exact bound for all of them in the case when the alphabet is not fixed. Moreover, we show that for any fixed alphabet, this bound can be reached in infinitely many cases. We also consider the state complexity of multiple catenations. The state complexities are obtained in the cases of the catenations of three and four languages. An estimate for the catenation of an arbitrary number of languages is given, which is very close to the state complexities in the three and four languages cases. (C) 2009 Elsevier B.V. All rights reserved.
estimation state complexity combined operations multiple operations