On the complexity of reduction algorithms in Novikov-Boone constructions

DOI10.1007/BF02219824zbMath0213.02002MaRDI QIDQ2544778

B. A. Trakhtenbrot

Publication date: 1970

Published in: Algebra and Logic (Search for Journal in Brave)

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) 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 (3)

Unsolvable algorithmic problems for semigroups, groups and rings ⋮ Space functions and space complexity of the word problem in semigroups. ⋮ From Logic to Theoretical Computer Science – An Update

Cites Work

• Unnamed Item
• Unnamed Item
• Word problems and recursively enumerable degrees at unsolvability. A first paper on Thue systems
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
• The word problem

This page was built for publication: On the complexity of reduction algorithms in Novikov-Boone constructions