Grant: Discovery Grants Program - Individual
Queen's University
$30,000.00
Automata with limited nondeterminism and applications of automata
EF 2015-16
Résumé
Finite-state machines, or finite automata, are an abstract model of computation and a basis for the study of fundamental questions in computing. There are many applications of finite automata, for example, compilers, text searching, natural language processing, web services and program verification.
By studying foundational properties of abstract models, such as finite automata, we can gain deeper insights into the complexity of computation, in particular, descriptional complexity. In descriptional complexity we are concerned with how succinctly certain objects, such as algorithms, can be specified. This is different from computational complexity which quantifies the resources, for example time, used by an algorithm. A commonly used descriptional complexity measure for finite automata is ""state complexity"" which quantifies the minimal number of states of an automaton recognizing a given language. Questions of descriptional complexity have become more important also from an applications point of view since finite automata used in natural language processing typically require millions of states.
Nondeterminism is a model of parallel computation. The work of the proposal deals with finite automata employing limited nondeterminism and we want to determine how much we can reduce the number of states by allowing additional parallelism, and vice versa. The crucial task is to establish lower bounds, that is, we have to prove that no machine with fewer states can recognize the same language. We can use techniques of communication complexity to prove lower bounds for the size of automata with limited nondeterminism.
The requested funding will support the research activity of 4 graduate students and one undergraduate student each year.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
217321-2013
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
2015
Competition year année de concours
2013
Award amount
30000
Program id
RGPIN
Program name 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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
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
3
Nb partie
5
Application title
Automata with limited nondeterminism and applications of automata
Keyword
NSERC
Application summary
Finite-state machines, or finite automata, are an abstract model of computation and a basis for the study of fundamental questions in computing. There are many applications of finite automata, for example, compilers, text searching, natural language processing, web services and program verification.
By studying foundational properties of abstract models, such as finite automata, we can gain deeper insights into the complexity of computation, in particular, descriptional complexity. In descriptional complexity we are concerned with how succinctly certain objects, such as algorithms, can be specified. This is different from computational complexity which quantifies the resources, for example time, used by an algorithm. A commonly used descriptional complexity measure for finite automata is ""state complexity"" which quantifies the minimal number of states of an automaton recognizing a given language. Questions of descriptional complexity have become more important also from an applications point of view since finite automata used in natural language processing typically require millions of states.
Nondeterminism is a model of parallel computation. The work of the proposal deals with finite automata employing limited nondeterminism and we want to determine how much we can reduce the number of states by allowing additional parallelism, and vice versa. The crucial task is to establish lower bounds, that is, we have to prove that no machine with fewer states can recognize the same language. We can use techniques of communication complexity to prove lower bounds for the size of automata with limited nondeterminism.
The requested funding will support the research activity of 4 graduate students and one undergraduate student each year.