Geodesic
On a hypothesis of the theory of formal languages. Part I
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 12 (2023) no. 3, pp. 72-86

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: formal languages, iterations of languages, binary relations, morphisms, inverse morphisms, algorithms, polynomial algorithms. 
@article{VYURV_2023_12_3_a4,
     author = {B.F. Melnikov},
     title = {On a hypothesis of the theory of formal languages. {Part} {I}},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {72--86},
     publisher = {mathdoc},
     volume = {12},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2023_12_3_a4/}
}
TY  - JOUR
AU  - B.F. Melnikov
TI  - On a hypothesis of the theory of formal languages. Part I
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2023
SP  - 72
EP  - 86
VL  - 12
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VYURV_2023_12_3_a4/
LA  - ru
ID  - VYURV_2023_12_3_a4
ER  - 
%0 Journal Article
%A B.F. Melnikov
%T On a hypothesis of the theory of formal languages. Part I
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2023
%P 72-86
%V 12
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VYURV_2023_12_3_a4/
%G ru
%F VYURV_2023_12_3_a4
B.F. Melnikov. On a hypothesis of the theory of formal languages. Part I. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 12 (2023) no. 3, pp. 72-86. http://geodesic.mathdoc.fr/item/VYURV_2023_12_3_a4/