Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part III. The condition for the existence of a lattice

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 third part of the article, similar to the second part, is more devoted to the second problem, i.e., the  problem of constructing an optimal inverse morphism. We formulate a hypothesis of the theory of formal languages, in which special subsets of the set of potential roots form an intersection semilattice.

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

Melnikov B. Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part II. Constructing an inverse morphism // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. ??. – 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.

Kulakov K., Dimitrov V. Basics of Software Testing. – Petrozavodsk, Publishing House of Petrozavodsk State University. – 2018. – 57 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).

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

Melnikov B., Vakhitova A. Some more on the finite automata // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 1998. – Vol. 5. No. 3. – P. 495–505.

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

Korabelshchikova S., Melnikov B. Maximum prefix codes and subclasses of the context-free languages class // Bulletin of the Northern (Arctic) Federal University. Series: Physics. Mathematics. – Серия: Natural sciences. – 2015. – No. 1. – P. 121–129 (in Russian).

Korabelshchikova S., Melnikov B. Iterations of languages and maximum prefix codes // Bulletin of the Voronezh State University. Series: Physics. Math. – 2015. – No. 2. – P. 106–120 (in Russian). [16] Lombardy S., Sakarovitch J. The universal automaton // Logic and Automata. Amsterdam University Press, 2008, P. 457–504.

Dolgov V., Melnikov B. Constructing universal finite automaton. I. From theory to practical algorithms // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2013. – No. 2. – P. 173– 181 (in Russian).

Dolgov V., Melnikov B. Constructing universal finite automaton. II. Examples of algorithms // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2014. – No. 4. – P. 78–85 (in Russian).

Melnikov B., Dolgov V. Some more algorithms for Conway’s universal automaton // Acta universitatis sapientiae informatica. – 2014. – Vol. 6. No. 1. – P. 5–20.

Melnikov B. The complete finite automaton // International Journal of Open Information Technologies. – 2017. – Vol. 5. No. 10. – P. 9–17.

Singh Sh., Krishna K. On syntactic complexity of circular semiflower automata // Implementation and Application of Automata, CIAA 2018, Lecture Notes in Computer Science, 10977, Springer International Publishing Ag. – 2018. – P. 312–323.

Refbacks

• There are currently no refbacks.

Abava  Кибербезопасность FRUCT 2023

ISSN: 2307-8162