TY - JOUR
AU - Alexandru Mateescu
AU - Arto Salomaa
AU - Sheng Yu
PY - 2002/01/01
Y2 - 2023/12/06
TI - Factorizations of languages and commutativity conditions
JF - Acta Cybernetica
JA - Acta Cybern
VL - 15
IS - 3
SE - Regular articles
DO -
UR - https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3583
AB - Representations of 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 do not necessarily exist. If they exist, they are not necessarily unique - the number of factors can vary even exponentially. The paper investigates prime decompositions, as well as the commuting of the factors, especially for the case of finite languages. In particular, a technique about commuting is developed in Section 4, where the factorization of languages L1 and L2 is discussed under the assumption L1L2 = L2L1.
ER -