On a Hypothesis of the Theory of Formal Languages. Part I
DOI:
https://doi.org/10.14529/cmse230305Keywords:
formal languages, iterations of languages, binary relations, morphisms, inverse morphisms, algorithms, polynomial algorithmsAbstract
The main subject of the article is the consideration of problems arising in the study of the necessary conditions for the equality of infinite iterations of finite languages. In previous publications, the author considered examples of the application of a special binary equivalence relation corresponding to this equality in a set of finite languages, and considered both examples describing the necessary conditions for its implementation and examples of its use. Further reducing the problem under consideration is applied to one of such necessary conditions: to finite automata and to infinite iterative trees. In addition, the article presents several variants of the formulation of an important hypothesis on the set of finite languages, its study also provides other options for reducing the problem under consideration to special problems of studying nondeterministic finite automata. At the same time, if the formulated hypothesis is fulfilled, some of these problems are solved in polynomial time, and some are not; with the continuation of work on this topic, the last fact may make it possible to reformulate the problem P=NP in the form of a special problem of the theory of formal languages.References
Melnikov B.F., Korabelshchikova S.Yu., Dolgov V.N. 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.F., Melnikova A.A. Some more on w-finite automata and w-regular languages. Part I: The main definitions and properties. International Journal of Open Information Technologies. 2020. Vol. 8, no. 8. P. 1–7.
Melnikov B.F., Melnikova A.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.F., Melnikova A.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.F. 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.F. 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.F., Melnikova A.A. A polynomial algorithm for constructing a finite automaton to check 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).
Melnikov B.F. 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.F. 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. 5. P. 1–8. (in Russian).
Melnikov B.F. 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. International Journal of Open Information Technologies. 2022. Vol. 10, no. 7. P. 1–9. (in Russian).
Melnikov B.F. Petal finite automata: basic definitions, examples and their relation to complete automata. Part I. International Journal of Open Information Technologies. 2022. Vol. 10, no. 9. P. 1–11. (in Russian).
Melnikov B.F. Petal finite automata: basic definitions, examples and their relation to complete automata. Part II. International Journal of Open Information Technologies. 2022. Vol. 10, no. 10. P. 1–10. (in Russian).
Melnikov B.F. Regular languages and nondeterministic finite automata (monograph). Moscow: Russian State Social University Ed., 2018. (in Russian). 179 p.
Melnikov B.F. The equality condition for infinite catenations of two sets of finite words. International Journal of of Foundations of Computer Science. 1993. Vol. 4, no. 3. P. 267–273. (in Russian).
Melnikov B.F. 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).
Alekseeva A.G., Melnikov B.F. Iterations of finite and infinite languages and nondeterministic finite automata. Vektor nauki of Togliatti State University. 2011. No. 3 (17). P. 30–33. (in Russian).
Hopcroft R., Motwani R., Ullman J. Introduction to Automata Theory, Languages, and Computation. Massachusetts: Addison-Wesley Publishing Company Reading, 2006. 530 p.
Hromkovič J. Theoretical Computer Science. Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Berlin: Springer, 2003. 323 p.
Melnikov B.F. Once more on the edge-minimization of nondeterministic finite automata and the connected problems. Fundamenta Informaticae. 2010. Vol. 104, no. 3. P. 267–283.
Aho A., Ullman J. The Theory of Parsing, Translation, and Compiling. Vol. 1: Parsing NJ: Prentice Hall, 1972. 560 p.
Melnikov B.F. The complete finite automaton. International Journal of Open Information Technologies. 2017. Vol. 5, no. 10. P. 9–17.
Yablonskiy S.V. Introduction to Discrete Mathematics. Moscow: Vysshaya shkola, 2003. 384 p. (in Russian).
