Semilattice of roots from formal languages of a special kind

Abstract

This article presents the result of studying the structure of a set of roots from languages of a special type, namely containing all possible words of length from t₁ to t₂ (t₁ £ t₂). The General case of extraction of n-th degree roots from a given language is studied; algorithms for finding all roots from the language, primitive roots, as well as the results of the programs that implement the proposed algorithms are given.

The problem under consideration is reduced to the problem of the backpack and is solved by the method of software implementation of the proposed algorithms. On the set of roots from the language, the order relation is set, the minimum and maximum elements are defined. The paper shows that the set of roots from languages of a special type is either empty or forms an upper semilattice, the minimum elements of which are the primitive roots, and the maximum element is the trivial root from the given language.

There are clear simple examples that illustrate the ambiguity of the operation of extracting a root from a language, the relationship between sets of roots from two languages with equally cardinal number of index sets, the properties of primitive roots, and the structure of the semilattice of roots. The results obtained can be used for a compact description of sets of roots and similar sets, as well as for their quantitative estimates.