Grant: Discovery Grants Program - Individual
University of Waterloo
$18,000.00
Quotient complexity of regular languages
EF 2013-14
Résumé
Finite automata are abstract models of hardware and software computing systems, and are closely related to regular languages, which are formal models for sets of strings of symbols. Every regular language can be recognized by a unique minimal finite automaton, and the language recognized by every finite automaton is regular.There are many applications of finite automata and regular languages, for example, design of digital circuits, compilers, text-searching, communication protocols, and web services. When implementing operations on regular languages, such as union or concatenation, it is important to know the worst-case complexity of the resulting language. A common measure of complexity is ""state complexity"", which is the number of states in the minimal automaton accepting the language. If a class of regular languages possesses some special properties, then the state complexity of operations on this class may be significantly lower. So far, very few subclasses of regular languages have been studied. The objective of this proposal is to study several special subclasses of regular languages.The problems to be solved include: finding upper bounds on the complexity of operations in a given class of languages, finding languages that meet this bound, and studying hierarchies of complexities.
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
871-2010
Name nom
Brzozowski, Janusz
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2010
Award amount
18000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
4
Nb partie
5
Application title
Quotient complexity of regular languages
Keyword
NSERC
Application summary
Finite automata are abstract models of hardware and software computing systems, and are closely related to regular languages, which are formal models for sets of strings of symbols. Every regular language can be recognized by a unique minimal finite automaton, and the language recognized by every finite automaton is regular.There are many applications of finite automata and regular languages, for example, design of digital circuits, compilers, text-searching, communication protocols, and web services. When implementing operations on regular languages, such as union or concatenation, it is important to know the worst-case complexity of the resulting language. A common measure of complexity is ""state complexity"", which is the number of states in the minimal automaton accepting the language. If a class of regular languages possesses some special properties, then the state complexity of operations on this class may be significantly lower. So far, very few subclasses of regular languages have been studied. The objective of this proposal is to study several special subclasses of regular languages.The problems to be solved include: finding upper bounds on the complexity of operations in a given class of languages, finding languages that meet this bound, and studying hierarchies of complexities.