No Access

POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS

LAURA CIOBANU

Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

https://doi.org/10.1142/S0218196707003597Cited by:3 (Source: Crossref)

Abstract

We say the endomorphism problem is solvable for an element W in a free group F if it can be decided effectively whether, given U in F, there is an endomorphism ϕ of F sending W to U. This work analyzes an approach due to Edmunds and improved by Sims. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when W is a two-generator word. We show that when W is a two-generator word this algorithm solves the problem in time polynomial in the length of U.

This result gives a polynomial-time algorithm for solving, in free groups, two-variable equations in which all the variables occur on one side of the equality and all the constants on the other side.

Keywords:

AMSC: 20E05, 68Q17

References

C. C. Edmunds, Commun. Algebra 3, 1 (1975). Crossref, Web of Science, Google Scholar
C. C. Edmunds, Proc. London Math. Soc. 38, 153 (1979). Web of Science, Google Scholar
C. C. Sims, Ohio State Univ. Math. Res. Inst. Publ. 8, 349 (2001). Google Scholar
L. Ciobanu, On the complexity of the endomorphism problem in free groups, PhD thesis, Rutgers University (2005) . Google Scholar
L. P. Comerford and C. C. Edmunds, Symp. in Group Theory, Singapore (1987) (de Gruyter, Berlin, 1989) pp. 347–355. Google Scholar
C. C. Edmunds, Proc. Amer. Math. Soc. 76(1), 23 (1979). Crossref, Web of Science, Google Scholar
G. S. Makanin, Izv. Akad. Nauk SSSR Ser. Mat. 46, 1199 (1982). Google Scholar
R. I. Grigorchuk and P. F. Kurchanov, On quadratic equations in free groups, Proc. Int. Conf. on Algebra131, Contemporary Mathematics (American Mathematical Society, 1992) pp. 159–171. Google Scholar
C. Gutiérrez, Satisfiability of equations in free groups is in PSPACE, Proc. Thirty-Second Ann. ACM Symp. on Theory of Computing (ACM, New York, 2000) pp. 21–27. Google Scholar
B. Khan, Computational and Experimental Group Theory 349 (American Mathematical Society, 2004) pp. 115–196. Crossref, Google Scholar
A. Koscielski and L. Pacholski, Theor. Comput. Sci. 191(1–2), 145 (1998). Crossref, Web of Science, Google Scholar
R. C. Lyndon, Michigan Math. J. 6, 155 (1959). Google Scholar
A. I. Mal'cev, Algebra i Logika Sem. 1(5), 45 (1962). Google Scholar
A. G. Myasnikov and V. Shpilrain, J. Algebra 269(1), 18 (2003). Crossref, Web of Science, Google Scholar
W. Plandowski, J. ACM 51(3), 483 (2004). Crossref, Web of Science, Google Scholar
A. A. Razborov, Math USSR — Izv. 25(1), 115 (1985). Crossref, Google Scholar
V. A. Roman'kov, Algebra i Logika 16, 457 (1977). Google Scholar
P. Schupp, Quadratic equations in groups, cancellation diagrams on compact surfaces, and automorphisms of surface groups, Word Problems, II, Conference on Decision Problems in Algebra, Studies in Logic and the Foundations of Mathematics 95 (North-Holland, Amsterdam, 1980) pp. 347–371. Google Scholar
P. E. Schupp, Proc. Amer. Math. Soc. 23, 421 (1969). Crossref, Web of Science, Google Scholar
M. J. Wicks, J. London Math. Soc. 37, 433 (1962). Google Scholar