Об одной гипотезе теории формальных языков. Часть I

Борис Феликсович Мельников

Аннотация


Основной предмет статьи — рассмотрение задач, возникающих при исследовании необходимых условий равенства бесконечных итераций конечных языков. В предыдущих публикациях автором рассматривались примеры применения соответствующего этому равенству специального бинарного отношения эквивалентности на множестве конечных языков, причем рассматривались как примеры, описывающие необходимые условия его выполнения, так и примеры его использования. К одному из таких необходимых условий применены два варианта сведeния рассматриваемой задачи: к конечным автоматам и к бесконечным итерационным деревьям. Также в статье приведены несколько вариантов важной гипотезы, формулируемой для множества конечных языков; ее исследование дает и иные варианты сведeния рассматриваемой задачи к специальным задачам для недетерминированных конечных автоматов. При этом в случае выполнения сформулированной гипотезы некоторые из таких задач решаются за полиномиальное время, а некоторые не решаются; при продолжении работ по данной тематике последний факт может дать возможность переформулировки проблемы P = NP в виде специальной задачи теории формальных языков.

Ключевые слова


формальные языки; итерации языков; бинарные отношения; морфизмы; инверсные морфизмы; алгоритмы; полиномиальные алгоритмы

Полный текст:

PDF

Литература


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




DOI: http://dx.doi.org/10.14529/cmse230305