patternMinor
Primitive word and cyclic rotations
Viewed 0 times
primitiverotationswordandcyclic
Problem
Definition. A word $w \in \Sigma^*$ is primitive if $w=u^n \rightarrow n=1$.
Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?
Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?
Solution
Yes, this is true. The direct implication ($\Rightarrow$) is the hardest to prove, and you will need the following lemma: two words commute if and only if they are powers of the same word (R.C. Lyndon and M.P. Schützenberger, The equation a M = bncp in a free group, Michigan Math. J.
9 (1962) 289-298. Or in this: H. Petersen, On the language of primitive words, Theor. Comp. Sci., 1996 https://doi.org/10.1016/0304-3975(95)00098-4). The rest of the proof should be straightforward enough.
9 (1962) 289-298. Or in this: H. Petersen, On the language of primitive words, Theor. Comp. Sci., 1996 https://doi.org/10.1016/0304-3975(95)00098-4). The rest of the proof should be straightforward enough.
Context
StackExchange Computer Science Q#119600, answer score: 5
Revisions (0)
No revisions yet.