Geodesic
Permutree sorting
Pilaud, Vincent1 ; Pons, Vivane2 ; Tamayo Jimenez, Daniel2
1 CNRS & LIX École Polytechnique Palaiseau France
2 Université Paris-Saclay CNRS Laboratoire Interdisciplinaire des Sciences du Numérique 91400 Orsay France
Algebraic Combinatorics, Tome 6 (2023) no. 1, pp. 53-74

Voir la notice de l'article provenant de la source Numdam

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 jki if j∈U and kij 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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/alco.249
Classification : 68P10, 68Q45, 68R05, 05E99
Keywords: stack sorting, automata, permutrees, weak order

Pilaud, Vincent 1 ; Pons, Vivane 2 ; Tamayo Jimenez, Daniel 2

1 CNRS & LIX École Polytechnique Palaiseau France
2 Université Paris-Saclay CNRS Laboratoire Interdisciplinaire des Sciences du Numérique 91400 Orsay France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{ALCO_2023__6_1_53_0,
     author = {Pilaud, Vincent and Pons, Vivane and Tamayo Jimenez, Daniel},
     title = {Permutree sorting},
     journal = {Algebraic Combinatorics},
     pages = {53--74},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {1},
     year = {2023},
     doi = {10.5802/alco.249},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.5802/alco.249/}
}
TY  - JOUR
AU  - Pilaud, Vincent
AU  - Pons, Vivane
AU  - Tamayo Jimenez, Daniel
TI  - Permutree sorting
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 53
EP  - 74
VL  - 6
IS  - 1
PB  - The Combinatorics Consortium
UR  - http://geodesic.mathdoc.fr/articles/10.5802/alco.249/
DO  - 10.5802/alco.249
LA  - en
ID  - ALCO_2023__6_1_53_0
ER  - 
%0 Journal Article
%A Pilaud, Vincent
%A Pons, Vivane
%A Tamayo Jimenez, Daniel
%T Permutree sorting
%J Algebraic Combinatorics
%D 2023
%P 53-74
%V 6
%N 1
%I The Combinatorics Consortium
%U http://geodesic.mathdoc.fr/articles/10.5802/alco.249/
%R 10.5802/alco.249
%G en
%F ALCO_2023__6_1_53_0
Pilaud, Vincent; Pons, Vivane; Tamayo Jimenez, Daniel. Permutree sorting. Algebraic Combinatorics, Tome 6 (2023) no. 1, pp. 53-74. doi: 10.5802/alco.249

Cité par Sources :