The Hong Kong University of Science and Technology
Department of Computer Science


PhD Thesis Defence


"Regular Languages and Codes"

By

Mr. Yo-Sub Han


Abstract

Regular languages are one of the oldest and well-known topics in formal
language theory. It has been more than a half century since the
introduction of regular languages. During this time period, many
challenging and exciting problems have been solved. Many researchers have
even believed that regular languages are a dead topic. However, because of
new applications, many interesting problems have arisen and some of them
have initiated new areas to investigate with respect to regular languages.

First, we survey finite-state automaton constructions and state
elimination, which we use to prove the Kleene theorem. In particular, we
study the structural properties of finite-state automata for computing
shorter regular expression using state elimination.

Second, we look at a popular application of regular languages, the pattern
matching problem. We show that a given pattern is prefix-free, then there
are at most a linear number of matching substrings. Furthermore, we
vigorously examine subfamilies of regular languages and, in particular,
investigate the decision problems and the prime decomposition problems for
these subfamilies.

We expect that we can extend results in this thesis for more general
families such as context-free languages, and aim to develop applications
based on these new results.


Date:			Wednesday, 26 October 2005

Time:			10:00a.m.-12:00noon

Venue:			Room 4480
			Lifts 25-26

Chairman:		Prof Qi Man Shao (MATH)

Committee Members:	Prof. Derick Wood (Supervisor)
			Prof. Sunil Arya
			Prof. Mordecai J. Golin
			Prof. Albert Y. Lo (ISMT)
			Prof. Arto Salomaa (Turku Centre for Computer Science,
					    Finland)


**** ALL are Welcome ****