کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875514 1441963 2018 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Avoidability of circular formulas
ترجمه فارسی عنوان
اجتناب از فرمول دایره ای
کلمات کلیدی
واژه ها، اجتناب از الگو،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , ,