Affiliations: Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7. [email protected] | School of Computing, Queen's University, Kingston, Ontario, Canada K7L 3N6. [email protected] | Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7. [email protected]
Note: [] Address for correspondence: Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7
Abstract: We consider the transition complexity of regular languages based on the incomplete deterministic finite automata. We establish tight bounds for the transition complexity of Boolean operations, in the case of union the upper and lower bounds differ by a multiplicative constant two. We show that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity bounds turn out to be similar to the corresponding bounds for state complexity.
