Sorting and generating reduced words

DOI10.1007/S00013-013-0571-7MaRDI QIDQ387597zbMATH OpenOpenAlexFDO

Authors Olcay Coşkun, Müge Taşkın

Publication date 23 December 2013

Published in Archiv der Mathematik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.5723

zbMATH Keywords

directed-braid poset

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Partial orders, general (06A06) Searching and sorting (68P10) Symmetric groups (20B30) Combinatorics on words (68R15)

Abstract: We introduce a partial order on the set of all reduced words of a given permutation $omega$, called emph{directed-braid poset} of $omega$. This poset enables us to produce two algorithms: One is a sorting algorithm applied on any reduced word of $omega$ and aims to obtained the natural word (lexicographically largest reduced word); the other one is a generation algorithm applied on the natural word and aims to obtained the set of all reduced words of $omega$.

Recommendations

• Word posets, with applications to Coxeter groups
• Reduced word enumeration, complexity, and randomization
• The maximum multiplicity of a generator in a reduced word
• Permutree sorting
• Convex orderings and symmetric group

Cites work

• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• On the number of reduced decompositions of elements of Coxeter groups
• Some combinatorial aspects of reduced words in finite Coxeter groups
• Tower tableaux

Cited in

(5)

• Word posets, with applications to Coxeter groups
• Reductions on Double Occurrence Words
• The maximum multiplicity of a generator in a reduced word
• Linked reduction systems for permutations.
• Reduced word enumeration, complexity, and randomization

This page was built for publication: Sorting and generating reduced words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q387597)