On the complexity of the identity problem for finitely defined groups

DOI10.1007/BF02219819zbMath0213.02003MaRDI QIDQ2544779

Yanyan Li

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
• Subgroups of finitely presented groups
• Hierarchies of Computable groups and the word problem
• Finitely Presented Groups with Word Problems of Arbitrary Degrees of Insolubility
• The word problem
• The word problem