Post's correspondence problem: from computer science to algebra

DOI10.1007/978-3-031-19135-0_2OpenAlexW4312335652MaRDI QIDQ6173100

Laura Ciobanu

Publication date: 21 July 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-19135-0_2

zbMATH Keywords

nilpotent groupsdecidabilitypost correspondence problemfree monoidsfree and hyperbolic groups

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Explicit bounds for fixed subgroups of endomorphisms of free products

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diophantine questions in the class of finitely generated nilpotent groups
• 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
• Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings
• Finding intersections and normalizers in finitely generated nilpotent groups
• Generic-case complexity, decision problems in group theory, and random walks.
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Evaluation of circuits over nilpotent and polycyclic groups
• Algorithmic constructions of relative train track maps and CTs
• The complexity of solution sets to equations in hyperbolic groups
• Rips construction and Kazhdan property (T).
• 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
• 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
• Fixed Subgroups of Homomorphisms of Free Groups
• Subgroups of small Cancellation Groups
• Conjugacy in Nilpotent Groups
• A variant of a recursively unsolvable problem
• Marked PCP is decidable