Faktorisasi monoid

Dalam matematika, faktorisasi dari monoid bebas adalah urutan himpunan bagian kata dengan properti bahwa setiap kata dalam monoid bebas dapat ditulis sebagai rangkaian elemen yang diambil dari himpunan bagian tersebut. Teorema Chen–Fox–Lyndon menyatakan bahwa kata Lyndon memberikan sebuah faktorisasi. Teorema Schützenberger menghubungkan definisi dalam hal sifat perkalian dengan sifat aditif.

Misalkan $A^{*}$ adalah monoid bebas pada huruf $A$. Misalkan $X_{i}$ adalah urutan himpunan bagian dari $A^{*}$ yang diindeks oleh himpunan indeks terurut total $I$. Faktorisasi sebuah kata $w$ pada $A^{*}$ adalah ekspresi

$w=x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\$

dengan $x_{i_{j}}\in X_{i_{j}}$ dan $i_{1}\geq i_{2}\geq \ldots \geq i_{n}$. Beberapa penulis membalik urutan ketidaksetaraan.

Teorema Chen–Fox–Lyndon

Kata Lyndon atas huruf yang tersusun total $A$ adalah kata yang secara leksikografis lebih kecil dari semua rotasinya. Teorema Chen–Fox–Lyndon menyatakan bahwa setiap untai dapat dibentuk dengan cara yang unik dengan menggabungkan urutan kata Lyndon yang tidak bertambah. Oleh karena itu $X_{i}$ menjadi himpunan satuan $\{I\}$ untuk setiap kata Lyndon $I$, dengan himpunan indeks $L$ dari kata-kata Lyndon yang diurutkan secara leksikografis, kita memperoleh pemfaktoran $A^{*}$. Pemfaktoran seperti ini dapat ditemukan dalam waktu linear.

Kata Hall

Himpunan Hall menyediakan faktorisasi. Memang, kata Lyndon adalah kasus khusus dari kata-kata Hall. Artikel pada kata Hall memberikan sketsa dari semua mekanisme yang diperlukan untuk membuktikan faktorisasi ini.

Bagi-dua

Bagi-dua monoid bebas adalah faktorisasi dengan hanya dua kelas $X_{0}$, $X_{1}$.

Contoh:

$A=\{a,b\}$, $X_{0}=\{a^{*}\,b\}$, $X_{1}=\{a\}$.

Jika $X$, $Y$ adalah himpunan lepas kata takkosonh, maka $(X.Y)$ adalah bagi-dua dari $A^{*}$ jika dan hanya jika

$YX\cup A=X\cup Y$.

Akibatnya, untuk suatu partisi $P$, $Q$ pada $A^{+}$ terdapat bagi-dua tunggal $(X.Y)$ dengan $X$ adalah himpunan bagian dari $P$ dan $Y$ adalah himpunan bagian dari $Q$.

Teorema Schützenberger

Teorema ini menyatakan bahwa urutan $X_{i}$ dari himpunan bagian $A^{*}$ membentuk pemfaktoran jika dan hanya jika dua dari tiga pernyataan berikut berlaku:

• Setiap elemen $A^{*}$ memiliki setidaknya satu ekspresi dalam formulir yang diperlukan;
• Setiap elemen $A^{*}$ memiliki paling banyak satu ekspresi dalam bentuk yang diminta;
• Setiap kelas konjugasi $C$ hanya bertemu dengan salah satu monoid $M_{i}=X_{i}^{*}$ dan elemen $C$ pada $M_{i}$ sekawan di $M_{i}$.

Lihat pula

• Kata Zimin

Referensi

• Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (edisi ke-2nd), Cambridge University Press, ISBN 0-521-59924-5, Zbl 0874.20040