Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
POP-STACK SORTING AND ITS IMAGE: PERMUTATIONS WITH OVERLAPPING RUNS
Alpen Adria Univ Klagenfurt, Klagenfurt, Austria..
Univ Paris 13, Villetaneuse, France..
Univ Washington, Seattle, WA 98195 USA..
Alpen Adria Univ Klagenfurt, Klagenfurt, Austria..
Show others and affiliations
2019 (English)In: Acta Mathematica Universitatis Comenianae, ISSN 0862-9544, E-ISSN 0231-6986, Vol. 88, no 3, p. 395-402Article in journal (Refereed) Published
Abstract [en]

Pop-stack sorting is an important variation for sorting permutations via a stack. A single iteration of pop-stack sorting is the transformation T : S-n -> S-n that reverses all the maximal descending sequences of letters in a permutation. We investigate structural and enumerative aspects of pop-stacked permutations - the permutations that belong to the image of S-n under T. This work is part of a project aiming to provide the full combinatorial analysis of sorting with a pop-stack, as it was successfully done for sorting with a stack (though, even in this case, some famous problems are still open). The first results already show that pop-stack sorting has a very rich combinatorial structure, and leads to surprising phenomena.

Place, publisher, year, edition, pages
COMENIUS UNIV , 2019. Vol. 88, no 3, p. 395-402
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-261061ISI: 000484349000007OAI: oai:DiVA.org:kth-261061DiVA, id: diva2:1356334
Note

QC 20191001

Available from: 2019-10-01 Created: 2019-10-01 Last updated: 2019-10-01Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Article

Authority records BETA

Linusson, Svante

Search in DiVA

By author/editor
Linusson, Svante
By organisation
Mathematics (Div.)
In the same journal
Acta Mathematica Universitatis Comenianae
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf