The Post correspondence problem in groups.

DOI10.1515/jgth-2014-0022zbMath1315.20035arXiv1310.5246MaRDI QIDQ471848

J. Herrera, Sumit K. Garg

Publication date: 17 November 2014

Published in: Journal of Group Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.5246

zbMATH Keywords

computational complexity; endomorphisms; Artin groups; word problem; nilpotent groups; hyperbolic groups; NP-completeness; free groups; free monoids; twisted conjugacy problem; Post correspondence problem; equalizers

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

20M05: Free semigroups, generators and relations, word problems

20F18: Nilpotent groups

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

03D40: Word problems, etc. in computability and recursion theory

08A50: Word problems (aspects of algebraic structures)