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  adalah monoid bebas pada huruf .  Misalkan  adalah urutan himpunan bagian dari   yang diindeks oleh himpunan indeks terurut total . Faktorisasi sebuah kata  pada  adalah ekspresi

dengan  dan . Beberapa penulis membalik urutan ketidaksetaraan.

Teorema Chen–Fox–Lyndon 
Kata Lyndon atas huruf yang tersusun total  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  menjadi himpunan satuan  untuk setiap kata Lyndon , dengan himpunan indeks  dari kata-kata Lyndon yang diurutkan secara leksikografis, kita memperoleh pemfaktoran .  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 , .

Contoh:
, , .

Jika ,  adalah himpunan lepas kata takkosonh, maka  adalah bagi-dua dari  jika dan hanya jika
.

Akibatnya, untuk suatu partisi ,  pada  terdapat bagi-dua tunggal  dengan  adalah himpunan bagian dari  dan  adalah himpunan bagian dari .

Teorema Schützenberger 
Teorema ini menyatakan bahwa urutan  dari himpunan bagian   membentuk pemfaktoran jika dan hanya jika dua dari tiga pernyataan berikut berlaku:
 Setiap elemen  memiliki setidaknya satu ekspresi dalam formulir yang diperlukan;
 Setiap elemen  memiliki paling banyak satu ekspresi dalam bentuk yang diminta;
 Setiap kelas konjugasi  hanya bertemu dengan salah satu monoid  dan elemen  pada  sekawan di .

Lihat pula 
 Kata Zimin

Referensi 

Bahasa formal