Technical Report: DCC-2011-08
A Review on State Complexity of Individual Operations
Yuan Gao
Dep. of Computer Science, University of Western Ontario
E-mail: gao@csd.uwo.ca
Nelma Morera
CMUP & DCC-FCUP
E-mail: nam@dcc.fc.up.pt
Rogério Reis
CMUP & DCC-FCUP
E-mail: rvr@dcc.fc.up.pt
Sheng Yu
Dep. of Computer Science, University of Western Ontario
E-mail: sy@csd.uwo.ca
April 2011
Abstract
The state complexity of a regular language is the number of states
of its minimal automaton. The complexity of a language operation is
the complexity of the resulting language seen as a function of the
complexities of the operation arguments. In this report we review
some of the results of state complexity of individual operations for
regular and some subregular languages.