Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Carleton University

$17,000.00

Automata in semigroup theory, group theory and analysis

EF 2010-11

Résumé
Finite state automata are a fundamental model of computation in theoretical computer science. They are used both as machines to recognize regular languages, and as machines to transform input strings into output strings. They also play a key role in compilers of computing languages. In addition, automata form a basic building block for more complicated models of computation. Automata theory has also found many applications in pure mathematics. Applications can be found in such diverse areas of mathematics as: group theory, semigroup theory, symbolic dynamics and holomorphic dynamics. I propose to explore several aspects of the theory of automata. The first aspect is Krohn-Rhodes theory, which concerns decomposing automata into their simplest possible parts. Krohn-Rhodes complexity measures the number of group parts needed in such a decomposition and I am looking for a way to compute this. Groups whose elements consist of automata have recently played a role in the theory of self-similar groups and their relationship with fractals. This proposal also suggests doing some work in this direction. Such groups may also lead to a way to generate new expander graphs, which have applications in telecommunication networks. Algorithmic problems concerning formal languages plays a major role in automata theory, especially in computer science applications. A typical question is of the sort: given a class of formal languages and given an operator on formal languages, does the class resulting from applying this operator still have decidable membership? There are also questions related to logical description of languages and hierarchies of regular languages.
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
262403-2007
Name nom
Steinberg, Benjamin
Department département
Mathematics and Statistics, School of
Organization id
23
Institution établissement
Carleton University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2007
Award amount
17000
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
336
Committee name en
Pure & Applied Maths - A
Committee name fr
Maths pures et appliquées - A
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
2908
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Algebra
Research subject fr
algèbre
Partie
4
Nb partie
5
Application title
Automata in semigroup theory, group theory and analysis
Keyword
NSERC
Application summary
Finite state automata are a fundamental model of computation in theoretical computer science. They are used both as machines to recognize regular languages, and as machines to transform input strings into output strings. They also play a key role in compilers of computing languages. In addition, automata form a basic building block for more complicated models of computation. Automata theory has also found many applications in pure mathematics. Applications can be found in such diverse areas of mathematics as: group theory, semigroup theory, symbolic dynamics and holomorphic dynamics. I propose to explore several aspects of the theory of automata. The first aspect is Krohn-Rhodes theory, which concerns decomposing automata into their simplest possible parts. Krohn-Rhodes complexity measures the number of group parts needed in such a decomposition and I am looking for a way to compute this. Groups whose elements consist of automata have recently played a role in the theory of self-similar groups and their relationship with fractals. This proposal also suggests doing some work in this direction. Such groups may also lead to a way to generate new expander graphs, which have applications in telecommunication networks. Algorithmic problems concerning formal languages plays a major role in automata theory, especially in computer science applications. A typical question is of the sort: given a class of formal languages and given an operator on formal languages, does the class resulting from applying this operator still have decidable membership? There are also questions related to logical description of languages and hierarchies of regular languages.