On the complexity of the identity problem for finitely defined groups

DOI10.1007/BF02219819zbMATH Open0213.02003MaRDI QIDQ2544779FDOQ2544779

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Subgroups of finitely presented groups
• The word problem
• The word problem
• Finitely Presented Groups with Word Problems of Arbitrary Degrees of Insolubility
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
• Hierarchies of Computable groups and the word problem

Cited In (3)

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

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)