This paper reports on a study of some combinatorial properties of overlapping words and overlapping languages. A maximal overlapping subword v of u is an overlapping subword of u and any word of a longer length than the word v is not an overlapping subword of u. For a language L, the notation mo(u) and mo(L) are used to represent the maximal overlapping subword of u and the set {mo(u) | u∈L}, respectively. It is true that mo(f n )=f n−1 for each primitive word f and n≥2. It is also shown that for a language L, whether L is a prefix code can be determined by whether mo(L) is a prefix code, and that if mo(L) is dense it always implies that L is dense. Some results concerning a language L satisfying mo(L)=L are provided. Several characterizations between a word w and its overlapping language ⟨ w⟩ are presented.
Acknowledgements
This paper was supported by the National Science Council, ROC., under Grant NSC 95-2115-M-156-001.