On the complexity of intersection and conjugacy problems in free groups

DOI10.1016/0304-3975(84)90046-XzbMath0555.20016OpenAlexW2020680034MaRDI QIDQ760501

Jürgen Avenhaus, Klaus Madlener

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90046-x

zbMATH Keywords

algorithmsdecision problemsfree groupsconjugacy problemHowson propertyset of generatorslog-space reducibilitypolynomially time complete

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items (5)

Thue systems as rewriting systems ⋮ On the parallel complexity of linear groups ⋮ Parallel algorithms for solvable permutation groups ⋮ FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY ⋮ \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata

Cites Work

• The Nielsen reduction and P-complete problems in free groups
• On finitely generated subgroups of free groups
• Conjugacy of subgroups of a free group
• Word Problems Solvable in Logspace
• On the Intersection of Finitely Generated Free Groups
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of intersection and conjugacy problems in free groups