O realizacji monoidów jako syntaktycznych monoidów języków

Niech będzie jakimś językiem, a następnie zdefiniujemy spójność syntaktyczną jako u ∼ v : ⇔ ∀ x , y ∈ X ∗ : x u y ∈ L ↔ x v y ∈ L i iloraz monoidu X ∗ / ∼ L wynosi nazywany składniowym monoid z L .$L \subseteq X^{\ast}$

Jakie monoidy powstają jako monoidy syntaktyczne języków? Znalazłem języki dla grup symetrycznych i dla zestawu wszystkich odwzorowań na pewnym podstawowym zestawie skończonym. Ale co z innymi, czy istnieją skończone monoidy, których nie można zapisać jako składniową monoidę jakiegoś języka?

Dla danego automatu, biorąc pod uwagę monoid wygenerowany przez odwzorowania wywołane literami stanów (tzw. Monoid transformacji), gdy skład funkcji jest odczytywany od lewej do prawej, utrzymuje, że monoid transformacji automatu minimalnego jest dokładnie monoid składniowy. Ta obserwacja pomogła mi w skonstruowaniu wyżej wymienionych przykładów.

Nie pozwól też, że bardzo łatwo jest zrealizować dowolną skończoną monoidę jako monoid transformacji jakiegoś automatu, po prostu weź elementy M jako stany i rozważ każdy generator M jako literę alfabetu, a przejścia są podane przez q x dla pewnego stanu q i litery x , wówczas monoid transformacji jest izomorficzny do samego M (jest to podobne do twierdzenia Cayleya o tym, jak grupy osadzają się w grupach symetrycznych).$M$$M$$M$$qx$$q$$x$$M$

$\omega$

Tytuł : Które skończone monoidy są syntaktycznymi monoidami racjonalnych języków omega .

Autorzy : Phan Trung Huy, Igor Litowski, Do Long Van

Streszczenie : Wprowadzono pojęcie zestawów sztywnych dla skończonej monoidu. Udowadniamy, że skończona monoid M jest syntaktyczną monoidą Arnolda jakiegoś racjonalnego języka ω (w skrócie ω-syntaktyczny) wtedy i tylko wtedy, gdy istnieje zestaw sztywny ω dla M. Ta właściwość jest rozstrzygalna dla skończonych monoidów . Ustalono związek między rodziną monoidów ω-syntaktycznych a monoidami ∗-syntaktycznymi (tj. Monoidami syntaktycznymi racjonalnych języków słów skończonych).

Dodatkowo strona wikipedia o syntaktycznych monoidach stwierdza:

• Każdy skończony monoid jest homomorficzny w stosunku do monoidu syntaktycznego w jakimś nietrywialnym języku [1], ale nie każdy skończony monoid jest izomorficzny w stosunku do monoidu syntaktycznego [2]
• Każda grupa skończona jest izomorficzna w składniowej monoidie jakiegoś nietrywialnego języka. [1]

[1] McNaughton, Robert; Papert, Seymour (1971). Liczniki automatyczne. Monografia badawcza 65. Z dodatkiem Williama Hennemana. MIT Naciśnij. p. 48. ISBN 0–262–13076–9. Zbl 0232.94024.

[2] Lawson (2004) s. 233

W bardziej elementarny sposób niż odpowiedź Denisa, z „Teorii obliczalności” Pippengera, str. 87, wyciągnięto następujący tekst i natychmiast sprawdzono.

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

$M$

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

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