Geodesic
NP-трудность проблемы разрешимости для уравнений с простой правой частью в свободной группе
Čebyševskij sbornik, Tome 13 (2012) no. 1, pp. 46-53.

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

@article{CHEB_2012_13_1_a3,
     author = {V. G. Durnev and O. V. Zetkina},
     title = {NP-{\cyrt}{\cyrr}{\cyru}{\cyrd}{\cyrn}{\cyro}{\cyrs}{\cyrt}{\cyrsftsn} {\cyrp}{\cyrr}{\cyro}{\cyrb}{\cyrl}{\cyre}{\cyrm}{\cyrery} {\cyrr}{\cyra}{\cyrz}{\cyrr}{\cyre}{\cyrsh}{\cyri}{\cyrm}{\cyro}{\cyrs}{\cyrt}{\cyri} {\cyrd}{\cyrl}{\cyrya} {\cyru}{\cyrr}{\cyra}{\cyrv}{\cyrn}{\cyre}{\cyrn}{\cyri}{\cyrishrt} {\cyrs} {\cyrp}{\cyrr}{\cyro}{\cyrs}{\cyrt}{\cyro}{\cyrishrt} {\cyrp}{\cyrr}{\cyra}{\cyrv}{\cyro}{\cyrishrt} {\cyrch}{\cyra}{\cyrs}{\cyrt}{\cyrsftsn}{\cyryu} {\cyrv} {\cyrs}{\cyrv}{\cyro}{\cyrb}{\cyro}{\cyrd}{\cyrn}{\cyro}{\cyrishrt} {\cyrg}{\cyrr}{\cyru}{\cyrp}{\cyrp}{\cyre}},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {46--53},
     publisher = {mathdoc},
     volume = {13},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2012_13_1_a3/}
}
TY  - JOUR
AU  - V. G. Durnev
AU  - O. V. Zetkina
TI  - NP-трудность проблемы разрешимости для уравнений с простой правой частью в свободной группе
JO  - Čebyševskij sbornik
PY  - 2012
SP  - 46
EP  - 53
VL  - 13
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2012_13_1_a3/
LA  - ru
ID  - CHEB_2012_13_1_a3
ER  - 
%0 Journal Article
%A V. G. Durnev
%A O. V. Zetkina
%T NP-трудность проблемы разрешимости для уравнений с простой правой частью в свободной группе
%J Čebyševskij sbornik
%D 2012
%P 46-53
%V 13
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2012_13_1_a3/
%G ru
%F CHEB_2012_13_1_a3
V. G. Durnev; O. V. Zetkina. NP-трудность проблемы разрешимости для уравнений с простой правой частью в свободной группе. Čebyševskij sbornik, Tome 13 (2012) no. 1, pp. 46-53. http://geodesic.mathdoc.fr/item/CHEB_2012_13_1_a3/

[1] Tarski A., Mostowski A., Robinson R. M., Undecidable theories, N. Y., 1953 | MR | Zbl

[2] Lyndon R. C., “Equations in free groups”, Trans. Amer. Math. Soc., 96 (1960), 445–457 | DOI | MR | Zbl

[3] Lorents A. A., “O predstavlenii mnozhestv reshenii sistem uravnenii s odnim neizvestnym v svobodnykh gruppakh”, Doklady AN SSSR, 178:2 (1968), 290–292 | Zbl

[4] “One-variable equations in free groups”, Proc. Amer. Math. Soc., 19 (1968), 912–918 | DOI | MR | Zbl

[5] Khmelevskii Yu. I. Sistemy uravnenii v svobodnoi gruppe, I, Izvestiya AN SSSR. Seriya matematika, 35:6 (1971), 1237–1268 ; “II”, 36:1 (1972), 110–179

[6] Makanin G. S., “Uravneniya v svobodnoi gruppe”, Izvestiya AN SSSR. Seriya matematicheskaya, 46:6 (1982), 1199–1273 | MR | Zbl

[7] Razborov A. A., “O sistemakh uravnenii v svobodnoi gruppe”, Izvestiya AN SSSR. Seriya matematicheskaya, 48:4 (1984), 779–832 | MR

[8] Diekert V., Makanin's Algorithm for Solving Word Equations with Regular Constraints. Preliminary version of the chapter in M. Lothaire. Algebraic Combinatorics on Words., Report No 1998/02, Fakultat Informatik. Universitat Stuttgart, 1998

[9] Maltsev A. I., “Ob uravnenii $zxyx^{-1}y^{-1}z^{-1}=aba^{-1}b^{-1}$ v svobodnoi gruppe”, Algebra i logika, 1:5 (1962), 45–50 | MR

[10] Schupp P. E., “On the substitution problem for free groups”, Proc. Amer. Math. Soc., 23 (1969), 421 – 423 | DOI | MR | Zbl

[11] Edmunds C. C., “On the endomorphisms problem for free group”, Com. Algebra, 3 (1975), 7–20 | DOI | MR

[12] Durnev V. G., “O probleme razreshimosti dlya uravnenii s odnim koeffitsientom”, Matem. zametki, 59:6 (1996), 832–845 | DOI | MR | Zbl

[13] Durnev V. G., “Ob uravneniyakh na svobodnykh polugruppakh i gruppakh”, Matem. zametki, 16:5 (1974), 717–724 | MR

[14] Vdovina A. A., “Proizvedenie kommutatorov i kvadratov v svobodnoi gruppe”, Tretya mezhdunarodnaya konferentsiya po algebre, Sbornik tezisov, Izd-vo. KrGU, Krasnoyarsk, 1993, 66–67

[15] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR