Sorting and preimages of pattern classes

Claesson, Anders and Úlfarsson, Henning; (2012) Sorting and preimages of pattern classes. In: 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012). Discrete Mathematics & Theoretical Computer Science, Nancy, France, pp. 595-606. (http://www.dmtcs.org/dmtcs-ojs/index.php/proceedin...)

Abstract

We introduce an algorithm to determine when a sorting operation, such as stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a new proof of the description of West-2-stack-sortable permutations, that is permutations that are completely sorted when passed twice through a stack, in terms of patterns. We also solve the long-standing problem of describing West-3-stack-sortable permutations. This requires a new type of generalized permutation pattern we call a decorated pattern.

• Share and Export
  

  RDF+XMLBibTeXRIOXX2 XMLRDF+N-TriplesJSONDublin CoreAtomSimple MetadataReferMETSHTML CitationASCII CitationOpenURL ContextObjectEndNoteOpenURL ContextObject in SpanMODSMPEG-21 DIDLEP3 XMLData Cite XMLRIS (EndNote Online, Zotero, Ref manager, etc)RDF+N3Multiline CSV
• Item metadata

  Item type:	Book Section
  ID code:	51691
  Dates:	Date Event 2012 Published
  Subjects:	Science > Mathematics
  Department:	Faculty of Science > Computer and Information Sciences
  Depositing user:	Pure Administrator
  Date deposited:	17 Feb 2015 11:54
  Last modified:	08 Apr 2024 13:18
  Related URLs:	Journal or Publication
  URI:	https://strathprints.strath.ac.uk/id/eprint/51691