A free monoid containing all strongly Bi-singular languages and non-primitive words

ABSTRACT

Let $Q^{\left(i\right)}$, where $i\ge 1$, be the set of ith powers of primitive words. A language is called strongly bi-singular if the minimal-length words in it are neither prefixes nor suffixes of any other word in the language. Strongly bi-singular languages forms a free monoid with respect to the concatenation of languages. The main result of this paper is that if we start with the basis of this free monoid together with the languages $Q^{\left(i\right)}$ for all $i\ge 2$, then the resulting family of languages is a code. So we find a free monoid which properly contains the free monoid of all strongly bi-singular languages.

KEYWORDS:

• Strongly bi-singular language
• code
• free monoid
• primitive word
• non-primitive word
• prefix code

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 68Q45
• 68Q70

Acknowledgments

The authors would like to thank the referees for their valuable suggestions.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by a National Natural Science Foundation of China # 11861071, an Applied Basic Research Program of Science and Technology Department of Yunnan Province of China # 2014FB101, and an Educational Committee Major Natural Science Foundation of Yunnan Province of China # ZD2015013.