Generalized factorizations of words and their algorithmic properties
We formalize the notion of a factorization of a word, a so-called F-factorization, 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 problems, 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 reserved.
factorizations of words regular factorizations