9 MAIO / QUINTA FEIRA / 01:21
FCUP PT 
 EN
 
 
APRESENTAÇÃO
PESSOAS
ENSINO
INVESTIGAÇÃO
BIBLIOTECA
NOTÍCIAS
CONTACTOS

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