TITLE:
On Some Problems of Extracting the Root from a Given Finite Language
AUTHORS:
Boris F. Melnikov, Aleksandra A. Melnikova
KEYWORDS:
Formal Languages, Iterations of Languages, Root Extraction, Algorithms, The Boolean
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.11 No.5,
May
31,
2023
ABSTRACT:
Based on the standard definition of the product (concatenation), the natural non-negative degree of the language is introduced. Root extraction is the reverse operation to it, and it can be defined in several different ways. Despite the simplicity of the formulation of the problem of extracting the root, the authors could not find any description of it in the literature (as well as on the Internet), including even its formulation. Most of the material in this article is devoted to the simplest version of the formulation: the root of the 2nd degree for the 1-letter alphabet, but many of the provisions of the article are generalized to more complex cases. Apparently, for a possible future description of a polynomial algorithm for solving at least one of the described statements of root extraction problems, it is first necessary to really analyze in detail such a special case, that is: either describe the necessary polynomial algorithm, or, conversely, show that the problem belongs to the class of NP-complete problems. Thus, in this article, we do not propose a polynomial algorithm for the problems under consideration; however, the models described here should help in constructing appropriate heuristic algorithms for their solution. A detailed description of the possible further application of such heuristic algorithms is beyond the scope of this article.