Une des questions incontournables qu'on se pose en theorie des langages est de savoir
si une logique est decidable. Autrement dit, pour une logique donnee, on veut savoir
s'il existe un algorithme qui determine si un langage donne est exprimable dans cette
logique. Depuis les travaux de Schutzenberger, McNaughton et Papert sur la logique
de premier ordre sur les mots, on reconnait l'importance de la theorie algebrique des
langages pour resoudre ces questions de decidabilite.
Un autre exemple historique est la caracterisation 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 denir par une combinaison booleenne d'expressions
regulieres de la forme [symbol]. Ces langages sont exactement ceux
qui sont denis par la cl^oture booleenne de [symbol] et le theoreme de Simon engendre
un algorithme qui en resout la decidabilite.
Suite aux succes sur les mots, on a attaque les m^emes questions de decidabilite
de logiques sur les langages de for^ets, plus speciquement sur les langages d'arbres.
Dernierement, Bojanczyk, Segoun et Straubing ont pu demontrer un analogue du
theoreme de Simon pour les for^ets. En eet, ils ont pu caracteriser la cl^oture booleenne
de [symbol], c'est-a-dire les langages testables par morceaux, en fonction d'une structure
algebrique nommee algebre de for^ets.
Ce memoire est d'abord un etat de l'art de la theorie algebrique des langages testables
par morceaux. Entre autres, nous presentons le theoreme de Simon sur les mots en
passant par un resultat de Straubing et Therien qui utilise la theorie des monodes partiellement
ordonnes. Ensuite, nous etudions un pendant de ce resultat pour les algebres
de for^ets. Finalement, nous reglons la decidabilite des langages de mots bien emboîtes
testables par morceaux, une sous-classe des langages visiblement a pile. En efet, nous
proposons un algorithme qui utilise le resultat de Bojanczyk, Segoun et Straubing sur
les langages de for^ets.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QQLA.2011/27983 |
| Date | 05 1900 |
| Creators | Dubé, Maxime |
| Contributors | Tesson, Pascal |
| Publisher | Université Laval |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Rights | © Maxime Dubé, 2011 |
Page generated in 0.0017 seconds