ON SOME FACTORIZATION PROBLEMS

We consider three notions of factorization arising in different framew orks: factorizing languages, factorization of the natural numbers, fac torizing codes. A language X subset of or equal to A is called factor izing if there exists a language Y subset of or equal to A such that XY = A and the product is unambiguous. This is a decidable property f or recognizable languages X. If Ne consider the particular case of una ry alphabets, we prove that finite factorizing languages can be constr ucted by using Krasner factorizations. Moreover, we extend Krasner's a lgorithm to factorizations of An. We introduce a class of languages, t he strong factorizing languages, which are related to the factorizing codes, introduced by Schutzenberger. We characterize strong factorizin g languages having three words.