www.wikidata.id-id.nina.az

Faktorisasi monoid Dalam matematika faktorisasi dari monoid bebas adalah urutan himpunan bagian kata dengan properti bah

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 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 sunting

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 sunting

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 sunting

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 sunting

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;[butuh klarifikasi]
  • 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 .[butuh klarifikasi]

Lihat pula sunting

  • Kata Zimin

Referensi sunting

  1. Lothaire (1997) p.64
  2. Lothaire (1997) p.67
  3. Duval, Jean-Pierre (1983). "Factorizing words over an ordered alphabet". Journal of Algorithms. 4 (4): 363–381. doi:10.1016/0196-6774(83)90017-2. .
  4. Guy Melançon, (1992) "Combinatorics of Hall trees and Hall words 2022-04-01 di Wayback Machine.", Journal of Combinatoric Theory, 59A(2) pp. 285–308.
  5. Lothaire (1997) p.68
  6. Lothaire (1997) p.69
  7. Lothaire (1997) p.71
  8. Lothaire (1997) p.92
  • 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 
wikipedia, wiki, buku, buku, perpustakaan, artikel, baca, unduh, gratis, unduh gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, gambar, musik, lagu, film, buku, permainan, permainan.
Tanggal penerbitan:
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 Schutzenberger 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 Daftar isi 1 Teorema Chen Fox Lyndon 2 Kata Hall 3 Bagi dua 4 Teorema Schutzenberger 5 Lihat pula 6 ReferensiTeorema Chen Fox Lyndon suntingKata Lyndon atas huruf yang tersusun total A displaystyle A nbsp adalah kata yangsecara 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 nbsp menjadi himpunan satuan I displaystyle I nbsp untuk setiap kata Lyndon I displaystyle I nbsp dengan himpunan indeks L displaystyle L nbsp dari kata kata Lyndon yang diurutkan secara leksikografis kita memperoleh pemfaktoran A displaystyle A nbsp 2 Pemfaktoran seperti ini dapat ditemukan dalam waktu linear 3 Kata Hall suntingHimpunan 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 suntingBagi dua monoid bebas adalah faktorisasi dengan hanya dua kelas X 0 displaystyle X 0 nbsp X 1 displaystyle X 1 nbsp 5 Contoh A a b displaystyle A a b nbsp X 0 a b displaystyle X 0 a b nbsp X 1 a displaystyle X 1 a nbsp Jika X displaystyle X nbsp Y displaystyle Y nbsp adalah himpunan lepas kata takkosonh maka X Y displaystyle X Y nbsp adalah bagi dua dari A displaystyle A nbsp jika dan hanya jika 6 Y X A X Y displaystyle YX cup A X cup Y nbsp Akibatnya untuk suatu partisi P displaystyle P nbsp Q displaystyle Q nbsp pada A displaystyle A nbsp terdapat bagi dua tunggal X Y displaystyle X Y nbsp dengan X displaystyle X nbsp adalah himpunan bagian dari P displaystyle P nbsp dan Y displaystyle Y nbsp adalah himpunan bagian dari Q displaystyle Q nbsp 7 Teorema Schutzenberger suntingTeorema ini menyatakan bahwa urutan X i displaystyle X i nbsp dari himpunan bagian A displaystyle A nbsp membentuk pemfaktoran jika dan hanya jika dua dari tiga pernyataan berikut berlaku Setiap elemen A displaystyle A nbsp memiliki setidaknya satu ekspresi dalam formulir yang diperlukan butuh klarifikasi Setiap elemen A displaystyle A nbsp memiliki paling banyak satu ekspresi dalam bentuk yang diminta Setiap kelas konjugasi C displaystyle C nbsp hanya bertemu dengan salah satu monoid M i X i displaystyle M i X i nbsp dan elemen C displaystyle C nbsp pada M i displaystyle M i nbsp sekawan di M i displaystyle M i nbsp 8 butuh klarifikasi Lihat pula suntingKata ZiminReferensi sunting Lothaire 1997 p 64 Lothaire 1997 p 67 Duval Jean Pierre 1983 Factorizing words over an ordered alphabet Journal of Algorithms 4 4 363 381 doi 10 1016 0196 6774 83 90017 2 Guy Melancon 1992 Combinatorics of Hall trees and Hall words Diarsipkan 2022 04 01 di Wayback Machine Journal of Combinatoric Theory 59A 2 pp 285 308 Lothaire 1997 p 68 Lothaire 1997 p 69 Lothaire 1997 p 71 Lothaire 1997 p 92 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 Schutzenberger 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 Diperoleh dari https id wikipedia org w index php title Faktorisasi monoid amp oldid 23865475