Evènement pour le groupe Graphes et Logique


Date 2012-01-31  11:00-12:00
TitreLangages de tuiles MSO définissables, monoïdes quasi-inversifs et pré-homomorphismes  
RésuméNous présentons ici une tentative de caractérisation algébrique des langages de tuiles discrètes unidimensionnelles définissables en logique monadique du second ordre. Ce travail est motivé par les résultats suivants. On sait que la classe des langages de tuiles définissables en MSO est particulièrement robuste. Elle est close non seulement par opération booléenne et projection, mais aussi par produit, produit itéré et résidus à droite ou a gauche (pour les tuiles positives) ou inverse (pour les tuiles quelconques). On sait aussi que cette classe est particulièrement simple. Un langage de tuile est MSO définissable si et seulement si, c'est une somme fini de produit de la forme P x R x S avec P, R et S des langages rationnels de mots. On sait aussi que, au contraire, la classe des langages de tuiles reconnaissable par monoïde fini est particulièrement réduite. Elle correspond, en un sens, aux ensembles finis de mots bi-infinis de la forme (uv)^omega u(vu)*(vu)^omega pour u et v deux mots finis. La question posée est donc la suivante : comment affaiblir la notion de reconnaissabilité algébrique pour obtenir tous les langages de tuiles MSO définissable ? Pour répondre à cette question, nous sommes amenés à définir les monoïdes quasi-inversifs et à étudier, sur ces monoïdes, la notion de pré-homomorphisme. * Plus en détails: Pour cela, nous sommes amenés à définir la notion de monoïde quasi-inversif : une sorte de monoïde presque inversif au sens où on souhaite disposer des idempotents de la forme xy pour x et y inverse l'un de l'autre, mais dans lequel on ne requiert pas la présence des inverses eux-mêmes. Nous proposons une axiomatisation de ces monoïdes qui forment une sur-classe de la classe des monoïdes inversifs, dont nous étudions les propriétés. Nous montrons en particulier que, malgré l'absence d'inverse, on peut tout de même y définir un ordre naturel qui conserve un certain nombre des bonnes propriétés de l'ordre naturel sur les monoïdes inversifs. Nous démontrons alors un théorème d'expansion permettant de construire, à partir de tout monoïde (fini) S, un monoïde quasi-inversif (fini) Q(S) dont S est (isomorphe à) un sous-monoïde. Fait curieux, ce résultat implique en particulier que, contrairement aux monoïdes inversifs, dans les monoïdes quasi-inversifs, il n'est pas toujours vrai que les idempotents commutent. La théorie des monoïdes quasi-inversifs n'est donc pas une sous théorie triviale de celle des monoïdes inversifs. Les propriétés spécifiques de cette expansion, bien plus nombreuses que celles des monoïdes quasi-inversifs quelconques sont présentées. En particulier, alors que l'ordre naturel sur un monoïde quasi-inversif n'est pas, en général, compatible avec le produit, c'est par contre le cas pour tout monoïde quasi-inversif de la forme Q(S). On montre aussi que le monoïde des tuiles positives (sous-monoïde quasi-inversif du monoïde de McAlster) sur un alphabet A se plonge dans Q(A^*) : l'expansion quasi-inversive du monoïde libre A^*. Pour définir une notion de reconnaissabilité raisonablement puissante on propose alors de considerer des pré-homomorphismes c'est-à-dire des fonctions monotones (vis à vis de l'ordre naturel) qui ne sont que sous-additives pour le produit, i.e. des fonctions f : S -> T telles que pour tout x et y de S, si x <= y alors f(x) <= f(y) et f(xy) <= f(x) f(y). Nous montrons alors que pour tout morphisme f : A^* -> S peut-être étendu en un pré-homomorphisme de Q(A^*) dans Q(S). Ce denier résultat, qui pourrait conduire à une notion (quasi-)algébrique de reconnaissabilité caractérisant les langages MSO définissables de tuiles positive, est alors étudié. 
Lieusalle 75 
OrateurDavid Janin 
Emaildavid.janin@labri.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index