کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435705 689929 2015 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Periodicity forcing words
ترجمه فارسی عنوان
دوره ای مجبور کردن کلمات
کلمات کلیدی
برابری مجموعه، مورفیسم ها، مشکل مکاتبه دوطرفه، دوره ای مجبور کردن مجموعه ها، دوره ای کلمات را تحریک می کند ابهام مورفیزم ها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The Dual Post Correspondence Problem asks, for a given word α, if there exists a non-periodic morphism g and an arbitrary morphism h   such that g(α)=h(α)g(α)=h(α). Thus α satisfies the Dual PCP if and only if it belongs to a non-trivial equality set. Words which do not satisfy the Dual PCP are called periodicity forcing, and are important to the study of word equations, equality sets and ambiguity of morphisms. In this paper, a ‘prime’ subset of periodicity forcing words is presented. It is shown that when combined with a particular type of morphism it generates exactly the full set of periodicity forcing words. Furthermore, it is shown that there exist examples of periodicity forcing words which contain any given factor/prefix/suffix. Finally, an alternative class of mechanisms for generating periodicity forcing words is developed, resulting in a class of examples which contrast those known already.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 601, 11 October 2015, Pages 2–14
نویسندگان
, , ,