On a special class of primitive words

详细信息    查看全文

• 作者：Elena Czeizler ; Lila Kari ; Shinnosuke Seki
• 关键词：Word equations ; Fine and Wilf theorem ; (Pseudo-)periodicity ; (Pseudo-)power ; (Pseudo-)primitivity ; (Anti-)morphic involution
• 刊名：Theoretical Computer Science
• 出版年：2010
• 出版时间：6 January 2010
• 年：2010
• 卷：411
• 期：3
• 页码：617-630
• 全文大小：1494 K

文摘

When representing DNA molecules as words, it is necessary to take into account the fact that a word u encodes basically the same information as its Watson–Crick complement θ(u), where θ denotes the Watson–Crick complementarity function. Thus, an expression which involves only a word u and its complement can be still considered as a repeating sequence. In this context, we define and investigate the properties of a special class of primitive words, called pseudo-primitive words relative to θ or simply θ-primitive words, which cannot be expressed as such repeating sequences. For instance, we prove the existence of a unique θ-primitive root of a given word, and we give some constraints forcing two distinct words to share their θ-primitive root. Also, we present an extension of the well-known Fine and Wilf theorem, for which we give an optimal bound.