Normal forms of quasiperiodic strings

Here we consider the problem of computing normal forms of quasiperiodic strings. A string x is quasiperiodic if it can be constructed by concatenation and superpositions of one of its proper factor (cover). The notion of quasiperiodicity is a generalization of periodicity in the sense that superpositions as well as concatenations are allowed to define it. It is shown here that given a quasiperiodic string x, there exists a unique factorization of x into roots of its shortest cover and how we can efficiently build such a factorization in linear time. These forms can be used, for example, to test whether or not a string v covers x(k) for some integer k, where v covers x. (C) 2000 Elsevier Science B.V. All rights reserved.