Sorting with two stacks in parallel

Résumé : Nous énumérons les permutations triables par deux piles en parallèle. Cette question était restée ouverte depuis les travaux de Knuth, Pratt et Tarjan dans les années 70. Notre solution consiste en une paire d’équations qui caractérisent la série génératrice. La première composante de ce système décrit la série $Q(a,u)$ des chemins fermés confinés dans le quart de plan positif, comptés selon leur longueur et le nombre de facteurs Nord-Ouest ou Est-Sud. Notre analyse du comportement asymptotique du nombre de permutations triables repose à ce stade sur deux conjectures remarquables portant sur $Q(a; u)$. Nous les prouvons pour les chemins fermés non confinés, ou confinés au demi-plan supérieur.
Type de document :
Communication dans un congrès
Louis J. Billera and Isabella Novik. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), pp.585-596, 2014, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01207545
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 1 octobre 2015 - 09:28:09
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : samedi 2 janvier 2016 - 10:36:08

Fichier

dmAT0151.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01207545, version 1

Collections

Citation

Michael Albert, Mireille Bousquet-Mélou. Sorting with two stacks in parallel. Louis J. Billera and Isabella Novik. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), pp.585-596, 2014, DMTCS Proceedings. 〈hal-01207545〉

Partager

Métriques

Consultations de la notice

106

Téléchargements de fichiers

200