کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429985 687761 2015 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cubic patterns with permutations
ترجمه فارسی عنوان
الگوهای مکعبی با جایگزینی
کلمات کلیدی
ترکیبیات بر روی کلمات، الگوهای قابل اجتناب، شبه دادرسی تغییرات
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We consider a generalisation of the classical problem of pattern avoidance in infinite words with functional dependencies between pattern variables. More precisely, we consider patterns involving permutations. The foremost remarkable fact regarding this new setting is that the notion of avoidability index (the smallest alphabet size for which a pattern is avoidable) is meaningless, since a pattern with permutations that is avoidable in one alphabet can be unavoidable in a larger alphabet. We characterise the (un-)avoidability of all patterns of the form πi(x)πj(x)πk(x)πi(x)πj(x)πk(x), called cubic patterns with permutations here, for all alphabet sizes in both the morphic and antimorphic case.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 81, Issue 7, November 2015, Pages 1298–1310
نویسندگان
, , ,