|
Technical Report: DCC-2013-02
The Operational Incomplete Transition Complexity on Finite Languages
Eva Maia, Nelma Moreira, Rogério Reis
DCC-FC & CMUP, Universidade do Porto
e-mail: {emaia,nam,rvr}@dcc.fc.up.pt
January 2013
Abstract
The state complexity of basic operations on finite languages
(considering complete DFAs) has been in studied the literature.
In this paper we study the incomplete
(deterministic) state and transition complexity on finite languages
of boolean operations, concatenation, star, and reversal. For all
operations we give tight upper bounds for both descriptional
measures. We correct the published state complexity of concatenation for
complete DFAs and
provide a tight upper bound for the case when the right
automaton is larger than the left one. For all binary
operations the tightness is proved using family languages with
a variable alphabet size. In general the operational complexities
depend not only on the complexities of the operands but also on
other refined measures.
|