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

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