The monomorphism problem in free groups.

DOI10.1007/s00013-010-0118-0zbMath1198.20022arXiv0910.1899OpenAlexW2089269623MaRDI QIDQ974649

Abderezak Ould Houcine, Laura Ciobanu

Publication date: 4 June 2010

Published in: Archiv der Mathematik (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.1899

zbMATH Keywords

computational complexitydecision problemsfree groupspolynomial time algorithmsefficient algorithmsendomorphism problemcomplexity of algorithmsmonomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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

On endomorphisms of the direct product of two free groups ⋮ Algorithmic problems for free-Abelian times free groups.

Cites Work

• Unnamed Item
• Unnamed Item
• A tighter bound for the number of words of minimum length in an automorphic orbit.
• Automorphic orbits in free groups.
• Stallings foldings and subgroups of free groups
• Satisfaction of existential theories in finitely presented groups and some embedding theorems.
• On equivalent sets of elements in a free group
• A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
• ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
• POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS