Word insertions and primitivity

Abstract

In this paper we consider relations between the operation of word insertion and primitivity. A necessary and sufficient condition under which the insertion u ← u of the word u into itself has maximum cardinality is obtained. The notion of insertion sequence is introduced and sufficient conditions under which an insertion sequence is a special type of language (regular, context-free, biprefix code) are obtained. Based on the operations of insertion, shuffle and commutative shuffle (which generalize catenation), the notions of ins-primitive words, shuffle-primitive words, and com-shuffle-primitive words are defined and investigated. These notions turn out to be generalizations of the classical notion of primitive words.