Permutree sorting

Source abstract

Generalizing stack sorting and c -sorting for permutations, we define the permutree sorting algorithm. Given two disjoint subsets U and D of { 2 , ⋯ , n - 1 } , the ( U , D ) -permutree sorting tries to sort the permutation π ∈ 𝔖 n and fails if and only if there are 1 ≤ i < j < k ≤ n such that π contains the subword j k i if j ∈ U and k i j if j ∈ D . This algorithm is seen as a way to explore an automaton which either rejects all reduced words of π , or accepts those reduced words for π whose prefixes are all ( U , D ) -permutree sortable.