An application of the matrix representation of transductions (Q1057659)

The paper deals with the following classical problem of formal language theory: given \(n\) languages \(L_ 1, L_ 2,\dots, L_ n\) recognized by the monoids \(M_ 1, M_ 2,\dots, M_ n\), respectively, and given an operation \(\phi\), find a monoid \(M\) recognizing the language \(\phi (L_ 1,\dots, L_ n)\). The author proves that most of the constructions given in the literature for solving this problem are particular cases of a general method based on considering the operation \(\phi\) as the inverse of a transduction. The procedure is not universal: the complementation and the star operation cannot be processed in this way, but a lot of operations can be approached in this way (union, intersection, inverse substitutions, quotient, concatenation, shuffle and so on, including the control operation on TOL systems).