×

Factorizations of languages and commutativity conditions. (English) Zbl 1065.68063

Summary: 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 \(L_1\) and \(L_2\) is discussed under the assumption \(L_1 L_2= L_2 L_1\).

MSC:

68Q45 Formal languages and automata