Free Access

The monoids of the patience sorting algorithm

Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal

E-mail Address: [email protected]

Search for more papers by this author

António Malheiro

Centro de Matemática e Aplicações and Departamento de Matemática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal

E-mail Address: [email protected]

Search for more papers by this author

and

Fábio M. Silva

Departamento de Matemática and CEMAT-CIÊNCIAS, Faculdade de Ciências, Universidade de Lisboa, Lisboa 1749-016, Portugal

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S0218196718500649Cited by:1

View article

Abstract

The left patience sorting ( $ℓ$ PS) monoid, also known in the literature as the Bell monoid, and the right patient sorting ( $r$ 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.

Each finite-rank $r$ PS monoid is shown to have polynomial growth and to satisfy a nontrivial identity (dependent on its rank), while the infinite rank $r$ PS 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.

$r$ PS 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.

Communicated by M. Volkov

Keywords:

AMSC: 20M05, 68Q45, 05E05, 05A05, 05A19, 11Y16

References

1. S. I. Adjan , Defining relations and algorithmic problems for groups and semigroups, in Proc. Steklov Inst. Math. 85 (1966) 1–52. Translated from the Russian by M. Greendlinger (American Mathematical Society, Providence, RI, 1966). Google Scholar
2. D. Aldous and P. Diaconis , Longest increasing subsequences: From patience sorting to the Baik–Deift–Johansson theorem, Bull. Amer. Math. Soc. (N.S.) 36(4) (1999) 413–432. Crossref, Google Scholar
3. J. Berstel , Transductions and Context-Free Languages, Leitfäden der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics], Vol. 38 (B. G. Teubner, Stuttgart, 1979). Crossref, Google Scholar
4. R. V. Book and F. Otto , String-Rewriting Systems, Texts and Monographs in Computer Science (Springer-Verlag, New York, 1993). Crossref, Google Scholar
5. M. R. Bridson and R. H. Gilman , Context-free languages of sub-exponential growth, J. Comput. Syst. Sci. 64(2) (2002) 308–310. Crossref, ISI, Google Scholar
6. A. Burstein and I. Lankham , Combinatorics of patience sorting piles, Sém. Lothar. Combin. 54A (2005/2007), Art. B54Ab, 19 pp. Google Scholar
7. A. J. Cain, R. D. Gray and A. Malheiro , Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids, Int. J. Algebra Comput. 25(1–2) (2015) 51–80. Link, Google Scholar
8. A. J. Cain, R. D. Gray and A. Malheiro , Finite Gröbner–Shirshov bases for plactic algebras and biautomatic structures for plactic monoids, J. Algebra 423 (2015) 37–53. Crossref, ISI, Google Scholar
9. A. J. Cain, G. Klein, Ł. Kubat, A. Malheiro and J. Okniński, A note on identities in plactic monoids and monoids of upper-triangular tropical matrices, preprint (2017), arXiv:1705.04596. Google Scholar
10. A. J. Cain and A. Malheiro, Identities in plactic, hypoplactic, sylvester, Baxter, and related monoids, preprint (2016), arXiv:1611.04151. Google Scholar
11. C. M. Campbell, E. F. Robertson, N. Ruškuc and R. M. Thomas , Automatic semigroups, Theoret. Comput. Sci. 250(1–2) (2001) 365–391. Crossref, ISI, Google Scholar
12. J. Cassaigne, M. Espie, D. Krob, J.-C. Novelli and F. Hivert , The Chinese monoid, Int. J. Algebra Comput. 11(3) (2001) 301–334. Link, ISI, Google Scholar
13. Y. Chen and J. Qiu , Gröbner–Shirshov basis for the Chinese monoid, J. Algebra Appl. 7(5) (2008) 623–628. Link, ISI, Google Scholar
14. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein , Introduction to Algorithms, 3rd edn. (MIT Press, Cambridge, MA, 2009). Google Scholar
15. E. Date, M. Jimbo and T. Miwa , Representations of $U_{q} (𝔤 𝔩 (n, C))$ at $q = 0$ and the Robinson–Schensted correspondence, in Physics and Mathematics of Strings (World Scientific, 1990), pp. 185–211. Link, Google Scholar
16. A. de Luca and S. Varricchio , Finiteness and Regularity in Semigroups and Formal Languages, 1st edn. (Springer, 2011). Google Scholar
17. G. Duchamp, F. Hivert and J.-Y. Thibon , Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras, Int. J. Algebra Comput. 12(5) (2002) 671–717. Link, ISI, Google Scholar
18. G. Duchamp and D. Krob , Plactic-growth-like monoids, in Words, Languages and Combinatorics, II (World Scientific, River Edge, NJ, 1994), pp. 124–142. Google Scholar
19. D. B. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson and W. P. Thurston , Word Processing in Groups (Jones and Bartlett Publishers, Boston, MA, 1992). Crossref, Google Scholar
20. I. Flores and G. Madpis , Average binary search length for dense ordered lists, Commun. ACM 14 (1971) 602–603. Crossref, Google Scholar
21. M. L. Fredman , On computing the length of longest increasing subsequences, Discrete Math. 11(1) (1975) 29–35. Crossref, Google Scholar
22. C. Frougny and J. Sakarovitch , Synchronized rational relations of finite and infinite words, Theoret. Comput. Sci. 108(1) (1993) 45–82. Crossref, ISI, Google Scholar
23. W. Fulton , Young Tableaux With Applications to Representation Theory and Geometry, Vol. 35, London Mathematical Society Student Texts (Cambridge University Press, Cambridge, 1997). Google Scholar
24. S. Ginsburg and E. H. Spanier , Bounded regular sets, Proc. Amer. Math. Soc. 17(5) (1966) 1043–1049. Crossref, ISI, Google Scholar
25. S. Giraudo , Algebraic and combinatorial structures on Baxter permutations, in 23rd Int. Conf. Formal Power Series and Algebraic Combinatorics (FPSAC 2011), Discrete Mathematics & Theoretical Computer Science Proceedings, Vol. AO (Association Discrete Mathematics & Theoretical Computer Science, Nancy, 2011), pp. 387–398. Google Scholar
26. S. Giraudo , Algebraic and combinatorial structures on pairs of twin binary trees, J. Algebra 360 (2012) 115–157. Crossref, Google Scholar
27. F. Hivert, J.-C. Novelli and J.-Y. Thibon , An analogue of the plactic monoid for binary search trees, in Proc. WORDS’03, TUCS General Publications, Vol. 27 (Turku Centre for Computer Science, Turku, 2003), pp. 27–35. Google Scholar
28. F. Hivert, J.-C. Novelli and J.-Y. Thibon , The algebra of binary search trees, Theoret. Comput. Sci. 339(1) (2005) 129–165. Crossref, ISI, Google Scholar
29. F. Hivert, J.-C. Novelli and J.-Y. Thibon , Trees, functional equations, and combinatorial Hopf algebras, European J. Combin. 29(7) (2008) 1682–1695. Crossref, Google Scholar
30. M. Hoffmann and R. M. Thomas , Biautomatic semigroups, in Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 3623 (Springer, Berlin, 2005), pp. 56–67. Crossref, Google Scholar
31. J. Howie , Fundamentals of Semigroup Theory, LMS Monographs (Clarendon Press, 1995). Google Scholar
32. O. H. Ibarra and B. Ravikumar , On sparseness, ambiguity and other decision problems for acceptors and transducers, in STACS 1986, Lecture Notes in Computer Science, Vol. 210 (Springer, Berlin, 1986), pp. 171–179. Google Scholar
33. R. Incitti , The growth function of context-free languages, Theoret. Comput. Sci. 255(1–2) (2001) 601–605. Crossref, Google Scholar
34. E. G. Karpuz , Complete rewriting system for the Chinese monoid, Appl. Math. Sci. 4 (2010) 1081–1087. Google Scholar
35. M. Kashiwara , On crystal bases, in Representations of Groups, Canadian Mathematical Society Conference Proceedings, Vol. 16 (American Mathematical Society, Providence, RI, 1995), pp. 155–197. Google Scholar
36. Y. Kobayashi , A finitely presented monoid which has solvable word problem but has no regular complete presentation, Theoret. Comput. Sci. 146(1–2) (1995) 321–329. Crossref, Google Scholar
37. D. Krob and J.-Y. Thibon , Noncommutative symmetric functions IV: Quantum linear groups and Hecke algebras at $q = 0$ , J. Algebraic Combin. 6(4) (1997) 339–376. Crossref, ISI, Google Scholar
38. Ł. Kubat and J. Okniński , Identities of the plactic monoid, Semigroup Forum 90 (2015) 100–112. Crossref, Google Scholar
39. A. Lascoux, B. Leclerc and J.-Y. Thibon , Crystal graphs and $q$ -analogues of weight multiplicities for the root system $A_{n}$ , Lett. Math. Phys. 35(4) (1995) 359–374. Crossref, ISI, Google Scholar
40. A. Lascoux and M.-P. Schützenberger , Le monoïde plaxique, in Noncommutative Structures in Algebra and Geometric Combinatorics, Quaderni de “La Ricerca Scientifica”, Vol. 109 (CNR, Rome, 1981), pp. 129–156. Google Scholar
41. M. Latteux and G. Thierrin , On bounded context-free languages, Elektron. Informationsverarb. Kybernetik 20 (1984) 3–8. Google Scholar
42. J.-L. Loday and M. O. Ronco , Hopf algebra of the planar binary trees, Adv. Math. 139(2) (1998) 293–309. Crossref, ISI, Google Scholar
43. M. Lothaire , Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Vol. 90 (Cambridge University Press, Cambridge, 2002). Crossref, Google Scholar
44. J.-C. Novelli , On the hypoplactic monoid, Discrete Math. 217(1–3) (2000) 315–336. Crossref, ISI, Google Scholar
45. F. Otto and Y. Kobayashi , Properties of monoids that are presented by finite convergent string-rewriting systems — A survey, in Advances in Algorithms, Languages, and Complexity, eds. D.-Z. DuK.-I. Ko (Springer US, Boston, MA, 1997), pp. 225–266. Crossref, Google Scholar
46. S. Poirier and C. Reutenauer , Algebres de Hopf de tableaux, Ann. Sci. Math. Québec 19(1) (1995) 79–90. Google Scholar
47. D. Raz , Length considerations in context-free languages, Theoret. Comput. Sci. 183(1) (1997) 21–32. Crossref, Google Scholar
48. M. Rey , Algebraic constructions on set partitions, in Proc. 19th Conf. Formal Power Series and Algebraic Combinatorics, Vol. 4, Nankai University, Tianjin, China (2007), p. 70, www-igm.univ-mlv.fr/∼rey/articles/rey-fpsac07.pdf. Google Scholar
49. M. Rey, A self-dual Hopf algebra on set partitions, preprint (2014), www-igm.univ-mlv.fr/ $\sim$ rey/articles/hopf_set.pdf. Google Scholar
50. N. Ruškuc, Semigroup presentations, Ph.D. thesis, University of St Andrews, St. Andrews (1995). Google Scholar
51. M. V. Sapir , Combinatorial Algebra: Syntax and Semantics (Springer, 2014). Google Scholar
52. C. Schensted , Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961) 179–191. Crossref, ISI, Google Scholar
53. M. Sipser , Introduction to the Theory of Computation, 1st edn. (International Thomson Publishing, 1996). Crossref, Google Scholar
54. R. P. Stanley , Enumerative Combinatorics, Vol. 1, 2nd edn. (Cambridge University Press, New York, NY, USA, 2011). Crossref, Google Scholar
55. H. Thomas and A. Yong , Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm, Adv. Appl. Math. 46(1) (2011) 610–642. Crossref, Google Scholar
56. V. I. Trofimov , Growth functions of some classes of languages, Cybernetics 17(6) (1981) 727–731. Google Scholar

Published: 27 September 2018

- Cited By 1
  - Combinatorics of patience sorting monoids
    Alan J. Cain, António Malheiro and Fábio M. Silva
    1 Sep 2019 | Discrete Mathematics, Vol. 342, No. 9
- Recommended
Vol. 29, No. 01
Metrics
Downloaded 32 times

History

Received 22 June 2017

Accepted 26 August 2018
Keywords
Loading ...

System Upgrade on Tue, May 19th, 2020 at 2am (ET)

The monoids of the patience sorting algorithm

Abstract

References

Recommended