On the Decomposition of Finite Languages
Alexandru Mateescu, Arto K. Salomaa, Sheng Yü · 1998
Representations of finite languages as a product (catenation) of languages are investigated, where the factor languages are "prime", that is, cannot be decomposed further in a nontrivial manner. In general, such prime decompositions are not unique - even the number of factors can vary exponentially. The paper investigates the uniqueness of prime decompositions, as well as the commuting of the factors. Interconnections to languages more general than finite are pointed out. In the case of regular languages, the notion of a decomposition set turns out to be a powerful tool. TUCS Research Group