The monoids of the patience sorting algorithm

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

The left patience sorting (PS) monoid, also known in the literature as the Bell monoid, and the right patient sorting (rPS) monoid are introduced by defining certain congruences on words. Such congruences are constructed using insertion algorithms based on the concept of decreasing subsequences. Presentations for these monoids are given. Each finite-rank rPS monoid is shown to have polynomial growth and to satisfy a nontrivial identity (dependent on its rank), while the infinite rank rPS monoid does not satisfy any nontrivial identity. Each PS monoid of finite rank has exponential growth and does not satisfy any nontrivial identity. The complexity of the insertion algorithms is discussed. rPS monoids of finite rank are shown to be automatic and to have recursive complete presentations. When the rank is 1 or 2, they are also biautomatic. PS monoids of finite rank are shown to have finite complete presentations and to be biautomatic.

Original languageEnglish
Pages (from-to)85-125
JournalInternational Journal Of Algebra And Computation
Volume29
Issue number1
DOIs
Publication statusPublished - 1 Feb 2019

Keywords

  • automatic monoid
  • complete rewriting system
  • growth of monoids
  • Patience sorting algorithm
  • PS tableau
  • semigroup identity

Fingerprint Dive into the research topics of 'The monoids of the patience sorting algorithm'. Together they form a unique fingerprint.

Cite this