State complexity approximation
Seminar 26/06/09, 15h by Prof. Sheng Yu from University of Western Ontario, Canada
Title: State complexity approximation
Speaker: Prof. Sheng Yu Department of Computer Science University of Western Ontario London, Ontario, Canada
Date: 26/06/2009, 15h
Place: Anfiteatro 2, DCC-FCUP Rua do Campo Alegre 1021 Porto
Abstract: In this talk, the basic concept of state complexity is reviewed and the new concept of state complexity approximation is introduced. The new concept is a further development of state complexity estimation. We show that this new concept is important in at least the following two cases: the exact state complexities are not known and difficult to obtain, and the state complexities have been obtained but are in incomprehensive forms. A number of examples will be shown to explain the new concept and to demonstrate its usefulness.