POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS
From MaRDI portal
Publication:5297787
DOI10.1142/S0218196707003597zbMath1125.20018OpenAlexW2050463519MaRDI QIDQ5297787
Publication date: 13 July 2007
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218196707003597
computational complexityfree groupspolynomial time algorithmsefficient algorithmsendomorphism problem
Automorphisms of infinite groups (20E36) Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Random equations in free groups ⋮ On the asymptotics of visible elements and homogeneous equations in surface groups. ⋮ The monomorphism problem in free groups. ⋮ The equation w(x, y) = u over free groups: an algebraic approach
Cites Work