Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups

DOI10.1002/malq.19930390117zbMath0799.03049OpenAlexW2076095858WikidataQ126258842 ScholiaQ126258842MaRDI QIDQ4304125

Friedrich Otto, Klaus Madlener, Daniel E. Cohen

Publication date: 24 November 1994

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19930390117

zbMATH Keywords

complexityTuring machineshalting problemword problems for groupspseudo-natural algorithmmodular machines

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Related Items (7)

Taming the hydra: The word problem and extreme integer compression ⋮ FUNCTIONS ON GROUPS AND COMPUTATIONAL COMPLEXITY ⋮ Space functions and space complexity of the word problem in semigroups. ⋮ Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem ⋮ EFFICIENT ALGORITHMS FOR HIGHLY COMPRESSED DATA: THE WORD PROBLEM IN HIGMAN'S GROUP IS IN P ⋮ Space functions of groups ⋮ Asymptotic invariants, complexity of groups and related problems

Cites Work

• Unnamed Item
• Subrekursive Komplexität bei Gruppen. II: Der Einbettungssatz von Higman für entscheidbare Gruppen

This page was built for publication: Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups