Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part II. Construction of an inverse morphism

Abstract

In the paper, we consider all possible subsets of the set of potential roots forming in some situations semi-lattices, 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 so-called 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 semi-lattices available on a pre-constructed 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 half-lattice by union, but also a half-lattice by intersection (and, therefore, a lattice). The proposed second part of the paper is more devoted to the second of the problems under consideration, i.e., to the problem of constructing an optimal inverse morphism.