Resumen
In the paper, we consider all possible subsets of the set of potential roots forming in some situations semilattices, by intersection and / or by union. Such structures arise in two similar problems in the theory of formal languages. Specifically, for some given finite language, we consider the problem of extracting the root of a given degree and the problem of constructing an optimal inverse morphism, where optimality can be defined, for example, as the length of the maximum word of a language that is an inverse morphic image. In both of the above cases, it is necessary to construct the set of socalled potential roots, i.e., such words of the alphabet in question, for each of which some degree of it is included in the source language. It is important to note that the construction of the set of all potential roots can be performed using a simple polynomial algorithm. Exponential algorithms for both problems are obvious: we just need to sort through all subsets of the set of these potential roots, and choose the appropriate one among these subsets. Therefore, the problem is to describe possible polynomial algorithms for these problems. For both of these problems, the possible existence of two semilattices available on a preconstructed set of subsets of potential roots is of interest. Among other things, in the paper we present the formulation of one important hypothesis of the theory of formal languages, in which we can assert that a special subset of a set of languages, each of which is an inverse morphic image of a given language, forms not only a halflattice by union, but also a halflattice by intersection (and, therefore, a lattice). The first part of the paper contains motivation, definition of basic concepts, after which includes the material, more dedicated the first of the tasks under consideration, i.e., the task of extracting a root from a language.