Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Permutree sorting

Abstract : Generalizing stack sorting and $c$-sorting for permutations, we define the permutree sorting algorithm. Given two disjoint subsets $U$ and $D$ of $\{2, \dots, n-1\}$, the $(U,D)$-permutree sorting tries to sort the permutation $\pi \in \mathfrak{S}_n$ and fails if and only if there are $1 \le i < j < k \le n$ such that $\pi$ contains the subword $jki$ if $j \in U$ and $kij$ if $j \in D$. This algorithm is seen as a way to explore an automaton which either rejects all reduced expressions of $\pi$, or accepts those reduced expressions for $\pi$ whose prefixes are all $(U,D)$-permutree sortable.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02997673
Contributor : Vincent Pilaud <>
Submitted on : Tuesday, November 10, 2020 - 10:57:41 AM
Last modification on : Tuesday, December 8, 2020 - 10:45:03 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02997673, version 1
  • ARXIV : 2007.07802

Citation

Vincent Pilaud, Viviane Pons, Daniel Tamayo Jiménez. Permutree sorting. 2020. ⟨hal-02997673⟩

Share

Metrics

Record views

9

Files downloads

10