On the complexity of the identity problem for finitely defined groups

DOI10.1007/BF02219819MaRDI QIDQ2544779zbMATHFDO

Authors Yanyan Li

Publication date 1970

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

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3302325 (Why is no real title available?)
• scientific article; zbMATH DE number 3317755 (Why is no real title available?)
• scientific article; zbMATH DE number 3083488 (Why is no real title available?)
• Finitely Presented Groups with Word Problems of Arbitrary Degrees of Insolubility
• Hierarchies of Computable groups and the word problem
• Subgroups of finitely presented groups
• The word problem
• The word problem
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups

Cited in

(3)

• An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
• Space functions and space complexity of the word problem in semigroups.
• Some algorithmic problems for relatively free groups

This page was built for publication: On the complexity of the identity problem for finitely defined groups

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