پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 11 |
| تعداد شماره‌ها | 212 |
| تعداد مقالات | 2,114 |
| تعداد مشاهده مقاله | 2,905,018 |
| تعداد دریافت فایل اصل مقاله | 2,120,967 |
On an interesting hypothesis of the theory of formal languages | ||
| Journal of Discrete Mathematics and Its Applications | ||
| دوره 9، شماره 2، شهریور 2024، صفحه 81-102 اصل مقاله (521.77 K) | ||
| نوع مقاله: Full Length Article | ||
| شناسه دیجیتال (DOI): 10.22061/jdma.2024.10789.1069 | ||
| نویسنده | ||
| Boris Melnikov* | ||
| Shenzhen MSU-BIT University | ||
| تاریخ دریافت: 29 فروردین 1403، تاریخ بازنگری: 06 اردیبهشت 1403، تاریخ پذیرش: 28 اردیبهشت 1403 | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| formal languages؛ iterations of languages؛ binary relations؛ morphisms؛ inverse morphisms | ||
| مراجع | ||
|
[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). | ||
|
آمار تعداد مشاهده مقاله: 71 تعداد دریافت فایل اصل مقاله: 92 |
||