The Nielsen reduction and P-complete problems in free groups
DOI10.1016/0304-3975(84)90024-0zbMATH Open0555.20015OpenAlexW2002522693MaRDI QIDQ760500FDOQ760500
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
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
free groupscoset representativesgeneralized word problemlog-space reducibilityNielsen reductionpolynomially time complete
Free nonabelian groups (20E05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Cites Work
- Word Problems Solvable in Logspace
- Title not available (Why is that?)
- Complete problems for deterministic polynomial time
- Title not available (Why is that?)
- Title not available (Why is that?)
- Subrekursive Komplexität bei Gruppen. II: Der Einbettungssatz von Higman für entscheidbare Gruppen
- Title not available (Why is that?)
- Algorithmische Probleme bei Einrelatorgruppen und ihre Komplexität
- Title not available (Why is that?)
Cited In (24)
- Computing with subgroups of the modular group.
- Thue systems as rewriting systems
- 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})\)
- Complexity of word problems for HNN-extensions
- Complexity of word problems for HNN-extensions
- Title not available (Why is that?)
- \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
- Title not available (Why is that?)
- The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
- On Pierce problem for reduced \(p\)-groups
- Parallel algorithms for solvable permutation groups
- Title not available (Why is that?)
- 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)
