d-Words and d-languages

Abstract

Let X be a finite alphabet containing more than one letter. A d-primitive word u over X is a non-overlapping word in the sense that no proper prefix of u is a suffix of u. D(1) is the set of all d-primitive words over X and D is the set of all positive powers of all words in D(1). Every language in D will be called a d-language. In this paper, we study some algebraic properties of d-primitive words and d-languages relative to formal language theory and codes. We,show that there are infinitely many cyclic-square-free words over alphabet with three letters. A characterization of three elements codes in D(1) is obtained and we prove that every regular component in D(1) is either a prefix code or a suffix code.