On some factorization problems
Marcella Anselmo, Clelia De Felice, Antonio Restivo · Bulletin of the Belgian Mathematical Society - Simon Stevin · 1997
We consider three notions of factorization arising in different frameworks: factorizing languages, factorization of the natural numbers, factorizing codes.A language X ⊆ A * is called factorizing if there exists a language Y ⊆ A * such that XY = A * and the product is unambiguous.This is a decidable property for recognizable languages X.If we consider the particular case of unary alphabets, we prove that finite factorizing languages can be constructed by using Krasner factorizations.Moreover, we extend Krasner's algorithm to factorizations of A n .We introduce a class of languages, the strong factorizing languages, which are related to the factorizing codes, introduced by Schützenberger.We characterize strong factorizing languages having three words.