Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2011-2012 / 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.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/22493 |
| Date | 17 April 2018 |
| Creators | Dubé, Maxime |
| Contributors | Tesson, Pascal |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | mémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise |
| Format | 143 p., application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0027 seconds