Non-primitive words in the language \(p^ +q^ +\). (English) Zbl 0813.68127

Shyr, H. J.; Yu, S. S.

Soochow J. Math. 20, No. 4, 535-546 (1994).

Summary: Primitive words on a free monoid

•  nLab
•  Wikipedia

\(X^*\) play an important role in algebraic theory

•  nLab
•  Wikipedia

of codes and language theory. It has been shown that if \(p\) and \(q\) are primitive words such that \(p \neq q\), then for some \(m \geq 1\), \(pq^ m\) non-primitive always implies that \(pq^{m+k}\) a primitive word for all \(k \geq 2\). In this note we show that for two primitive words \(p \neq q\), the language \(p^ +\), \(q^ +\) contains at most one non-primitive word. Moreover, if \(p\) and \(q\) are two distinct non-overlapping primitive words, then \(p^ + q^ +\) contain only primitive words.

MSC:

68Q45	Formal languages and automata
68R15	Combinatorics on words

Keywords:

algebraic theory of codes; language theory