On the complex of problems for the study of the necessary conditions for the equality of infinite iterations of finite languages

Boris Melnikov

Abstract


In some previous publications, we investigated the properties of a special binary relation, which was sometimes called the equivalence relation at infinity. For a pair of finite languages, the equality of infinite iterations of these languages is necessary and sufficient to fulfill this relationship. Earlier, we considered examples of the application of this relation: both examples describing the necessary conditions for its implementation, and examples of its use in various fields of formal language theory. The problems considered in this paper can be called the tasks of investigating the necessary conditions for the equality of infinite iterations of finite languages, building algorithms based on these conditions to verify that a finite language belongs to a set of morphic images of extended maximal prefix codes and algorithms for constructing corresponding morphisms, as well as the use of such algorithms in some problems of the theory of formal languages. The main subject of the paper is motivation to consider such tasks. And, apparently, the main “component” of such motivation is the plan of proving the possibility of reducing the equality P = NP to the special hypothesis of the theory of formal languages formulated earlier in one of our previous publications. It is worth noting that the first version of this plan was published by us in 2011; here is an amended version, and with a much larger number of comments. However, the basic idea is the same, but here it has already been formalized specifically, and the solutions to many auxiliary subproblems necessary for the implementation of such a plan have already been published over the past time. Briefly, this basic idea can be formulated as follows. For some nondeterministic finite automaton, a pair of finite languages is constructed in a special way, and for this pair it is shown that if the above hypothesis were fulfilled, then there would be an algorithm for checking the fulfillment of the equivalence relation at infinity in polynomial time. But, on the other hand, taking an arbitrary nondeterministic finite automaton and considering it as an NSPRI automaton defined in our previous publications, we could construct a pair of finite languages corresponding to this automaton in polynomial time; and this pair satisfies the equivalence relation at infinity if and only if the language of the NSPRI automaton coincides with the universal language over a given alphabet (i.e., a language containing all possible words). Thus, the fulfillment of the above hypothesis entails the fulfillment of the equality P = NP.


Full Text:

PDF (Russian)

References


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. The polynomial algorithm for checking execution conditions of the extended morphic image maximum prefix code // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 12. – P. 1–9 (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.

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

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

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

Bratko I. Prolog Programming for Artificial Intelligence. – London, Pearson. – 2012. – 696 p.

Melnikov B., Terentyeva Y. Building an optimal spanning tree as a tool for ensuring the stability of the communication

network // News of higher educational institutions. Volga region. Technical sciences. – 2021. – No. 1 (57). – P. 36–54 (in Russian).

Melnikov B., Terentyeva Y. Building communication networks: on the application of the Kruskal’s algorithm in the problems of large dimensions // IOP Conference Series: Materials Science and Engineering. – 2021. С. 12089. International Journal of Open Information Technologies ISSN: 2307-8162 vol. 10, no. ??, 2022

Kuznetsov S. Databases. – Moscow, Edition of Department of Computational Mathematics and Cybernetics of Moscow State University. – 2020. – 255 p. (in Russian).

Aho A., Ullman J. The Theory of Parsing, Translation, and Compiling. Vol. 1: Parsing. NJ: Prentice Hall, 1972. – 560 p.

Hopcroft J., Motwani R., Ullman J. Introduction to Automata Theory, Languages, and Computation. Massachusetts,

Addison-Wesley Publishing Company Reading. – 2006. – 550 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).

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. Algorithm for checking equality of infinite iterations of finite languages // Bulletin of the Moscow University. Series 15: Computational Mathematics and Cybernetics. – 1996. – No. 4. – P. 49–56 (in Russian).

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

Melnikov B. Some consequences of the equivalence condition of unambiguous bracketed grammars // Bulletin of the Moscow University. Series 15: Computational Mathematics and Cybernetics. – 1991. – No. 10. – P. 51–54 (in Russian).

Dubasova O., Melnikov B. On an extension of the class of context-free languages // Programming and Computer Software (Russian Academy of Sciences Ed.). – 1995. – No. 6. – P. 46–54 (in Russian).

Melnikov B., Kashlakova E. Some grammatical structures of programming languages as simple bracketed languages // Informatica (Lithuanian Academy of Sciences). – 2000. – Vol. 11. No. 4. – P. 441–454.

Ginsburg S. The mathematical theory of context free languages. NY, McGraw-Hill Book Company. – 1966. – 232 p.

Staneviciené L. On a tool for the study of context-free languages // Cybernetics. – 1989. – No. 4. – P. 135–136 (in Russian).

Staneviciené L. D-graphs in context-free language theory //Informatica (Lithuanian Academy of Sciences). – 1997. – Vol. 8. No. 1. – P. 43–56.

Meytus V. The solvability of the equivalence problem of deterministic push-down automata // Cybernetics and System Analysis. – 1992. – No. 5. – P. 20–45 (in Russian).

Sénizergues G. L(A) = L(B)? decidability results from complete formal systems // Theoretical computer science. – 2001. – Vol. 251. No. 1–2. – P. 1–166.

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

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

Dang V. V., Korabelshchikova S., Melnikov B. About the problem of finding minimal approximation semigroup // News of higher educational institutions. Volga region. Physical and Mathematical sciences. – 2015. – No. 3 (35). – P. 88–99 (in Russian).

Dolgov V., Melnikov B., Melnikova A. Cycles of the transition graph of a basic finite automaton and related issues // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2016. – No. 4. – P. 95–111 (in Russian).

Melnikov B. Extended nondeterministic finite automata //Fundamenta Informaticae. – 2010. – Vol. 104, No. 3. – P. 255–265.

Melnikov B., Melnikova A. Extended basis finite automaton. Part I. Basic definitions // International Journal of Open Information Technologies. – 2019. – Vol. 7, No. 10. – P. 1–8 (in Russian).

Melnikov B., Melnikova A. Extended basis finite automaton. Part II. The description of auxiliary languages and some properties // International Journal of Open Information Technologies. – 2020. – Vol. 8, No. 5. – P. 1–7 (in Russian).

Melnikov B., Melnikova A. Some properties of the basis finite automaton // The Korean Journal of Computational and Applied Mathematics (Journal of Computational and Applied Mathematics). – 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 Computational and Applied Mathematics). – 2002. – Vol. 9, No. 2. – P. 475–485.

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

Kameda T., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Transactions on Computers. – 1970. – Vol. C-19, No. 7. – P. 617–627.

Polák L. Minimalizations of NFA using the universal automaton // International Journal of Foundation of Computer Science. – 2005. – Vol. 16, No. 5. – P. 999–1010.

Lombardy S., Sakarovitch J. The universal automaton // Logic and Automata. Amsterdam University Press. – 2008. – P. 457–504.

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

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

Dolgov V., Melnikov B. On the automatic construction algorithms of Waterloo-like finite automata based on complete automata // Heuristic algorithms and distributed computing. – 2014. – Vol. 1. No. 4. – P. 24–45 (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