کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875514 | 1441963 | 2018 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Avoidability of circular formulas
ترجمه فارسی عنوان
اجتناب از فرمول دایره ای
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
واژه ها، اجتناب از الگو،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Clark has defined the notion of n-avoidance basis which contains the avoidable formulas with at most n variables that are closest to be unavoidable in some sense. The family Ci of circular formulas is such that C1=AA, C2=ABA.BAB, C3=ABCA.BCAB.CABC and so on. For every i⩽n, the n-avoidance basis contains Ci. Clark showed that the avoidability index of every circular formula and of every formula in the 3-avoidance basis (and thus of every avoidable formula containing at most 3 variables) is at most 4. We determine exactly the avoidability index of these formulas.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 726, 23 May 2018, Pages 1-4
Journal: Theoretical Computer Science - Volume 726, 23 May 2018, Pages 1-4
نویسندگان
Guilhem Gamard, Pascal Ochem, Gwenaël Richomme, Patrice Séébold,