Sorting and generating reduced words
Archiv der Mathematik, cilt.101, sa.5, ss.427-436, 2013 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 101 Sayı: 5
- Basım Tarihi: 2013
- Doi Numarası: 10.1007/s00013-013-0571-7
- Dergi Adı: Archiv der Mathematik
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.427-436
- Boğaziçi Üniversitesi Adresli: Evet
Özet
We introduce a partial order on the set of all reduced words of a given permutation ω, called directed-braid poset of ω. This poset enables us to produce two algorithms: One is a sorting algorithm applied to any reduced word of ω and aims to obtain the natural word (i.e. lexicographically largest reduced word); the other one is a generation algorithm applied to the natural word and returns the set of all reduced words of ω. © 2013 Springer Basel.