Grant: Discovery Grants Program - Individual
Simon Fraser University
$22,000.00
Applied Analytic Combinatorics
EF 2015-16
Résumé
Combinatorial structures arising as discrete mathematical models of physical phenomena are increasingly found lurking at the interface of mathematics and other sciences, particularly physics, biology and computer science. The simplicity of the structures is deceptive, as they are often sufficiently rich to play a key role in our understanding of the underlying phenomena being studied. Analytic combinatorics is a rapidly advancing area of theory which studies combinatorial families and their properties using complex analysis and algebra. A central feature of this theory is its algorithmic and generic nature.
This research program considers several problems in the domain of statistical mechanics, genomics and theoretical computer science, and to each addresses questions well adapted to analytic combinatorics: solvability; enumeration and parameter distribution; and random generation. Three applications act as conduits of study: (I) lattice path enumeration; (II) tree models of permutations; and (III) RNA secondary structures.
The questions take the form of ""Do we expect a particular polymer to have this shape?"" ""What is a typical evolution scenario between two mammals and their common ancestor?"" and ""How often should this folding structure occur in an RNA strand of this length?"". Ideally, we then compare results to actual data in order to gauge the quality of the model. Random generation allows us to form and test hypotheses, to determine the practical complexity of related algorithms, and to assess the quality of the data.
The results for each application inform a larger study of combinatorial structures:we are interested in the meta classification of combinatorial classes by some notion of complexity. This augments the classical Chomsky Hierarchy of formal languages.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
312582-2012
Name nom
Mishna, Marni
Department département
Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2012
Award amount
22000
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
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
4
Nb partie
5
Application title
Applied Analytic Combinatorics
Keyword
NSERC
Application summary
Combinatorial structures arising as discrete mathematical models of physical phenomena are increasingly found lurking at the interface of mathematics and other sciences, particularly physics, biology and computer science. The simplicity of the structures is deceptive, as they are often sufficiently rich to play a key role in our understanding of the underlying phenomena being studied. Analytic combinatorics is a rapidly advancing area of theory which studies combinatorial families and their properties using complex analysis and algebra. A central feature of this theory is its algorithmic and generic nature.
This research program considers several problems in the domain of statistical mechanics, genomics and theoretical computer science, and to each addresses questions well adapted to analytic combinatorics: solvability; enumeration and parameter distribution; and random generation. Three applications act as conduits of study: (I) lattice path enumeration; (II) tree models of permutations; and (III) RNA secondary structures.
The questions take the form of ""Do we expect a particular polymer to have this shape?"" ""What is a typical evolution scenario between two mammals and their common ancestor?"" and ""How often should this folding structure occur in an RNA strand of this length?"". Ideally, we then compare results to actual data in order to gauge the quality of the model. Random generation allows us to form and test hypotheses, to determine the practical complexity of related algorithms, and to assess the quality of the data.
The results for each application inform a larger study of combinatorial structures:we are interested in the meta classification of combinatorial classes by some notion of complexity. This augments the classical Chomsky Hierarchy of formal languages.