Geodesic
Sorting with two stacks in parallel
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) (2014).

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

At the end of the 1960s, Knuth characterised in terms of forbidden patterns the permutations that can be sorted using a stack. He also showed that they are in bijection with Dyck paths and thus counted by the Catalan numbers. Subsequently, Pratt and Tarjan asked about permutations that can be sorted using two stacks in parallel. This question is significantly harder, and the associated counting question has remained open for 40 years. We solve it by giving a pair of equations that characterise the generating function of such permutations. The first component of this system describes the generating function $Q(a,u)$ of square lattice loops confined to the positive quadrant, counted by the length and the number of North-West and East-South factors. Our analysis of the asymptotic number of sortable permutations relies at the moment on two intriguing conjectures dealing with this series. Given the recent activity on walks confined to cones, we believe them to be attractive $\textit{per se}$. We prove these conjectures for closed walks confined to the upper half plane, or not confined at all. 
@article{DMTCS_2014_special_265_a50,
     author = {Albert, Michael and Bousquet-M\'elou, Mireille},
     title = {Sorting with two stacks in parallel},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)},
     year = {2014},
     doi = {10.46298/dmtcs.2425},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2425/}
}
TY  - JOUR
AU  - Albert, Michael
AU  - Bousquet-Mélou, Mireille
TI  - Sorting with two stacks in parallel
JO  - Discrete mathematics & theoretical computer science
PY  - 2014
VL  - DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2425/
DO  - 10.46298/dmtcs.2425
LA  - en
ID  - DMTCS_2014_special_265_a50
ER  - 
%0 Journal Article
%A Albert, Michael
%A Bousquet-Mélou, Mireille
%T Sorting with two stacks in parallel
%J Discrete mathematics & theoretical computer science
%D 2014
%V DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2425/
%R 10.46298/dmtcs.2425
%G en
%F DMTCS_2014_special_265_a50
Albert, Michael; Bousquet-Mélou, Mireille. Sorting with two stacks in parallel. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) (2014). doi : 10.46298/dmtcs.2425. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2425/

Cité par Sources :