کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874279 686507 2014 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Motzkin subposets and Motzkin geodesics in Tamari lattices
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Motzkin subposets and Motzkin geodesics in Tamari lattices
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 114, Issues 1–2, January–February 2014, Pages 31-37
نویسندگان
, ,