A non-ambiguous decomposition of regular languages and factorizing codes

摘要

Given languages Z, L is contained in ∑~*, 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 and regular languages. The result in the case Z=L allows one to decide whether, given a finite language S is contained in ∑~*, there exist finite languages C,P such that SC~*P = ∑~* with non-ambiguous operations. This problem is related to Schutzenberger's Factorization Conjecture on codes. We also construct an infinite family of factorizing codes.