An extension of the Lyndon-Schützenberger result to pseudoperiodic words |
| |
Authors: | Elena Czeizler |
| |
Affiliation: | Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7 |
| |
Abstract: | One of the particularities of information encoded as DNA strands is that a string u contains basically the same information as its Watson-Crick complement, denoted here as θ(u). Thus, any expression consisting of repetitions of u and θ(u) can be considered in some sense periodic. In this paper, we give a generalization of Lyndon and Schützenberger’s classical result about equations of the form ul=vnwm, to cases where both sides involve repetitions of words as well as their complements. Our main results show that, for such extended equations, if l?5,n,m?3, then all three words involved can be expressed in terms of a common word t and its complement θ(t). Moreover, if l?5, then n=m=3 is an optimal bound. These results are established based on a complete characterization of all possible overlaps between two expressions that involve only some word u and its complement θ(u), which is also obtained in this paper. |
| |
Keywords: | Pseudoperiodic word (extended) Lyndon-Schü tzenberger equation Pseudo-primitive word Antimorphic involution Non-trivial overlap |
本文献已被 ScienceDirect 等数据库收录! |
|