Post's Correspondence Problem for hyperbolic and virtually nilpotent groups

DOI10.1112/blms.12921arXiv2211.12158MaRDI QIDQ6188133

Laura Ciobanu, Alan D. Logan, Alex Levine

Publication date: 1 February 2024

Published in: Bulletin of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

decidabilityhyperbolic groupvirtually nilpotent groupconjugacy problemPost's correspondence problem

Mathematics Subject Classification ID

68R15: Combinatorics on words

68Q45: Formal languages and automata

20F19: Generalizations of solvable and nilpotent groups

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

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

20F67: Hyperbolic groups and nonpositively curved groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diophantine questions in the class of finitely generated nilpotent groups
• Finding all solutions of equations in free groups and monoids with involution
• The Post correspondence problem in groups.
• Equations with one unknown in nilpotent groups
• Variations on the post correspondence problem for free groups
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• The algorithmic theory of polycyclic-by-finite groups
• Cohomology theory of aspherical groups and of small cancellation groups
• Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings
• Finding intersections and normalizers in finitely generated nilpotent groups
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Polynomials describing the multiplication in finitely generated torsion-free nilpotent groups
• The equivalence of some residual properties of word-hyperbolic groups
• The complexity of solution sets to equations in hyperbolic groups
• Rips construction and Kazhdan property (T).
• Matrix representations for torsion-free nilpotent groups by Deep Thought.
• Fixed points and stable images of endomorphisms for the free group of rank two
• An algorithm for finding a basis of the fixed point subgroup of an automorphism of a free group
• Equations in nilpotent groups
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• Groups, Languages and Automata
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Foliations for solving equations in groups: free, virtually free, and hyperbolic groups
• The conjugacy problem in subgroups of right-angled Artin groups
• Subgroups of small Cancellation Groups
• Conjugacy in Nilpotent Groups
• A variant of a recursively unsolvable problem
• Knapsack in hyperbolic groups