Overlapping words, codes, disjunctivity and density of languages

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 ⁿ )=f ⁿ⁻¹ 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.

Keywords:

• Overlapping words
• Overlapping languages
• Overlapping forms

Acknowledgements

This paper was supported by the National Science Council, ROC., under Grant NSC 95-2115-M-156-001.

Additional information

Notes on contributors

Kuo-Hsiang Chen

Email: [email protected]

Yen-Shung Tsai

Email: [email protected]