An extension of the Lyndon-Schützenberger result to pseudoperiodic words

Reference:

Elena Czeizler, Eugen Czeizler, Lila Kari, and Shinnosuke Seki. An extension of the lyndon-schützenberger result to pseudoperiodic words. Information and computation, 209(4):717–730, 2011.

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 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 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 and its complement , which is also obtained in this paper.

Keywords:

Pseudoperiodic word; (extended) Lyndon–Schützenberger equation; Pseudo-primitive word; Antimorphic involution; Non-trivial overlap

Suggested BibTeX entry:

@article{CzCKS11,
    author = {Elena Czeizler and Eugen Czeizler and Lila Kari and Shinnosuke Seki},
    journal = {Information and computation},
    language = {eng},
    number = {4},
    pages = {717--730},
    title = {An extension of the Lyndon-Sch{\"u}tzenberger result to pseudoperiodic words},
    volume = {209},
    year = {2011},
}