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

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

Full Text:

PDF (Russian)

References


Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part I. Extracting the root from the language // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 4. – P. 1–9 (in Russian).

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

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

Novikov F. Discrete mathematics for programmers. – Saint Petersburg, Piter. – 2009. – 304 p. (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).

Abramyan M., Melnikov B. Algorithms of transformation of finite automata, corresponding to infinite iterative trees // Modern information technologies and IT education. – 2021. – Vol. 17. No. 1. – P. 13–23. (in Russian).

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

Graham R., Knuth D., Patashnik O. Concrete Mathematics. A foundation for computer science. – USA, Addison-Wesley Professional. – 1994. – xiv+657 p.

Melnikov B. Subclasses of the context-free languages class (monograph). – Moscow, Moscow State University Ed. – 1995. – 174 p. –

ISBN 5-211-03448-1. (in Russian).

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. Regular languages and nondeterministic finite automata (monograph). – Moscow, Russian Social State University Ed. – 2018. – 179 p. – ISBN 978-5-7139-1355-7. (in Russian).

Skornyakov L. (Ed.) General Algebra. Vol. 1. – Moscow, Nauka. – 1990. – 592 p. (in Russian).

Hausdorff F. Grundzüge der Mengenlehre. – Grundzüge der Mengenlehre, von Veit. – 1914. – ISBN 978-0-8284-0061-9. (Reprinted by Chelsea Publishing Company in 1949.)

Gurov S. Boolean algebras, ordered sets, lattices: definitions, properties, examples. – Moscow, Librokom. – 2013. – 352 p. (in Russian).

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.


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2020

ISSN: 2307-8162