Post's Correspondence Problem for hyperbolic and virtually nilpotent groups

DOI10.1112/BLMS.12921MaRDI QIDQ6188133zbMATH OpenOpenAlexFDO

Authors Laura Ciobanu, Alex Levine, Alan D. Logan

Publication date 1 February 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

conjugacy problemdecidabilityhyperbolic groupPost's correspondence problemvirtually nilpotent group

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Generalizations of solvable and nilpotent groups (20F19) Hyperbolic groups and nonpositively curved groups (20F67) Free semigroups, generators and relations, word problems (20M05) Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: Post's Correspondence Problem (the PCP) is a classical decision problem in theoretical computer science that asks whether for pairs of free monoid morphisms $g,hcolonSigm{a}^{\ast }oDelt{a}^{\ast }$ there exists any non-trivial $xinSigm{a}^{\ast }$ such that $g(x)=h(x)$. Post's Correspondence Problem for a group $Gamma$ takes pairs of group homomorphisms $g,hcolonF(Sigma)oGamma$ instead, and similarly asks whether there exists an $x$ such that $g(x)=h(x)$ holds for non-elementary reasons. The restrictions imposed on $x$ in order to get non-elementary solutions lead to several interpretations of the problem; we consider the natural restriction asking that $xotinker(g)capker(h)$ and prove that the resulting interpretation of the PCP is undecidable for arbitrary hyperbolic $Gamma$, but decidable when $Gamma$ is virtually nilpotent. We also study this problem for group constructions such as subgroups, direct products and finite extensions. This problem is equivalent to an interpretation due to Myasnikov, Nikolev and Ushakov when one map is injective.

Recommendations

• The Post correspondence problem in groups.
• On some variants of Post's correspondence problem
• A simple undecidable problem for free groups
• Remarks on generalized Post Correspondence Problem
• The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups

Cites work

• A variant of a recursively unsolvable problem
• An algorithm for finding a basis of the fixed point subgroup of an automorphism of a free group.
• Cohomology theory of aspherical groups and of small cancellation groups
• Compressed decision problems in hyperbolic groups
• Conjugacy in Nilpotent Groups
• Diophantine questions in the class of finitely generated nilpotent groups
• Equations in nilpotent groups.
• Equations with one unknown in nilpotent groups
• Finding all solutions of equations in free groups and monoids with involution
• Finding intersections and normalizers in finitely generated nilpotent groups
• Fixed points and stable images of endomorphisms for the free group of rank two
• Foliations for solving equations in groups: free, virtually free, and hyperbolic groups.
• Groups, languages and automata
• scientific article; zbMATH DE number 3976343 (Why is no real title available?)
• scientific article; zbMATH DE number 4004453 (Why is no real title available?)
• scientific article; zbMATH DE number 1284162 (Why is no real title available?)
• scientific article; zbMATH DE number 2133330 (Why is no real title available?)
• scientific article; zbMATH DE number 3305031 (Why is no real title available?)
• scientific article; zbMATH DE number 3396154 (Why is no real title available?)
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups
• Knapsack in hyperbolic groups
• Matrix representations for torsion-free nilpotent groups by Deep Thought.
• Noneffective regularity of equality languages and bounded delay morphisms
• Polynomials describing the multiplication in finitely generated torsion-free nilpotent groups
• Random nilpotent groups, polycyclic presentations, and Diophantine problems
• Rips construction and Kazhdan property (T).
• Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE
• Subgroups of small Cancellation Groups
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• The algorithmic theory of polycyclic-by-finite groups
• The complexity of solution sets to equations in hyperbolic groups
• The conjugacy problem in subgroups of right-angled Artin groups
• The equivalence of some residual properties of word-hyperbolic groups
• The Post correspondence problem in groups.
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
• Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings
• Variations on the post correspondence problem for free groups

This page was built for publication: Post's Correspondence Problem for hyperbolic and virtually nilpotent groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6188133)