The Nielsen reduction and P-complete problems in free groups

DOI10.1016/0304-3975(84)90024-0zbMath0555.20015OpenAlexW2002522693MaRDI QIDQ760500

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)90024-0

zbMATH Keywords

generalized word problemfree groupscoset representativeslog-space reducibilityNielsen reductionpolynomially 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

Thue systems as rewriting systems, On the parallel complexity of linear groups, Parallel algorithms for solvable permutation groups, FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY, COMPUTING WITH SUBGROUPS OF THE MODULAR GROUP, The fully compressed subgroup membership problem, Complete problems for symmetric logspace involving free groups, Complexity of word problems for HNN-extensions, Complexity of word problems for HNN-extensions, On the complexity of intersection and conjugacy problems in free groups, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata, Compression techniques in group theory

Cites Work

• Complete problems for deterministic polynomial time
• Subrekursive Komplexität bei Gruppen. II: Der Einbettungssatz von Higman für entscheidbare Gruppen
• Word Problems Solvable in Logspace
• Algorithmische Probleme bei Einrelatorgruppen und ihre Komplexität
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item