School of Mathematics, Statistics and Physics

Seminar Item

Pure Maths (Algebra and Geometry) - Alan Logan (Heriot-Watt)

The Post Correspondence Problem and Equalisers for Immersions of Free Groups

Date/Time: Monday 14 December, 1.30pm - Algebra and Geometry Seminar

Venue: Zoom


The Post Correspondence Problem (PCP) is a classical decision problem about equalisers of free monoid morphisms. It is undecidable in general, but decidable in special cases (e.g. for binary alphabets), and is extremely well-studied in computer science. It even has a Wikipedia page! This talk is about equalisers of free *group* homomorphisms, and the statement of the PCP generalises to this setting. We prove positive results for immersions of free groups, in the sense of Kapovich: the PCP is decidable here, and we answer two questions of Stallings for these maps.