Sobre a realização de monóides como monóides sintáticos de línguas

Seja uma linguagem, então definimos a congruência sintática como e o quociente monoid é chamado o monoid sintática 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$

Agora, quais monoides surgem como monoides sintáticos de idiomas? Encontrei idiomas para grupos simétricos e para o conjunto de todos os mapeamentos em algum conjunto finito subjacente. Mas e quanto a outros, existem monóides finitos que não poderiam ser escritos como o monóide sintático de alguma linguagem?

Para um dado autômato, considerando o monóide gerado pelos mapeamentos induzidos pelas letras nos estados (o chamado monóide de transformação) quando a composição da função é lida da esquerda para a direita, sustenta que o monóide de transformação do autômato mínimo é precisamente o monóide sintático. Essa observação me ajudou a construir os exemplos mencionados acima.

Não me permita também que seja bastante simples perceber qualquer monóide finito como o monóide de transformação de algum autômato, simplesmente pegue os elementos de como estados e considere cada gerador de como uma letra do alfabeto e as transições são dadas por para algum estado e letra , o monóide de transformação é isomórfico ao próprio (isso é semelhante ao teorema de Cayley sobre como os grupos se incorporam em grupos simétricos). $M$ $M$ $M$ $qx$ $q$ $x$ $M$

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

O que o termo "linguagem" significa neste contexto? Um submonóide, talvez? Editar. Bem, acho que não, pois isso significaria que sempre foi a relação de igualdade. Talvez eles sejam subconjuntos arbitrários?

\sim

$\sim$

goblin

@goblin Uma linguagem é apenas um subconjunto arbitrário de (isto é, conjunto de seqüências finitas ou o monóide livre); eles codificam palavras.

X^{*}

$X^{\ast}$

StefanH

Obrigado. Eu estava começando a supor isso. Existe alguma conexão entre o que você está fazendo aqui e o grupo de quocientes que é um subgrupo normal de um grupo ? De qualquer forma, isso parece muito legal.

G / N

$G/N$

N

$N$

G

$G$

Goblin

@ goblin Se você está procurando uma analogia e para

, então não vejo nenhuma relação direta apenas com a abstrata de formar estruturas fatoriais (e, portanto, induzir morfismos canônicos); mas há outras maneiras pelas quais os grupos podem entrar em cena aqui, por exemplo, o monóide sintático pode ser um grupo, ou

também pode ser um grupo (o que generaliza a noção de grupos automáticos, eu acho, mas não sou especialista aqui). Sugiro que você abra um novo post se estiver interessado em saber como os grupos podem entrar no palco aqui!

X^{*}

$X^{\ast}$

\sim

$\sim$

G

$G$

N

$N$

L

$L$

StefanH

@goblin Talvez outra analogia que, de certa forma, possa ser familiar para o teórico dos grupos: Dada uma linguagem

, possamos formar um autômato (não necessariamente finito!) para aceitar

(por exemplo, com as classes corretas nerode). Agora, se

denota os estados, então nós temos uma ação

, que dá um mapeamento

. Agora o núcleo desta ação como uma relação de congruência refina

de cima 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$ em seguida, (mas apenas

pode enviá-los para diferentes estados finais, daí ele pode corretamente refinar

u \sim v

$u\sim v$

\sim

$\sim$

StefanH

Respostas:

Parece que há um papel de responder a esta pergunta exata, e mesmo no caso mais geral de línguas -Regular, mas não consigo encontrar uma versão de acesso aberto. Se alguém encontrar um link sem paywall, seria ótimo. Solicitei o texto completo no ResearchGate. $\omega$

Título : Quais monóides finitos são monóides sintáticos das línguas ômega-racional .

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

Resumo : Uma noção de conjuntos ω-rígidos para um monóide finito é introduzida. Provamos que um monóide finito M é o monóide sintático de Arnold de alguma linguagem ω racional (ω-sintática para abreviar) se e somente se existir um conjunto ω-rígido para M. Essa propriedade é mostrada como determinável para os monóides finitos . A relação entre a família de monóides ω-sintáticos e a dos monoides ∗-sintáticos (isto é, os monóides sintáticos de linguagens racionais de palavras finitas) é estabelecida.

Além disso, a página da Wikipedia sobre monóides sintáticos afirma:

Todo monóide finito é homomórfico ao monóide sintático de alguma linguagem não trivial, [1] mas nem todo monóide finito é isomórfico a um monóide sintático. [2]
Todo grupo finito é isomórfico ao monóide sintático de alguma linguagem não trivial. [1]

[1] McNaughton, Robert; Papert, Seymour (1971). Autômatos sem contador. Monografia de pesquisa 65. Com um apêndice de William Henneman. MIT Pressione. p. 48. ISBN 0-262-13076-9. Zbl 0232.94024.

[2] Lawson (2004), p.

Denis
fonte

O que significa "homomórfico para"? Ou seja, em qual direção o homomorfismo vai e é necessário que seja um adjetivo?

Emil Jeřábek apoia Monica

Isso significa que qualquer monóide finito é um submonóide de um monóide sintático. Isso é confirmado em kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1437-2.pdf

Denis

Apenas uma observação: as publicações RIMS das reuniões do grupo de autômatos geralmente não são arbitradas. Portanto, tenha cuidado com o conteúdo, se você não puder verificá-lo.

precisa

De uma maneira mais elementar que a resposta de Denis, o seguinte é extraído de "Theories of Computability" de Pippenger, p.87, e verificação imediata.

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

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

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

J.-E. PIN
fonte