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.