d-Primitive Words and D(1)-Concatenated Words

Itaru KATAOKA  Tetsuo MORIYA  

IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.8   pp.1577-1579
Publication Date: 2009/08/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.1577
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Automata and Formal Language Theory
primitive word,  d-primitive word,  regular component,  

Full Text: PDF>>
Buy this Article

In this paper, we study d-primitive words and D(1)-concatenated words. First we show that neither D(1), the set of all d-primitive words, nor D(1)D(1), the set of all D(1)-concatenated words, is regular. Next we show that for u, v, w ∈Σ+ with |u|=|w|, uvwD(1) if and only if uv+wD(1). It is also shown that every d-primitive word, with the length of two or more, is D(1)-concatenated.