On Non-overlapping Words

Tetsuo MORIYA  Itaru KATAOKA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.3   pp.707-709
Publication Date: 2011/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.707
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
primitive word,  non-overlapping word,  d-primitive word,  context-sensitive,  context-free,  

Full Text: PDF>>
Buy this Article




Summary: 
Let Q be the set of all primitive words over a finite alphabet having at least two letters. In this paper, we study the language D(1) of all non-overlapping (d-primitive) words, which is a proper subset of Q. We show that D(1) is a context-sensitive langauage but not a deterministic context-free language. Further it is shown that [D(1)]n is not regular for n ≥ 1.