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 non-trivial x in A such that g(x)=h(x)? This question can be phrased in terms of equalizers, asked in the context of free groups, and expanded: if the ‘equalizer’ 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 equalizer 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 generalizations. However, in this talk we will show that there are links and surprising equivalences between these problems in free groups, and classes of maps for which we can give complete answers.
This is joint work with Alan Logan.
This video was produced by Newcastle University, Australia, as part of the Symmetries in Newcastle seminar series.
