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.^{[butuh klarifikasi]}

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

w = x i 1 x i 2 ⋯ x i n   {\displaystyle w=x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}\ }

dengan x i j ∈ X i j {\displaystyle x_{i_{j}}\in X_{i_{j}}} dan i 1 ≥ i 2 ≥ … ≥ i n {\displaystyle 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 {\displaystyle A} adalah kata yang secara leksikografis lebih kecil dari semua rotasinya.^[1] 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 {\displaystyle X_{i}} menjadi himpunan satuan { I } {\displaystyle \{I\}} untuk setiap kata Lyndon I {\displaystyle I} , dengan himpunan indeks L {\displaystyle L} dari kata-kata Lyndon yang diurutkan secara leksikografis, kita memperoleh pemfaktoran A ∗ {\displaystyle A^{*}} .^[2] Pemfaktoran seperti ini dapat ditemukan dalam waktu linear.^[3]

Kata Hall

Himpunan Hall menyediakan faktorisasi.^[4] 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 {\displaystyle X_{0}} , X 1 {\displaystyle X_{1}} .^[5]

Contoh:

A = { a , b } {\displaystyle A=\{a,b\}} , X 0 = { a ∗ b } {\displaystyle X_{0}=\{a^{*}\,b\}} , X 1 = { a } {\displaystyle X_{1}=\{a\}} .

Jika X {\displaystyle X} , Y {\displaystyle Y} adalah himpunan lepas kata takkosonh, maka ( X . Y ) {\displaystyle (X.Y)} adalah bagi-dua dari A ∗ {\displaystyle A^{*}} jika dan hanya jika^[6]

Y X ∪ A = X ∪ Y {\displaystyle YX\cup A=X\cup Y} .

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

Teorema Schützenberger

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

• Setiap elemen A ∗ {\displaystyle A^{*}} memiliki setidaknya satu ekspresi dalam formulir yang diperlukan;^{[butuh klarifikasi]}
• Setiap elemen A ∗ {\displaystyle A^{*}} memiliki paling banyak satu ekspresi dalam bentuk yang diminta;
• Setiap kelas konjugasi C {\displaystyle C} hanya bertemu dengan salah satu monoid M i = X i ∗ {\displaystyle M_{i}=X_{i}^{*}} dan elemen C {\displaystyle C} pada M i {\displaystyle M_{i}} sekawan di M i {\displaystyle M_{i}} .^{[8][butuh klarifikasi]}

Lihat pula

• Kata Zimin

Referensi

• Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 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 2nd), Cambridge University Press, ISBN 0-521-59924-5, Zbl 0874.20040