909 -- Langages rationnels. Exemples et applications. : Différence entre versions

De AgregmathKL
Aller à : navigation, rechercher
(→‎Développements possibles)
m
Ligne 10 : Ligne 10 :
 
#* Interprétation
 
#* Interprétation
 
#* Exemples
 
#* Exemples
−
#* Hauteur d'étoile \[ généralisé \]
+
#* Hauteur d'étoile (généralisé ... bof)
−
#* Langage de hauteur d'étoile <math>n</math>
+
#* Langage de hauteur d'étoile <math>n</math>  
 
# Équations
 
# Équations
 
#* Lemme d'ARDEN
 
#* Lemme d'ARDEN
Ligne 18 : Ligne 18 :
 
#* Décidabilité de l'équivalence
 
#* Décidabilité de l'équivalence
 
#* Exemple
 
#* Exemple
−
#* Règle de Saloma. <ref> Sylvain Schmidt </ref>
+
#* Le problème d'universalité est PSPACE-Complet (DEV)
 +
# Ordre sous-mot
 +
#* Définition, de l'ordre, des antichaînes (ensemble d'éléments incomparables deux à deux )
 +
#* Théorème de Higman et ses corollaires ( les sous-mots et les sur-mots d'un langage sont rationnels )
 +
 
 
=== II) Caractérisations ===
 
=== II) Caractérisations ===
 
# Théorème de Kleene
 
# Théorème de Kleene
−
# (Lemmes de l'étoile)
+
#* Dérivées d'Antimirov et résolutions d'équations par le lemme d'Arden
−
#* 3 versions.
+
# Lemme de l'étoile [Carton p. 54]
−
#* Caractérisation par le lemme de l'étoile par blocs appliqué au langage et à son complémentaire.
+
#* version par bloc
−
# Grammaire
+
#* Théorème (EPR) : Caractérisation par le lemme de l'étoile par blocs appliqué au langage et à son complémentaire.
 +
# Grammaire régulières
 
#* Caractérisation par les langages de grammaires linéaires gauches.
 
#* Caractérisation par les langages de grammaires linéaires gauches.
 
# Automate à Pile
 
# Automate à Pile
−
#* Le langage de Pile d'un automate à pile est reconnaissable  
+
#* Définition langage de Dyck et langage de Pile
−
=== III) Cas d'un monoïde quelconque ===
+
#* Le langage de Pile d'un automate à pile est reconnaissable (DEV)
−
<ref> O. Carton </ref>
+
# Reconnaissance par monoïde
−
# Définitions.
+
#* Définition
−
# Version faible du théorème de Kleene.
+
#* Théorème de caractérisation : reconnaissance par monoïde fini.
 +
#* Exemple
 +
#* Propriétés de stabilité par morphismes
 +
# Théorème de Myhill-Nérode [Carton p. 45]
 +
#* Définition résiduels
 
#* Exemples
 
#* Exemples
 +
#* Caractérisation par finitude du nombre de résiduels
 +
=== III) Cas d'un monoïde quelconque [Carton p. 72] ===
 +
# Définitions : Reconnaissance par monoïde fini, Rationalité...
 +
# Version faible du théorème de Kleene.
 +
#* Exemples et contre-exemples
 
=== IV) Applications ===
 
=== IV) Applications ===
−
# Arithmétique de Presburger.
 
 
# Analyse Lexicale.
 
# Analyse Lexicale.
 
#* Expressions régulières
 
#* Expressions régulières
 
#* Exemples de commandes...
 
#* Exemples de commandes...
−
# Séparation par automate.
+
#* Application à la compilation
  
 
== Développements possibles ==
 
== Développements possibles ==
−
# Caractérisation de la rationalité par le lemme de l'étoile par blocs (immonde)
+
# Le problème d'universalité d'un langage rationnel est PSPACE-dur
−
# Presburger
+
#* Le caractère PSPACE est admis pour des raisons de temps.
 
# Langage de Pile d'un Automate à Pile
 
# Langage de Pile d'un Automate à Pile
 +
# Caractérisation de la rationalité par le lemme de l'étoile par blocs (immonde)
 
# Théorème de Higman et corollaires :
 
# Théorème de Higman et corollaires :
 
#* Il n'existe pas d'antichaïne infinie pour l'ordre lexicographique sur le monoïde libre d'un alphabet fini.
 
#* Il n'existe pas d'antichaïne infinie pour l'ordre lexicographique sur le monoïde libre d'un alphabet fini.
 
#* Les surmots et sousmots pour l'ordre lexicographique d'un langage quelconque sont rationnels.
 
#* Les surmots et sousmots pour l'ordre lexicographique d'un langage quelconque sont rationnels.
−
#
+
# (Presburger)
−
# Séparation par automate
+
# (Séparation par automate)
 
#* Montré indécidable par réduction à 3-SAT
 
#* Montré indécidable par réduction à 3-SAT
  
 
== Références ==
 
== Références ==
−
Carton... "C'est mal de ne pas mettre quelque chose qui est dans le Carton, c'est mal de mettre quelque chose qui n'est pas dans le Carton."
+
Carton... "C'est mal de ne pas mettre quelque chose qui est dans le Carton, c'est mal de mettre quelque chose qui n'est pas dans le Carton." (D. Cachera)

Version du 30 octobre 2011 à 17:59

Plan de Kévin et Basile (2012)

Le Plan

I) Expressions Rationnelles

  1. Définitions
    • Par induction
    • Par récurrence et hauteur
  2. Sémantique
    • Interprétation
    • Exemples
    • Hauteur d'étoile (généralisé ... bof)
    • Langage de hauteur d'étoile n
  3. Équations
    • Lemme d'ARDEN
    • Pivot de GAUSS
  4. Réduction des expressions rationnelles
    • Décidabilité de l'équivalence
    • Exemple
    • Le problème d'universalité est PSPACE-Complet (DEV)
  5. Ordre sous-mot
    • Définition, de l'ordre, des antichaînes (ensemble d'éléments incomparables deux à deux )
    • Théorème de Higman et ses corollaires ( les sous-mots et les sur-mots d'un langage sont rationnels )

II) Caractérisations

  1. Théorème de Kleene
    • Dérivées d'Antimirov et résolutions d'équations par le lemme d'Arden
  2. Lemme de l'étoile [Carton p. 54]
    • version par bloc
    • Théorème (EPR) : Caractérisation par le lemme de l'étoile par blocs appliqué au langage et à son complémentaire.
  3. Grammaire régulières
    • Caractérisation par les langages de grammaires linéaires gauches.
  4. Automate à Pile
    • Définition langage de Dyck et langage de Pile
    • Le langage de Pile d'un automate à pile est reconnaissable (DEV)
  5. Reconnaissance par monoïde
    • Définition
    • Théorème de caractérisation : reconnaissance par monoïde fini.
    • Exemple
    • Propriétés de stabilité par morphismes
  6. Théorème de Myhill-Nérode [Carton p. 45]
    • Définition résiduels
    • Exemples
    • Caractérisation par finitude du nombre de résiduels

III) Cas d'un monoïde quelconque [Carton p. 72]

  1. Définitions : Reconnaissance par monoïde fini, Rationalité...
  2. Version faible du théorème de Kleene.
    • Exemples et contre-exemples

IV) Applications

  1. Analyse Lexicale.
    • Expressions régulières
    • Exemples de commandes...
    • Application à la compilation

Développements possibles

  1. Le problème d'universalité d'un langage rationnel est PSPACE-dur
    • Le caractère PSPACE est admis pour des raisons de temps.
  2. Langage de Pile d'un Automate à Pile
  3. Caractérisation de la rationalité par le lemme de l'étoile par blocs (immonde)
  4. Théorème de Higman et corollaires :
    • Il n'existe pas d'antichaïne infinie pour l'ordre lexicographique sur le monoïde libre d'un alphabet fini.
    • Les surmots et sousmots pour l'ordre lexicographique d'un langage quelconque sont rationnels.
  5. (Presburger)
  6. (Séparation par automate)
    • Montré indécidable par réduction à 3-SAT

Références

Carton... "C'est mal de ne pas mettre quelque chose qui est dans le Carton, c'est mal de mettre quelque chose qui n'est pas dans le Carton." (D. Cachera)

Récupérée de « https://minerve.ens-rennes.fr/index.php?title=909_--_Langages_rationnels._Exemples_et_applications.&oldid=340 »