Pour savoir comment effectuer et gérer un dépôt de document, consultez le « Guide abrégé – Dépôt de documents » sur le site Web de la Bibliothèque. Pour toute question, écrivez à corpus@ulaval.ca.
 

Personne :
Dubé, Maxime

En cours de chargement...
Photo de profil

Adresse électronique

Date de naissance

Projets de recherche

Structures organisationnelles

Fonction

Nom de famille

Dubé

Prénom

Maxime

Affiliation

Université Laval. Faculté des sciences et de génie

ISNI

ORCID

Identifiant Canadiana

ncf13722777

person.page.name

Résultats de recherche

Voici les éléments 1 - 1 sur 1
  • PublicationAccès libre
    Les langages testables par morceaux
    (2011) Dubé, Maxime; Tesson, Pascal
    Une des questions incontournables qu'on se pose en théorie des langages est de savoir si une logique est décidable. Autrement dit, pour une logique donnée, on veut savoir s'il existe un algorithme qui détermine si un langage donné est exprimable dans cette logique. Depuis les travaux de Schützenberger, McNaughton et Papert sur la logique de premier ordre sur les mots, on reconnait l'importance de la théorie algébrique des langages pour résoudre ces questions de décidabilité. Un autre exemple historique est la caractérisation de Simon des langages testables par morceaux de mots par les monodes J -triviaux. On dit qu'un langage est testable par morceaux si on peut le définir par une combinaison booléenne d'expressions régulieres de la forme [symbol]. Ces langages sont exactement ceux qui sont définis par la clôture booléenne de [symbol] et le théorème de Simon engendre un algorithme qui en resout la décidabilité. Suite aux succès sur les mots, on a attaque les mêmes questions de décidabilité de logiques sur les langages de forêts, plus spéciquement sur les langages d'arbres. Dernièrement, Bojanczyk, Segoufin et Straubing ont pu démontrer un analogue du théorème de Simon pour les forêts. En effet, ils ont pu caractériser la clôture booléenne de [symbol], c'est-à-dire les langages testables par morceaux, en fonction d'une structure algébrique nommée algèbre de forêts. Ce mémoire est d'abord un état de l'art de la théorie algébrique des langages testables par morceaux. Entre autres, nous présentons le théorème de Simon sur les mots en passant par un résultat de Straubing et Thérien qui utilise la théorie des monodes partiellement ordonnés. Ensuite, nous étudions un pendant de ce résultat pour les algèbres de forêts. Finalement, nous règlons la décidabilité des langages de mots bien emboîtés testables par morceaux, une sous-classe des langages visiblement à pile. En efet, nous proposons un algorithme qui utilise le résultat de Bojanczyk, Segoufin et Straubing sur les langages de forêts.