Transition Complexity of Incomplete DFAs

Yuan Gao
(The University of Western Ontario)
Kai Salomaa
(Queen's University)
Sheng Yu
(The University of Western Ontario)

In this paper, we consider the transition complexity of regular languages based on the incomplete deterministic finite automata. A number of results on Boolean operations have been obtained. It is shown 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 result is similar to that of state complexity.

In Ian McQuillan and Giovanni Pighizzini: Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (DCFS 2010), Saskatoon, Canada, 8-10th August 2010, Electronic Proceedings in Theoretical Computer Science 31, pp. 99–109.
Published: 7th August 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.31.12 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org