Complete problems for symmetric logspace involving free groups

DOI10.1016/0020-0190(91)90121-WzbMath0743.68064MaRDI QIDQ1183484

Iain A. Stewart

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

free groupsfinite model theorycomplete problemsGeneralized Word Problemsymmetric logspace

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On completeness for NP via projection translations ⋮ Methods for proving completeness via logical reductions ⋮ Context-sensitive transitive closure operators

Cites Work

• The Nielsen reduction and P-complete problems in free groups
• Symmetric space-bounded computation
• Symmetric Complementation
• Languages that Capture Complexity Classes
• Word Problems Solvable in Logspace
• Unnamed Item
• Unnamed Item
• Unnamed Item