Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874279 | Information Processing Letters | 2014 | 7 Pages |
Abstract
The Tamari lattice of order n can be defined by the set Dn of Dyck words endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we study this rotation on the restricted set of Motzkin words. An upper semimodular join semilattice is obtained and a shortest path metric can be defined. We compute the corresponding distance between two Motzkin words in this structure. This distance can also be interpreted as the length of a geodesic between these Motzkin words in a Tamari lattice. So, a new upper bound is obtained for the classical rotation distance between two Motzkin words in a Tamari lattice. For some specific pairs of Motzkin words, this bound is exactly the value of the rotation distance in a Tamari lattice. Finally, enumerating results are given for join and meet irreducible elements, minimal elements and coverings.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
J.-L. Baril, J.-M. Pallo,