The Nielsen reduction and P-complete problems in free groups

DOI10.1016/0304-3975(84)90024-0MaRDI QIDQ760500zbMATH OpenOpenAlexFDO

Authors 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

free groupscoset representativesgeneralized word problemlog-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)

Recommendations

• scientific article; zbMATH DE number 3874607
• scientific article; zbMATH DE number 8769
• Nielsen reduction in free groups with operators
• A reduction of the decidability problem of the theory of a free group
• On reduction ofp-groups
• A reduction theorem for nonsolvable finite groups
• On Pierce problem for reduced p-groups
• On the Nielsen method in free products with amalgamated subgroups
• scientific article; zbMATH DE number 1237912
• PSPACE-completeness of certain algorithmic problems on the subgroups of free groups

Cites work

• scientific article; zbMATH DE number 3874607 (Why is no real title available?)
• scientific article; zbMATH DE number 3811849 (Why is no real title available?)
• scientific article; zbMATH DE number 3563392 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 1008505 (Why is no real title available?)
• Algorithmische Probleme bei Einrelatorgruppen und ihre Komplexität
• 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

Cited in

(24)

• Thue systems as rewriting systems
• Computing with subgroups of the modular group.
• Complete problems for symmetric logspace involving free groups
• On the parallel complexity of linear groups
• Non-commutative lattice problems
• Nielsen reduction in free groups with operators
• The fully compressed subgroup membership problem
• Polynomial-time word problems.
• Implementation of some algorithms of combinatorial group theory in the algebraic programming system APS-1
• Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
• scientific article; zbMATH DE number 3874607 (Why is no real title available?)
• Complexity of word problems for HNN-extensions
• Complexity of word problems for HNN-extensions
• \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
• Compression techniques in group theory
• On the complexity of intersection and conjugacy problems in free groups
• The complexity of bidirected reachability in valence systems
• scientific article; zbMATH DE number 4093751 (Why is no real title available?)
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• On Pierce problem for reduced p-groups
• Parallel algorithms for solvable permutation groups
• scientific article; zbMATH DE number 988810 (Why is no real title available?)
• FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY
• Formalizing free groups in Isabelle/HOL: the Nielsen-Schreier theorem and the conjugacy problem

This page was built for publication: The Nielsen reduction and P-complete problems in free groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760500)