Sobre la realización de monoides como monoides sintácticos de idiomas

Let ser un lenguaje, entonces definimos la congruencia sintáctica como y el cociente monoid es llamado el monoide sintáctica de . $L \subseteq X^{\ast}$

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$

X^{*} / \sim_{L}

$X^{\ast} / \sim_L$

L

$L$

Ahora, ¿qué monoides surgen como monoides sintácticos de idiomas? Encontré idiomas para grupos simétricos y para el conjunto de todas las asignaciones en algún conjunto finito subyacente. Pero, ¿qué hay de otros? ¿Hay monoides finitos que no podrían escribirse como el monoide sintáctico de algún idioma?

Para un autómata dado, al considerar el monoide generado por las asignaciones inducidas por las letras en los estados (el llamado monoide de transformación) cuando la composición de la función se lee de izquierda a derecha, sostiene que el monoide de transformación del autómata mínimo es precisamente el monoide sintáctico Esta observación me ayudó a construir los ejemplos mencionados anteriormente.

No me permito tampoco que sea bastante simple realizar cualquier monoide finito como el monoide de transformación de algún autómata, simplemente tome los elementos de como estados y considere cada generador de como una letra del alfabeto y las transiciones se dan por para algún estado y letra , entonces el monoide de transformación es isomorfo a sí mismo (esto es similar al teorema de Cayley sobre cómo los grupos se integran en grupos simétricos). $M$ $M$ $M$ $qx$ $q$ $x$ $M$

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

¿Qué significa el término "lenguaje" en este contexto? ¿Un submonoide, tal vez? Editar. Bueno, supongo que no, ya que esto significaría que

siempre fue la relación de igualdad. ¿Quizás son subconjuntos arbitrarios?

\sim

$\sim$

duende

@goblin Un lenguaje es solo un subconjunto arbitrario de

(es decir, un conjunto de secuencias finitas o el monoide libre); codifican palabras.

X^{*}

$X^{\ast}$

StefanH

Gracias. Estaba empezando a suponer lo mismo. ¿Hay alguna conexión entre lo que está haciendo aquí y el grupo de cocientes

donde

es un subgrupo normal de un grupo

? De cualquier manera, esto parece muy bueno.

G / N

$G/N$

N

$N$

G

$G$

duende

@goblin Si está buscando una analogía

con

, entonces no veo ninguna relación directa sino simplemente la abstracta de las estructuras de factores formadores (y, por lo tanto, induce morfismos canónicos); pero hay otras formas en que los grupos podrían ingresar a la imagen aquí, por ejemplo, el monoide sintáctico podría ser un grupo, o

también podría ser un grupo (lo que generaliza a la noción de grupos automáticos, supongo, pero no soy un experto aquí). ¡Te sugiero que abras una nueva publicación si estás interesado en cómo los grupos podrían entrar al escenario aquí!

X^{*}

$X^{\ast}$

\sim

$\sim$

G

$G$

N

$N$

L

$L$

StefanH

@goblin Tal vez otra analogía que de alguna manera pueda ser familiar para el teórico de grupos: dado un lenguaje

, podemos formar un autómata (¡no necesariamente finito!) para aceptar

(por ejemplo, con las clases correctas nerode). Ahora bien, si

denota los estados, entonces tenemos una acción

, lo que da un mapeo

. Ahora el núcleo de esta acción como una relación de congruencia refina

desde arriba como

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$ entonces (pero simplemente

puede enviarlos a diferentes estados finales, por lo tanto, puede refinar adecuadamente

u \sim v

$u\sim v$

\sim

$\sim$

StefanH

Respuestas:

Parece que hay un documento que responde a esta pregunta exacta, e incluso en el caso más general de los idiomas regulares , pero no puedo encontrar una versión de acceso abierto. Si alguien encuentra un enlace sin paywall, sería genial. Solicité el texto completo en ResearchGate. $\omega$

Título : ¿Qué monoides finitos son monoides sintácticos de lenguajes omega racionales ?

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

Resumen : Se introduce una noción de conjuntos rigid-rígidos para un monoide finito. Demostramos que un monoide finito M es el monoide sintáctico de Arnold de algún lenguaje ω racional (ω-sintáctico para abreviar) si y solo si existe un conjunto rigid-rígido para M. Esta propiedad se muestra como decidible para los monoides finitos . Se establece la relación entre la familia de los monoides sy-sintácticos y la de los monoides ∗-sintácticos (es decir, los monoides sintácticos de lenguajes racionales de palabras finitas).

Además, la página de Wikipedia sobre monoides sintácticos dice:

Cada monoide finito es homomórfico al monoide sintáctico de algún lenguaje no trivial, [1] pero no todo monoide finito es isomorfo a un monoide sintáctico. [2]
Cada grupo finito es isomorfo al monoide sintáctico de algún lenguaje no trivial. [1]

[1] McNaughton, Robert; Papert, Seymour (1971). Autómatas sin mostrador. Monografía de investigación 65. Con un apéndice de William Henneman. MIT Press. pag. 48. ISBN 0-262-13076-9. Zbl 0232.94024.

[2] Lawson (2004) p.233.

Denis
fuente

¿Qué significa "homomórfico"? Es decir, ¿en qué dirección va el homomorfismo, y se requiere que sea sobreyectivo?

Emil Jeřábek apoya a Monica el

Significa que cualquier monoide finito es un submonoide de un monoide sintáctico. Esto se confirma en kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1437-2.pdf

Denis

Solo una nota: las publicaciones RIMS de las reuniones grupales de autómatas generalmente no son arbitradas. Así que tenga cuidado con los contenidos, si no puede verificarlos usted mismo.

Peter Leupold

De una manera más elemental que la respuesta de Denis, lo siguiente se extrae de las "Teorías de la computabilidad" de Pippenger, p.87, y se comprueba inmediatamente.

$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
fuente

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

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

J.-E. Alfiler
fuente