Article ID Journal Published Year Pages File Type
437795 Theoretical Computer Science 2009 14 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics