Аннотация:
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.
