Generalized factorizations of words and their algorithmic properties

We formalize the notion of a factorization of a word, a so-called F-factori zation, introduced in [7] when solving some open problems on word equations . We show that most of the factorizations considered in the literature fit well into that framework, and in particular that central algorithmic proble ms, such as the uniqueness or the synchronizability, remain polynomial time solvable for an important and large class of F-factorizations, namely for regular F-factorizations. (C) 1999 Elsevier Science B.V. All rights reserve d.