{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:34:59Z","timestamp":1772372099196,"version":"3.50.1"},"reference-count":47,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2019,2]]},"abstract":"<jats:p>The left patience sorting ([Formula: see text][Formula: see text]PS) monoid, also known in the literature as the Bell monoid, and the right patient sorting ([Formula: see text]PS) 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.<\/jats:p><jats:p>Each finite-rank [Formula: see text]PS monoid is shown to have polynomial growth and to satisfy a nontrivial identity (dependent on its rank), while the infinite rank [Formula: see text]PS monoid does not satisfy any nontrivial identity. Each [Formula: see text][Formula: see text]PS monoid of finite rank has exponential growth and does not satisfy any nontrivial identity. The complexity of the insertion algorithms is discussed.<\/jats:p><jats:p>[Formula: see text]PS monoids of finite rank are shown to be automatic and to have recursive complete presentations. When the rank is [Formula: see text] or [Formula: see text], they are also biautomatic. [Formula: see text][Formula: see text]PS monoids of finite rank are shown to have finite complete presentations and to be biautomatic.<\/jats:p>","DOI":"10.1142\/s0218196718500649","type":"journal-article","created":{"date-parts":[[2018,8,31]],"date-time":"2018-08-31T09:12:00Z","timestamp":1535706720000},"page":"85-125","source":"Crossref","is-referenced-by-count":5,"title":["The monoids of the patience sorting algorithm"],"prefix":"10.1142","volume":"29","author":[{"given":"Alan J.","family":"Cain","sequence":"first","affiliation":[{"name":"Centro de Matem\u00e1tica e Aplica\u00e7\u00f5es, Faculdade de Ci\u00eancias e Tecnologia, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal"}]},{"given":"Ant\u00f3nio","family":"Malheiro","sequence":"additional","affiliation":[{"name":"Centro de Matem\u00e1tica e Aplica\u00e7\u00f5es and Departamento de Matem\u00e1tica, Faculdade de Ci\u00eancias e Tecnologia, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal"}]},{"given":"F\u00e1bio M.","family":"Silva","sequence":"additional","affiliation":[{"name":"Departamento de Matem\u00e1tica and CEMAT-CI\u00caNCIAS, Faculdade de Ci\u00eancias, Universidade de Lisboa, Lisboa 1749-016, Portugal"}]}],"member":"219","published-online":{"date-parts":[[2019,2,27]]},"reference":[{"key":"S0218196718500649BIB001","first-page":"1","volume":"85","author":"Adjan S. I.","year":"1966","journal-title":"Proc. Steklov Inst. Math."},{"key":"S0218196718500649BIB002","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-99-00796-X"},{"key":"S0218196718500649BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"S0218196718500649BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"S0218196718500649BIB005","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1804"},{"key":"S0218196718500649BIB006","first-page":"19","volume":"54","author":"Burstein A.","year":"2005","journal-title":"S\u00e9m. Lothar. Combin."},{"key":"S0218196718500649BIB007","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196715400044"},{"key":"S0218196718500649BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2014.09.037"},{"key":"S0218196718500649BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00151-6"},{"key":"S0218196718500649BIB012","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196701000425"},{"key":"S0218196718500649BIB013","doi-asserted-by":"publisher","DOI":"10.1142\/S0219498808003028"},{"key":"S0218196718500649BIB014","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"S0218196718500649BIB015","doi-asserted-by":"publisher","DOI":"10.1142\/9789814434461_0003"},{"key":"S0218196718500649BIB016","volume-title":"Finiteness and Regularity in Semigroups and Formal Languages","author":"de Luca A.","year":"2011","edition":"1"},{"key":"S0218196718500649BIB017","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196702001139"},{"key":"S0218196718500649BIB018","first-page":"124","volume-title":"Words, Languages and Combinatorics, II","author":"Duchamp G.","year":"1994"},{"key":"S0218196718500649BIB019","doi-asserted-by":"publisher","DOI":"10.1201\/9781439865699"},{"key":"S0218196718500649BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/362663.362752"},{"key":"S0218196718500649BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90103-X"},{"key":"S0218196718500649BIB022","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90230-Q"},{"key":"S0218196718500649BIB023","series-title":"London Mathematical Society Student Texts","volume-title":"Young Tableaux With Applications to Representation Theory and Geometry","volume":"35","author":"Fulton W.","year":"1997"},{"key":"S0218196718500649BIB024","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1966-0201310-3"},{"key":"S0218196718500649BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2012.03.020"},{"key":"S0218196718500649BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.01.012"},{"key":"S0218196718500649BIB029","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.09.005"},{"key":"S0218196718500649BIB030","doi-asserted-by":"publisher","DOI":"10.1007\/11537311_6"},{"key":"S0218196718500649BIB031","series-title":"LMS Monographs","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198511946.001.0001","volume-title":"Fundamentals of Semigroup Theory","author":"Howie J.","year":"1995"},{"key":"S0218196718500649BIB033","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00152-3"},{"key":"S0218196718500649BIB034","first-page":"1081","volume":"4","author":"Karpuz E. G.","year":"2010","journal-title":"Appl. Math. Sci."},{"key":"S0218196718500649BIB036","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00264-J"},{"key":"S0218196718500649BIB037","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008673127310"},{"key":"S0218196718500649BIB038","doi-asserted-by":"publisher","DOI":"10.1007\/s00233-014-9609-9"},{"key":"S0218196718500649BIB039","doi-asserted-by":"publisher","DOI":"10.1007\/BF00750843"},{"key":"S0218196718500649BIB040","series-title":"Quaderni de \u201cLa Ricerca Scientifica\u201d","first-page":"129","volume-title":"Noncommutative Structures in Algebra and Geometric Combinatorics","volume":"109","author":"Lascoux A.","year":"1981"},{"key":"S0218196718500649BIB041","first-page":"3","volume":"20","author":"Latteux M.","year":"1984","journal-title":"Elektron. Informationsverarb. Kybernetik"},{"key":"S0218196718500649BIB042","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1998.1759"},{"key":"S0218196718500649BIB043","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019"},{"key":"S0218196718500649BIB044","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00270-8"},{"key":"S0218196718500649BIB045","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-3394-4_12"},{"issue":"1","key":"S0218196718500649BIB046","first-page":"79","volume":"19","author":"Poirier S.","year":"1995","journal-title":"Ann. Sci. Math. Qu\u00e9bec"},{"key":"S0218196718500649BIB047","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00308-8"},{"key":"S0218196718500649BIB051","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-08031-4","volume-title":"Combinatorial Algebra: Syntax and Semantics","author":"Sapir M. V.","year":"2014"},{"key":"S0218196718500649BIB052","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1961-015-3"},{"key":"S0218196718500649BIB053","doi-asserted-by":"publisher","DOI":"10.1145\/230514.571645"},{"key":"S0218196718500649BIB054","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139058520"},{"key":"S0218196718500649BIB055","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2009.07.005"},{"issue":"6","key":"S0218196718500649BIB056","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1007\/BF01069218","volume":"17","author":"Trofimov V. I.","year":"1981","journal-title":"Cybernetics"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196718500649","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T20:19:05Z","timestamp":1720556345000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196718500649"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2]]},"references-count":47,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2019,2,27]]},"published-print":{"date-parts":[[2019,2]]}},"alternative-id":["10.1142\/S0218196718500649"],"URL":"https:\/\/doi.org\/10.1142\/s0218196718500649","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2]]}}}