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