Dynamical aspects of σ-machines

Giulio Cerbai

Research output: Contribution to journalArticlepeer-review

Abstract

The σ-machine was recently introduced by Cerbai, Claesson and Ferrari as a tool to gain a better insight on the problem of sorting permutations with two stacks in series. It consists of two consecutive stacks, which are restricted in the sense that their content must at all times avoid a certain pattern: a given σ, in the first stack, and 21, in the second. Here we prove that in most cases sortable permutations avoid a bivincular pattern ξ. We provide a geometric decomposition of ξ-avoiding permutations and use it to count them directly. Then we characterize the permutations with the property that the output of the σ-avoiding stack does not contain σ, which we call effective. For σ=123, we obtain an alternative method to enumerate sortable permutations. Finally, we classify σ-machines and determine the most challenging to be studied.

Original languageEnglish
Article number113486
JournalDiscrete Mathematics
Volume346
Issue number9
DOIs
Publication statusPublished - Sept 2023

Bibliographical note

Publisher Copyright:
© 2023 Elsevier B.V.

Other keywords

  • Permutation patterns
  • Stack sorting
  • σ-machine

Fingerprint

Dive into the research topics of 'Dynamical aspects of σ-machines'. Together they form a unique fingerprint.

Cite this