Sur la réalisation des monoïdes comme monoides syntaxiques des langues

Soit $L \subseteq X^{\ast}$ un langage, puis nous définissons la congruence syntaxique comme

u \sim v :\Leftrightarrow \forall x, y \in X^{*} : x u y \in L \leftrightarrow x v y \in L

$u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L$ et le quotient monoïde est appelé monoïde syntaxique de .

X^{*} / \sim_{L}

$X^{\ast} / \sim_L$

L

$L$

Maintenant, quels monoïdes surgissent en tant que monoides syntaxiques des langues? J'ai trouvé des langues pour les groupes symétriques et pour l'ensemble de tous les mappages sur un ensemble fini sous-jacent. Mais qu'en est-il des autres, y a-t-il des monoïdes finis qui ne pourraient pas être écrits comme le monoïde syntaxique d'une langue?

Pour un automate donné, en considérant le monoïde généré par les mappages induits par les lettres sur les états (le soi-disant monoïde de transformation) lorsque la composition de la fonction est lue de gauche à droite, il considère que le monoïde de transformation de l'automate minimal est précisément le monoïde syntaxique. Cette observation m'a aidé à construire les exemples mentionnés ci-dessus.

Permettez-moi également de ne pas dire qu'il est assez simple de réaliser un monoïde fini comme le monoïde de transformation d'un automate, simplement prendre les éléments de comme états, et considérer chaque générateur de comme une lettre de l'alphabet et les transitions sont données par pour un état et une lettre , alors le monoïde de transformation est isomorphe à lui-même (ceci est similaire au théorème de Cayley sur la façon dont les groupes s'intègrent dans des groupes symétriques). $M$ $M$ $M$ $qx$ $q$ $x$ $M$

fl.formal-languages automata-theory regular-language algebra monoid StefanH
la source

Que signifie le terme «langue» dans ce contexte? Un submonoïde, peut-être? Éditer. Eh bien, je suppose que non, car cela signifierait que a toujours été la relation d'égalité. Ce sont peut-être des sous-ensembles arbitraires?

\sim

$\sim$

gobelin

@goblin Un langage n'est qu'un sous-ensemble arbitraire de

(c'est-à-dire un ensemble de séquences finies, ou le monoïde libre); ils codent des mots.

X^{*}

$X^{\ast}$

StefanH

Merci. Je commençais à supposer autant. Y a-t-il un lien entre ce que vous faites ici et le groupe de quotients

où

est un sous-groupe normal d'un groupe

? Quoi qu'il en soit, cela semble très cool.

G / N

$G/N$

N

$N$

G

$G$

gobelin

@goblin Si vous cherchez une analogie

avec

, alors je ne vois pas de relation directe simplement alors la relation abstraite de formation de structures factorielles (et donc d'induction de morphismes canoniques); mais il existe d'autres façons pour les groupes d'entrer dans l'image ici, par exemple le monoïde syntaxique pourrait être un groupe, ou

pourrait également être un groupe (ce qui généralise la notion de groupes automatiques, je suppose, mais je ne suis pas un expert ici). Je vous suggère d'ouvrir un nouveau message si vous êtes intéressé par la façon dont les groupes pourraient entrer sur la scène ici!

X^{*}

$X^{\ast}$

\sim

$\sim$

G

$G$

N

$N$

L

$L$

StefanH

@goblin Peut-être une autre analogie qui, à certains égards, pourrait être familière au théoricien de groupe: étant donné un langage

nous pouvons former un automate (pas nécessairement fini!) pour accepter

(par exemple avec les bonnes classes de nerode). Maintenant , si

représente les états, nous avons une action

, ce qui donne une cartographie

. Maintenant, le noyau de cette action en tant que relation de congruence affine

d'en haut comme

L

$L$

L

$L$

Q

$Q$

Q \times X^{*} \to Q

$Q \times X^{\ast} \to Q$

X^{*} \to Q^{Q}

$X^{\ast} \to Q^Q$

\sim

$\sim$

q_{0} \cdot x u y = q_{0} \cdot x v y

$q_0\cdot xuy = q_0\cdot xvy$ ensuite (mais simplement

peut les envoyer à différents états finaux, il peut donc affiner correctement

u \sim v

$u\sim v$

\sim

$\sim$

StefanH

Réponses:

Il semble qu'il y ait un document de répondre à cette question précise, et même dans le cas plus général des langues réguliers réguliers, mais je ne peux pas trouver une version en libre accès. Si quelqu'un trouve un lien sans mur payant, ce serait bien. J'ai demandé le texte intégral sur ResearchGate. $\omega$

Titre : Quels monoïdes finis sont des monoïdes syntaxiques d'oméga-langages rationnels .

Auteurs : Phan Trung Huy, Igor Litovsky, Do Long Van

Résumé : Une notion d'ensembles rigid-rigides pour un monoïde fini est introduite. Nous prouvons qu'un monoïde fini M est le monoïde syntaxique d'Arnold d'un langage rational rationnel (ω-syntaxique pour faire court) si et seulement s'il existe un ensemble ω-rigide pour M. Cette propriété se révèle décidable pour les monoïdes finis . La relation entre la famille des monoïdes ω-syntaxiques et celle des mono-ids-syntaxiques (c'est-à-dire les monoides syntaxiques des langages rationnels des mots finis) est établie.

De plus, la page wikipedia sur les monoides syntaxiques déclare:

Chaque monoïde fini est homomorphe au monoïde syntaxique d'un langage non trivial [1], mais tous les monoïdes finis ne sont pas isomorphes à un monoïde syntaxique [2].
Chaque groupe fini est isomorphe au monoïde syntaxique d'un langage non trivial. [1]

[1] McNaughton, Robert; Papert, Seymour (1971). Automates sans compteur. Monographie de recherche 65. Avec une annexe de William Henneman. MIT Appuyez sur. p. 48. ISBN 0-262-13076-9. Zbl 0232.94024.

[2] Lawson (2004) p.233

Denis
la source

Que signifie "homomorphe à"? Autrement dit, dans quelle direction va l'homomorphisme, et doit-il être surjectif?

Emil Jeřábek 3.0

Cela signifie que tout monoïde fini est un sous-monoïde d'un monoïde syntaxique. Ceci est confirmé dans kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1437-2.pdf

Denis

Juste une note: les publications RIMS des réunions du groupe automates ne sont généralement pas référencées. Faites donc attention au contenu, si vous ne pouvez pas le vérifier vous-même.

Peter Leupold

D'une manière plus élémentaire que la réponse de Denis, ce qui suit est extrait des "Théories de la calculabilité" de Pippenger, p.87, et immédiat à vérifier.

Définition: Soit un monoïde, et . Définissez la relation de congruence sur par ssi , . $M$ $Y \subseteq M$ $\equiv_Y$ $M$ $x \equiv_Y y$ $\big[\forall w, z \in M$ $wxz \in Y \Leftrightarrow wyz \in Y\big]$

$M$ $Y \subseteq M$ $x \equiv_Y y \Rightarrow x = y$ $x, y \in M$ $M \approx M/\equiv_Y$

$M$

Michaël Cadilhac
la source

$P$ $M$ $P$ $M$

$\{1, a, b, c\}$ $1$ $xy = y$ $x, y \in \{a,b,c\}$

J.-E. Épingle
la source