کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437284 | 690108 | 2012 | 27 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Intervals of balanced binary trees in the Tamari lattice
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We show that the set of balanced binary trees is closed by interval in the Tamari lattice. We establish that the intervals [T,T′], where T and T′ are balanced binary trees are isomorphic as posets to a hypercube. We introduce synchronous grammars that allow to generate tree-like structures and obtain fixed-point functional equations to enumerate these. We also introduce imbalance tree patterns and show that they can be used to describe some sets of balanced binary trees that play a particular role in the Tamari lattice. Finally, we investigate other families of binary trees that are also closed by interval in the Tamari lattice.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 420, 24 February 2012, Pages 1-27
Journal: Theoretical Computer Science - Volume 420, 24 February 2012, Pages 1-27