کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437795 690185 2009 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Morphically primitive words
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Morphically primitive words
چکیده انگلیسی

In the present paper, we introduce an alternative notion of the primitivity of words, that–unlike the standard understanding of this term–is not based on the power (and, hence, the concatenation) of words, but on morphisms. For any alphabet Σ, we call a word w∈Σ∗ morphically imprimitive provided that there are a shorter word v and morphisms h,h′:Σ∗→Σ∗ satisfying h(v)=w and h′(w)=v, and we say that w is morphically primitive otherwise. We explain why this is a well-chosen terminology, we demonstrate that morphic (im-) primitivity of words is a vital attribute in many combinatorial domains based on finite words and morphisms, and we study a number of fundamental properties of the concepts under consideration.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 21–23, 17 May 2009, Pages 2148-2161