Seminar series
Tue, 28 Nov 2023
Laura Ciobanu

The Post Correspondence Problem (PCP) is a classical problem in computer science that can be stated as: is it decidable whether given two morphisms g and h between two free semigroups $A$ and $B$, there is any nontrivial $x$ in $A$ such that $g(x)=h(x)$? This question can be phrased in terms of equalisers, asked in the context of free groups, and expanded: if the `equaliser' of $g$ and $h$ is defined to be the subgroup consisting of all $x$ where $g(x)=h(x)$, it is natural to wonder not only whether the equaliser is trivial, but what its rank or basis might be. 

While the PCP for semigroups is famously insoluble and acts as a source of undecidability in many areas of computer science, the PCP for free groups is open, as are the related questions about rank, basis, or further generalisations. In this talk I will give an overview of what is known about the PCP in hyperbolic groups, nilpotent groups and beyond (joint work with Alex Levine and Alan Logan).

Please contact us with feedback and comments about this page. Last updated on 26 Nov 2023 09:34.