Back to Search
Start Over
An extension of the Lyndon–Schützenberger result to pseudoperiodic words
- Source :
-
Information & Computation . Apr2011, Vol. 209 Issue 4, p717-730. 14p. - Publication Year :
- 2011
-
Abstract
- 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 . Thus, any expression consisting of repetitions of u and 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 , to cases where both sides involve repetitions of words as well as their complements. Our main results show that, for such extended equations, if , then all three words involved can be expressed in terms of a common word t and its complement . Moreover, if , then 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 , which is also obtained in this paper. [Copyright &y& Elsevier]
- Subjects :
- *EQUATIONS
*ALGEBRA
*MATHEMATICS
*POLYNOMIALS
*GENERALIZATION
*NUMERICAL analysis
*DNA
Subjects
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 209
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 58755968
- Full Text :
- https://doi.org/10.1016/j.ic.2011.01.001