On an interesting hypothesis of the theory of formal languages

Document Type : Full Length Article

Author

Shenzhen MSU-BIT University

Abstract

The formulation of a hypothesis for any pair of nonempty finite languages is considered. The hypothesis consists in the formulation of the necessary conditions for the equality of infinite iterations of these languages, the paper provides some equivalent versions of this hypothesis. When fulfilling this hypothesis, we show the possibility of verifying the equality of infinite iterations of these languages in polynomial time. On the other hand, we present a plan for reducing the verification of the same equality to checking the completeness of the language of a specially constructed nondeterministic finite automaton, and such a check cannot be carried out in polynomial time. In this regard, the possibility of reducing the equality P=NP to the special hypothesis of the theory of formal languages is formulated.

Graphical Abstract

On an interesting hypothesis of the theory of formal languages

Keywords

Main Subjects


[1] B. Melnikov, On a classification of sequential context-free languages and grammars, Vestnik of Moscow University, series ”Computational mathematics and cybernetics”, 3 (1993) 64–69 (in Russian).
[2] O. Dubasova, B. Melnikov, On an extension of the class of context-free languages, Programming and Computer Software, 21(6) (1995) 299–306.
[3] G. S´enizergues, L(A)=L(B)? Decidability results from complete formal systems, Theoretical Computer Science, 251(1–2) (2001) 1–166.
[4] B. Melnikov, A. Melnikova, A polynomial algorithm for construction an automaton for checking the equality of infinite iterations of two finite languages, Lecture Notes in Networks and Systems, 502 (2022) 521–530.
[5] B. Melnikov, The equality condition for infinite catenations of two sets of finite words, International Journal of Foundation of Computer Science, 4(3) (1993) 267–274.
[6] B. Melnikov, L. Meng, Eight variants of finite automata for checking the fulfillment of the coverage relation of iterations of two finite languages. Part I, International Journal of Open Information Technologies, 11(11) (2023) 1–9 (in Russian).
[7] B. Melnikov, L. Meng, Eight variants of finite automata for checking the fulfillment of the coverage relation of iterations of two finite languages. Part II, International Journal of Open Information Technologies, 12(2) (2024) 1–11 (in Russian).
[8] B. Melnikov, Variants of finite automata corresponding to infinite iterative morphism trees. Part I, International Journal of Open Information Technologies, 9(7) (2021) 5–13 (in Russian).
[9] B. Melnikov, Variants of finite automata corresponding to infinite iterative morphism trees. Part II, International Journal of Open Information Technologies, 9(10) (2021) 1–8 (in Russian).
[10] B. Melnikov, Once more on the edge-minimization of nondeterministic finite automata and the connected problems, Fundamenta Informaticae, 104(3) (2010) 267–283.
[11] B. Melnikov, 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, 10(4) (2022) 1–9 (in Russian).
[12] B. Melnikov, Semi-lattices of the subsets of potential roots in the problems of the formal languages theory. Part II. Constructing an inversemorphism, InternationalJournalofOpenInformationTechnologies, 10(5) (2022) 1–8 (in Russian).
[13] B. Melnikov, 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, 10(7) (2022) 1–9 (in Russian).
[14] B. Melnikov, Petal finite automata: basic definitions, examples and their relation to complete automata. Part I, International Journal of Open Information Technologies, 10(9) (2022) 1–11 (in Russian).
[15] B. Melnikov, Petal finite automata: basic definitions, examples and their relation to complete automata. Part II, International Journal of Open Information Technologies, 10(10) (2022) 1–10 (in Russian).
Volume 9, Issue 2
June 2024
Pages 81-102
  • Receive Date: 17 April 2024
  • Revise Date: 25 April 2024
  • Accept Date: 17 May 2024
  • Publish Date: 01 June 2024