Grant: Discovery Grants Program - Individual
Université de Sherbrooke
$18,000.00
Langages formels, groupoïdes et automates
EF 2012-13
Résumé
Mon projet porte sur les algèbres finies (associatives: groupes, semigroupes et monoïdes; non-associatives: quasigroupes, boucles et groupoïdes), leurs propriétés en ce qui a trait à la reconnaissance de langages, et leurs applications potentielles dans d'autres domaines de l'informatique théorique.
En ce qui concerne la reconnaissance de langages, mon effort principal porte actuellement sur les boucles. Ces algèbres sont exactement celles qui ont un élément neutre et dont la table est un carré latin, c'est à dire que chaque ligne et chaque colonne de la table est une permutation des éléments de la boucle. Les boucles finies fournissent une caractérisation originale d'une classe de langages, les ouverts réguliers, qui ont été définis dans un contexte totalement différent. Je travaille actuellement sur des cas particuliers de boucles particulièrement intéressants qui sont apparus au cours de mes recherches antérieures.
Une des applications auxquelles je m'intéresse présentement est le modèle des automates quantiques, qui combine les propriétés du calcul quantique avec la relative simplicité du modèle des automates finis. Diverses questions sont ouvertes dans ce domaine. Une des possibilités de recherche consiste à explorer la question de la taille que doit avoir un automate pour être capable de reconnaître un langage donné. Ceci fait suite à des résultats qui montrent que, pour certains langages, on peut utiliser des automates quantiques exponentiellement plus petits que leurs contreparties classiques, alors que dans d'autres cas c'est l'automate quantique qui est exponentiellement plus gros que son équivalent classique.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
89786-2008
Name nom
Beaudry, Martin
Department département
Sciences, Faculté des
Organization id
68
Institution établissement
Université de Sherbrooke
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2008
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
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
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
5
Nb partie
5
Application title
Langages formels, groupoïdes et automates
Keyword
NSERC
Application summary
Mon projet porte sur les algèbres finies (associatives: groupes, semigroupes et monoïdes; non-associatives: quasigroupes, boucles et groupoïdes), leurs propriétés en ce qui a trait à la reconnaissance de langages, et leurs applications potentielles dans d'autres domaines de l'informatique théorique.
En ce qui concerne la reconnaissance de langages, mon effort principal porte actuellement sur les boucles. Ces algèbres sont exactement celles qui ont un élément neutre et dont la table est un carré latin, c'est à dire que chaque ligne et chaque colonne de la table est une permutation des éléments de la boucle. Les boucles finies fournissent une caractérisation originale d'une classe de langages, les ouverts réguliers, qui ont été définis dans un contexte totalement différent. Je travaille actuellement sur des cas particuliers de boucles particulièrement intéressants qui sont apparus au cours de mes recherches antérieures.
Une des applications auxquelles je m'intéresse présentement est le modèle des automates quantiques, qui combine les propriétés du calcul quantique avec la relative simplicité du modèle des automates finis. Diverses questions sont ouvertes dans ce domaine. Une des possibilités de recherche consiste à explorer la question de la taille que doit avoir un automate pour être capable de reconnaître un langage donné. Ceci fait suite à des résultats qui montrent que, pour certains langages, on peut utiliser des automates quantiques exponentiellement plus petits que leurs contreparties classiques, alors que dans d'autres cas c'est l'automate quantique qui est exponentiellement plus gros que son équivalent classique.