A non-ambiguous decomposition of regular languages and factorizing codes ?
Given languages Z,L???,Z is L-decomposable (finitely L-decomposable, resp.) if there exists a non-trivial pair of languages (finite languages, resp.) (A,B), such that Z=AL+B and the operations are non-ambiguous. We show that it is decidable whether Z is L-decomposable and whether Z is finitely L-decomposable, in the case Z and L are regular languages. The result in the case Z=L allows one to decide whether, given a finite language S??? , there exist finite languages C,P such that SC?P=?? with non-ambiguous operations. This problem is related to Schtzenberger's Factorization Conjecture on codes. We also construct an infinite family of factorizing codes.
codes formal languages non-ambiguous factorizations