Sorting and generating reduced words

DOI10.1007/S00013-013-0571-7zbMATH Open1278.05008arXiv1301.5723OpenAlexW2011134170MaRDI QIDQ387597FDOQ387597

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

Publication date: 23 December 2013

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

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$.

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

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

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)

Cites Work

• Some combinatorial aspects of reduced words in finite Coxeter groups
• Title not available (Why is that?)
• On the number of reduced decompositions of elements of Coxeter groups
• Tower tableaux

Cited In (5)

• Linked reduction systems for permutations.
• Word posets, with applications to Coxeter groups
• Reductions on Double Occurrence Words
• The maximum multiplicity of a generator in a reduced word
• 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)