Generalisasi pernyataan bahwa monoid mengenali bahasa iff sintaksis monoid membagi monoid

Biarkan menjadi alfabet terbatas. Untuk bahasa tertentu yang sintaksis monoid adalah gagasan terkenal dalam teori bahasa formal. Selanjutnya, monoid mengenali bahasa jika ada morfisme sedemikian rupa sehingga .L ⊆ A $A$$L \subseteq A^{\ast}$ M L φ : A ∗ → M L = φ - 1 ( φ ( L ) ) $M(L)$$M$$L$$\varphi : A^{\ast} \to M$$L = \varphi^{-1}(\varphi(L)))$

Maka kami memiliki hasil yang bagus:

monoid mengenali jika adalah gambar homomorfis dari submonoid (ditulis sebagai ).L ⊆ A ∗ M ( L ) M M ( L ) ≺ $M$$L \subseteq A^{\ast}$$M(L)$$M$$M(L) \prec M$

Di atas biasanya menyatakan dalam konteks bahasa reguler, dan kemudian monoids di atas semua terbatas.

Sekarang anggaplah kita mengganti dengan monoid sewenang-wenang , dan kita mengatakan bahwa subset dikenali oleh jika ada morfisme sedemikian rupa sehingga . Maka kita masih memiliki itu jika mengenali , maka (lihat S. Eilenberg, Automata, Mesin dan Bahasa, Volume B), tetapi apakah kebalikannya berlaku? N L ⊆ N M φ : N → M L = φ - 1 ( φ ( L ) ) M L M ( L ) ≺ $A^{\ast}$$N$$L \subseteq N$$M$$\varphi : N \to M$$L = \varphi^{-1}(\varphi(L))$$M$$L$$M(L) \prec M$

Dalam bukti untuk kebalikannya dibuktikan dengan mengeksploitasi properti bahwa jika untuk beberapa morfisme dan juga merupakan morfisme, maka kita dapat menemukan sedemikian rupa sehingga bertahan, cukup dengan memilih beberapa untuk setiap dan memperluas ini untuk morphism dari ke . Tapi ini tidak bekerja untuk monoids sewenang-wenang jadi saya berharap sebaliknya berbicara salah. Dan jika itu salah, untuk monoid apa selain N = φ ( M ) φ : M → N ψ : A ∗ → N ρ : A ∗ → M φ ( ρ ( u ) ) = ψ ( u ) ρ ( x ) ∈ φ - 1 ( ψ ( x )) ) x ∈ A A ∗ M N A $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}$ apakah itu masih benar, dan apakah monoids tersebut telah mendapat perhatian dalam literatur penelitian?

Ya, monoids ini telah mendapat perhatian dalam literatur penelitian dan benar-benar mengarah pada pertanyaan yang sulit.

Definisi . Monoid disebut proyektif jika sifat berikut ini berlaku: jika f : N → R adalah morfisme monoid dan h : T → R adalah morfisme surjektif, maka terdapat morfisme g : N → T sedemikian sehingga f = h ∘ g .$N$$f:N \to R$$h:T \to R$$g:N \to T$$f = h \circ g$

Anda dapat menemukan diskusi panjang tentang monoid proyektif di [1], tepat setelah Definisi 4.1.33. Ditunjukkan secara khusus bahwa setiap semi-grup hingga proyektif adalah sebuah band (sebuah semi-grup di mana setiap elemen idempoten). Tetapi kebalikannya tidak benar dan itu sebenarnya merupakan masalah terbuka untuk memutuskan apakah suatu semi-grup terbatas bersifat projektif.

[1] J. Rhodes dan B. Steinberg, Teori dari semigroup terbatas$q$ . Monografi Springer dalam Matematika. Springer, New York, 2009. xxii + 666 hal. ISBN: 978-0-387-09780-0