Inscriere cercetatori

Daca aveti cont Ad Astra si de Facebook, intrati pe pagina de profil pentru a da dreptul sa va logati pe site doar cu acest buton.

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa old.ad-astra.ro

Facebook

Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în volumul unei conferinţe

Autori: Gabriel Istrate, Cosmin Bonchis

Editorial: Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM'2015), Lecture Notes in Computer Science vol. 9133, p.261-271, Springer Verlag, 2015.

Rezumat:

Want create site? Find Free WordPress Themes and plugins.

We investigate partitioning of integer sequences into heapable subsequences (previously defined and studied by Byers et al. We show that an extension of patience sorting computes the decomposition into a minimal number of heapable subsequences (MHS). We connect this parameter to an interactive particle system, a multiset extension of Hammersley’s process, and investigate its expected value on a random permutation. In contrast with the (well studied) case of the longest increasing subsequence, we bring experimental evidence that the correct asymptotic scaling is $frac{1+sqrt{5}}{2} · ln(n)$. Finally we give a heap-based extension of Young tableaux, prove a hook inequality and an extension of the Robinson-Schensted correpondence.

Did you find apk for android? You can find new Free Android Games and apps.

Cuvinte cheie: heapable sequence, Young tableaux

URL: http://link.springer.com/chapter/10.1007/978-3-319-19929-0_22#page-1