Technical Report: DCC-2012-02

On the Incomplete Transition Complexity of Some Basic Operations on Regular Languages

Eva Maia, Nelma Moreira, Rogério Reis

DCC-FC & CMUP, Universidade do Porto
e-mail: {emaia,nam,rvr}@dcc.fc.up.pt
April 2012

Abstract

Y. Gao et al. studied for the first time the transition complexity of Boolean operations on regular languages based on non necessarily complete DFAs. For the intersection and the complementation, tight bounds were presented, but for the union operation the upper and lower bounds differ by a multiplicative constant two. In this paper we continue this study by extending the analysis to the concatenation and the Kleene star operations. For both operations tight upper bounds are given, as well as, a tight upper bound for the transition complexity of the union.