Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Université de Sherbrooke

$20,000.00

Langages formels, algèbres finies et automates.

FY 2013-14

Summary
Les algèbres associatives (semigroupes et monoïdes) et non-associatives (groupoïdes, quasigroupes, boucles) permettent de modéliser la reconnaissance de langages de mots, c'est-à-dire de décider si un mot reçu en donnée appartient à un ensemble prédéterminé. De même, on utilise les algèbres généralisées et les algèbres de forêts pour les données bidimensionnelles hiérarchiques que sont les arbres et les forêts. L'étude des relations qui peuvent exister entre différentes classes (variétés) d'algèbres et de langages est un important domaine de recherche en informatique théorique. Le projet que je propose est axé sur deux directions de recherche. La première consiste à étudier la reconnaissance de langages de mots par des algèbres non-associatives ; cela permet d'établir des descriptions, en termes non-associatifs, de variétés de langages de mots qui avaient été définies en des termes très différents. La seconde direction de recherche consiste à faire un travail analogue avec les algèbres et langages de forêts. Je veux en particulier étudier une manière de construire des algèbres de forêts, le produit contexte, et les limites sur la puissance des algèbres qui peuvent être obtenus de la sorte, en comparant les langages de forêts qu'elles reconnaissent avec des variétés de langages déjà définies en termes de logique formelle ou de variétés de monoïdes.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
89786-2013
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
2013
Competition year année de concours
2013
Award amount
20000
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
1
Nb partie
5
Application title
Langages formels, algèbres finies et automates.
Keyword
NSERC
Application summary
Les algèbres associatives (semigroupes et monoïdes) et non-associatives (groupoïdes, quasigroupes, boucles) permettent de modéliser la reconnaissance de langages de mots, c'est-à-dire de décider si un mot reçu en donnée appartient à un ensemble prédéterminé. De même, on utilise les algèbres généralisées et les algèbres de forêts pour les données bidimensionnelles hiérarchiques que sont les arbres et les forêts. L'étude des relations qui peuvent exister entre différentes classes (variétés) d'algèbres et de langages est un important domaine de recherche en informatique théorique. Le projet que je propose est axé sur deux directions de recherche. La première consiste à étudier la reconnaissance de langages de mots par des algèbres non-associatives ; cela permet d'établir des descriptions, en termes non-associatifs, de variétés de langages de mots qui avaient été définies en des termes très différents. La seconde direction de recherche consiste à faire un travail analogue avec les algèbres et langages de forêts. Je veux en particulier étudier une manière de construire des algèbres de forêts, le produit contexte, et les limites sur la puissance des algèbres qui peuvent être obtenus de la sorte, en comparant les langages de forêts qu'elles reconnaissent avec des variétés de langages déjà définies en termes de logique formelle ou de variétés de monoïdes.