Let B and S be, respectively, the base steps of bubblesort and stacksort, and call B ̃ and S ̃ their dual versions via the reverse-complement map. We find some unexpected commutation properties between the classical operators and their duals, and we also prove that the set of permutations sortable by a prescribed number of iterations of B and B ̃ is a pattern class.
Bubblesort, stacksort and their duals / Luca Ferrari. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 170:(2014), pp. 64-71. [10.1016/j.dam.2014.01.014]
Bubblesort, stacksort and their duals
FERRARI, LUCA
2014
Abstract
Let B and S be, respectively, the base steps of bubblesort and stacksort, and call B ̃ and S ̃ their dual versions via the reverse-complement map. We find some unexpected commutation properties between the classical operators and their duals, and we also prove that the set of permutations sortable by a prescribed number of iterations of B and B ̃ is a pattern class.File in questo prodotto:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
