The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal

Article type: Research Article

Authors: Gao, Yuan | Salomaa, Kai | Yu, Sheng

Affiliations: Department of Computer Science, The University of Western Ontario London, Ontario N6A 5B7, Canada. E-mail: {ygao72,syu}@csd.uwo.ca | School of Computing, Queen's University, Kingston, Ontario K7L 3N6, Canada. E-mail: ksalomaa@cs.queensu.ca

Abstract: 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.

Journal: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 75-89, 2008