6533b82bfe1ef96bd128d82a

RESEARCH PRODUCT

On languages factorizing the free monoid

subject

description

A language X⊂A* is called factorizing if there exists a language Y⊂A* such that XY = A* This work was partially supported by ESPRIT-EBRA project ASMICS contact 6317 and project 40% MURST “Algoritmi, Modelli di Calcolo e Strutture Informative”. and the product is unambiguous. First we give a combinatorial characterization of factorizing languages. Further we prove that it is decidable whether a regular language X is factorizing and we construct an automaton recognizing the corresponding language Y. For finite languages we show that it suffices to consider words of bounded length. A complete characterization of factorizing languages with three words and explicit regular expression for the corresponding language Y are also given. Finally we prove a more general result stating that, given two regular languages X and T, it is decidable whether there exists a language Y such that XY=T and the product is unambiguous.