On the complexity of reduction algorithms in Novikov-Boone constructions

DOI10.1007/BF02219824MaRDI QIDQ2544778zbMATH OpenFDO

Authors B. A. Trakhtenbrot

Publication date 1970

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

Full work available at URL https://doi.org/10.1007/BF02219824

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cites work

• scientific article; zbMATH DE number 3301428 (Why is no real title available?)
• scientific article; zbMATH DE number 3322090 (Why is no real title available?)
• The word problem
• 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

Cited in

(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

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

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