Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Queen's University

$23,000.00

Descriptional complexity of finite-state machines

FY 2009-10

Summary
My research on finite-state machines is part of the theory of computing. Algorithms based on finite-state machines are used in practically all areas of computing, from natural language processing to software verification. My work deals with lower bounds for the size of finite-state machines. This area of research is called descriptional complexity. When we have an implementation of a finite-state machine for a problem P, this gives an upper bound for the descriptional complexity of P. However, the crucial task is to establish lower bounds, that is, we have to prove that no machine of smaller size can solve the problem. Work on descriptional complexity contributes to our understanding of fundamental questions on the difficulty of computational problems. Descriptional complexity has recently become more important also from an applications point of view since finite-state machines used in natural language processing may require millions of states. A finite-state machine can be in one of a finite number of states and changes its state at discrete time steps according to a given set of transitions. A typical example of the type of questions I am interested in, is to determine the number of transitions that a machine with a given number of states may need in the worst-case. The number of transitions is at most quadratic in the number of states, even if the machine is nondeterministic, that is, it can have multiple transitions for a given state and input symbol. However, currently we do not have matching lower bounds. In order to find worst-case examples we need both theoretical tools from combinatorics and software implementations of the finite-state machines to test our conjectures. The work of the proposal involves, at a given time, the training of 2 Ph.D. and 2 M.Sc. students. Our research group hosted the 9th International Conference on Implementation and Application of Automata at Queen's University in July 2004.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
217321-2008
Name nom
Salomaa, Kai
Department département
Computing, School of
Organization id
29
Institution établissement
Queen's University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2008
Award amount
23000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
2
Nb partie
5
Application title
Descriptional complexity of finite-state machines
Keyword
NA
Application summary
My research on finite-state machines is part of the theory of computing. Algorithms based on finite-state machines are used in practically all areas of computing, from natural language processing to software verification. My work deals with lower bounds for the size of finite-state machines. This area of research is called descriptional complexity. When we have an implementation of a finite-state machine for a problem P, this gives an upper bound for the descriptional complexity of P. However, the crucial task is to establish lower bounds, that is, we have to prove that no machine of smaller size can solve the problem. Work on descriptional complexity contributes to our understanding of fundamental questions on the difficulty of computational problems. Descriptional complexity has recently become more important also from an applications point of view since finite-state machines used in natural language processing may require millions of states. A finite-state machine can be in one of a finite number of states and changes its state at discrete time steps according to a given set of transitions. A typical example of the type of questions I am interested in, is to determine the number of transitions that a machine with a given number of states may need in the worst-case. The number of transitions is at most quadratic in the number of states, even if the machine is nondeterministic, that is, it can have multiple transitions for a given state and input symbol. However, currently we do not have matching lower bounds. In order to find worst-case examples we need both theoretical tools from combinatorics and software implementations of the finite-state machines to test our conjectures. The work of the proposal involves, at a given time, the training of 2 Ph.D. and 2 M.Sc. students. Our research group hosted the 9th International Conference on Implementation and Application of Automata at Queen's University in July 2004.