Semi-­lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language

Boris Melnikov

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 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.

Full Text:

PDF (Russian)

References


Melnikov B., Korabelshchikova S., Dolgov V. On the task of extracting the root from the language // International Journal of Open Information Technologies. – 2019. – Vol. 7. No. 3. – P. 1–6.

Melnikov B. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundation of Computer Science. – 1993. – Vol. 4. No. 3. – P. 267–274.

Alekseeva A., Melnikov B. Iterations of finite and infinite languages and nondeterministic finite automata // Vector of Science of Togliatti State University. – 2011. – No. 3 (17). – P. 30–33 (in Russian).

Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part I // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 4. – P. 1–11 (in Russian).

Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part II // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 5. – P. 1–11 (in Russian).

Melnikov B. Variants of finite automata, corresponding to infinite iterative morphism trees. Part I // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 7. – P. 5–13 (in Russian).

Melnikov B. Variants of finite automata, corresponding to infinite iterative morphism trees. Part II // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 10. – P. 1–8 (in Russian).

Melnikov B., Melnikova A. Polynomial algorithm of construction a finite automaton for checking equality infinite iterations of two finite languages // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 11. – P. 1–10 (in Russian).

Melnikov B., Melnikova A. Some properties of the basis finite automaton // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 2002. – Vol. 9. No. 1. – P. 135–150.

Melnikov B., Sciarini­Guryanova N. Possible edges of a finite automaton defining a given regular language // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 2002. – Vol. 9. No. 2. – P. 475–485.

Melnikov B., Sayfullina M. On some algorithms of equivalent transformation of nondeterministic finite automata // News of higher educational institutions. Mathematics. – 2009. – No. 4. – P. 67–72 (in Russian).

Skornyakov L. (Ed.) General Algebra. Vol. 2. – Moscow, Nauka. – 1991. – 480 p. (in Russian).

Salomaa A. Jewels of Formal Language Theory. Computer Science Press, Rockville, Maryland. – 1981. – 144 p.

Korabelshchikova S., Melnikov B. Iterations of languages and maximum prefix codes // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2015. – No. 2. – P. 106–120 (in Russian).

Yablonskiy S. Introduction to Discrete Mathematics. Study Guide for Universities. – Moscow, Vysshaya Shkola. – 2001. – 384 p. (in Russian).

Lallement G. textitSemigroups and Combinatorial Applications. – NY, John Wiley & Sons. – 1979. – 376 p.

Novikov F. Discrete mathematics for programmers. – Saint Petersburg, Piter. – 2009. – 304 p. (in Russian).

Melnikov B. Description of special submonoids of the global supermonoid of the free monoid // News of higher educational institutions. Mathematics. – 2004. – No. 3. – P. 46–56 (in Russian).


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162