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 dengan x i j ∈ X i j dan i 1 ≥ i 2 ≥ … ≥ i n . Beberapa penulis membalik urutan ketidaksetaraan.