Uogólnienie stwierdzenia, że ​​monoid rozpoznaje język iff monoid syntaktyczny dzieli monoid

Pozwolić $A$być skończonym alfabetem. Dla danego języka składniowym monoid jest dobrze znanym pojęciem w teorii język form. Co więcej, monoid rozpoznaje język jeśli istnieje morfizm taki, że .$L \subseteq A^{\ast}$ $M(L)$$M$$L$$\varphi : A^{\ast} \to M$$L = \varphi^{-1}(\varphi(L)))$

Mamy więc ładny wynik:

Monoid rozpoznaje jeśli jest homomorficznym obrazem submonoidu (napisanego jako ).$M$$L \subseteq A^{\ast}$$M(L)$$M$$M(L) \prec M$

Powyższe jest zwykle stwierdzone w kontekście zwykłych języków, a następnie wszystkie powyższe monoidy są skończone.

Załóżmy teraz, że podstawiamy dowolnym arbitralnym monoidem i mówimy, że podzbiór jest rozpoznawany przez jeśli istnieje morfizm taki, że . Zatem nadal mamy to, że jeśli rozpoznaje , to (patrz S. Eilenberg, Automata, Machines and Languages, Tom B), ale czy istnieje odwrotność?$A^{\ast}$$N$$L \subseteq N$$M$$\varphi : N \to M$$L = \varphi^{-1}(\varphi(L))$$M$$L$$M(L) \prec M$

W dowodzie na odwrotność udowodniono poprzez wykorzystanie właściwości, że jeśli dla pewnego morfizmu i jest także morfizmem, wtedy możemy znaleźć tak że , po prostu wybierając niektóre dla każdego i rozszerzenie to morfizmu z dla . Ale to nie działa w przypadku arbitralnych monoidów więc spodziewam się, że powyższa konwersja będzie fałszywa. A jeśli jest to fałsz, dla jakiego rodzaju monoidu obok$A^{\ast}$$N = \varphi(M)$$\varphi : M \to N$$\psi : A^{\ast} \to N$$\rho : A^{\ast} \to M$$\varphi(\rho(u)) = \psi(u)$$\rho(x) \in \varphi^{-1}(\psi(x))$$x \in A$$A^{\ast}$$M$$N$$A^{\ast}$ czy to nadal prawda i czy te monoidy zwróciły uwagę w literaturze naukowej?

Tak, te monoidy zwróciły uwagę w literaturze badawczej i faktycznie prowadzą do trudnych pytań.

Definicja . Monoid$N$nazywa się rzutowym, jeśli zachowuje się następująca właściwość: if$f:N \to R$ jest monoidalnym morfizmem i $h:T \to R$ jest morfizmem przejmującym, wówczas istnieje morfizm $g:N \to T$ takie, że $f = h \circ g$.

Długą dyskusję na temat monoidów rzutowych można znaleźć w [1], zaraz po definicji 4.1.33. W szczególności pokazano, że każda rzutowana półgrupa skończona jest pasmem (półgrupa, w której każdy element jest idempotentny). Ale odwrotność nie jest prawdą i faktycznie jest to otwarty problem, aby zdecydować, czy skończona półgrupa jest rzutowa.

[1] J. Rhodes i B. Steinberg, The$q$-teoria skończonych półgrup . Springer Monographs in Mathematics. Springer, New York, 2009. XXII + 666 s. ISBN: 978-0-387-09780-0