Is there any algebraic structure on Dyck words of length $2n$ or full binary trees of $n+1$ leaves?

152 Views Asked by At

Just out of curiosity, I wonder if there are researches about algebraic structures on Dyck words of length $2n$ or (equivalently) full binary trees of $n+1$ leaves (with fixed $n \in \mathbb{Z}^+$).

As a matter of fact, that two sets have the same number of elements: the $n^{th}$ Catalan number $C_n$.

I've googled but got no result.

Thanks in advance.

1

There are 1 best solutions below

0
On

There is actually a huge literature on this topic. See Chapter 11, Words and trees, in [2] and Lemma 9.3.1 in [4] for your specific question. See the notes of Chapter 9 in [3] for (many) relevant references. Reference [3] doesn't address your question but is still a good reference on algebra over words. For an algebraic theory of context-free languages, see [2] and Chapter 2 in [1]

[1] Berstel, Jean. Transductions and context-free languages. Leitfäden der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics], 38. B. G. Teubner, Stuttgart, 1979. 278 pp. ISBN: 3-519-02340-7

[1] Berstel, J.; Boasson, L. Towards an algebraic theory of context-free languages, Fund. Inform. 25 (1996), no. 3-4, 217--239

[2] Lothaire, M. Combinatorics on words. With a foreword by Roger Lyndon and a preface by Dominique Perrin. Corrected reprint of the 1983 original, with a new preface by Perrin. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. xviii+238 pp. ISBN: 0-521-59924-5

[3] Lothaire, M. Algebraic combinatorics on words. A collective work by Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desarmenien, Volker Diekert, Tero Harju, Juhani Karhumaki and Wojciech Plandowski. With a preface by Berstel and Perrin. Encyclopedia of Mathematics and its Applications, 90. Cambridge University Press, Cambridge, 2002. xiv+504 pp. ISBN: 0-521-81220-8 MR1905123

[4] Lothaire, M. Applied combinatorics on words. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. With a preface by Berstel and Perrin. Encyclopedia of Mathematics and its Applications, 105. Cambridge University Press, Cambridge, 2005. xvi+610 pp. ISBN: 978-0-521-84802-2; 0-521-84802-4