Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$41,000.00

Descriptional complexity, combinatorics on words, formal languages and number theory

EF 2010-11

Résumé
I propose to investigate problems combining aspects of theoretical computer science, combinatorics, algebra, and number theory, along the lines of the topics in my recent monograph with Jean-Paul Allouche, ""Automatic Sequences: Theory, Applications, Generalizations"", published by Cambridge University Press in 2003. In particular, I plan to work on problems involving the topics of descriptional complexity, conbinatorics on words, formal languages, and finite automata. In descriptional complexity, we are concerned with how succinctly objects can be described (as opposed to the resource consumption of algorithms, which is the domain of computational complexity). The techniques used in this area are taken from algebra, number theory, and combinatorics, and problems frequently make use of deep results in these areas. Combinatorics on words is concerned with the properties of strings of symbols. For example, given two words, when do they ""commute"" (that is, read the same no matter which word is taken first)? Although of interest in its own right, recently there are also some applications to cryptography, where it is used in constructing hash functions resistant to certain kinds of attacks. Formal languages is the study of the mathematical properties of languages, which are sets of words. This area is of particular interest because of applications to parsing and compiling. Finite automata are simple models of computation. By studying the properties of these simple models, we hope to gain deeper insight into the nature of what can and cannot be computed.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
105829-2008
Name nom
Shallit, Jeffrey
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
2010
Competition year année de concours
2008
Award amount
41000
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
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
3
Nb partie
5
Application title
Descriptional complexity, combinatorics on words, formal languages and number theory
Keyword
NSERC
Application summary
I propose to investigate problems combining aspects of theoretical computer science, combinatorics, algebra, and number theory, along the lines of the topics in my recent monograph with Jean-Paul Allouche, ""Automatic Sequences: Theory, Applications, Generalizations"", published by Cambridge University Press in 2003. In particular, I plan to work on problems involving the topics of descriptional complexity, conbinatorics on words, formal languages, and finite automata. In descriptional complexity, we are concerned with how succinctly objects can be described (as opposed to the resource consumption of algorithms, which is the domain of computational complexity). The techniques used in this area are taken from algebra, number theory, and combinatorics, and problems frequently make use of deep results in these areas. Combinatorics on words is concerned with the properties of strings of symbols. For example, given two words, when do they ""commute"" (that is, read the same no matter which word is taken first)? Although of interest in its own right, recently there are also some applications to cryptography, where it is used in constructing hash functions resistant to certain kinds of attacks. Formal languages is the study of the mathematical properties of languages, which are sets of words. This area is of particular interest because of applications to parsing and compiling. Finite automata are simple models of computation. By studying the properties of these simple models, we hope to gain deeper insight into the nature of what can and cannot be computed.