28 DECEMBER / SATURDAY / 11:38
FCUP PT 
 EN
 
 
INFORMATION
STAFF
EDUCATION
RESEARCH
LIBRARY
NEWS
CONTACTS

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.


FCUP 2024