کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949630 | 1440199 | 2017 | 29 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An algorithm computing combinatorial specifications of permutation classes
ترجمه فارسی عنوان
یک الگوریتم محاسبات ترکیبی از خصوصیات کلاس های تعویض
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This article presents a methodology that automatically derives a combinatorial specification for a permutation class C, given its basis B of excluded patterns and the set of simple permutations in C, when these sets are both finite. This is achieved considering both pattern avoidance and pattern containment constraints in permutations. The obtained specification yields a system of equations satisfied by the generating function of C, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in C. The method presented is fully algorithmic.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 224, 19 June 2017, Pages 16-44
Journal: Discrete Applied Mathematics - Volume 224, 19 June 2017, Pages 16-44
نویسندگان
Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, Carine Pivoteau, Dominique Rossin,