|
SEMINARS |
"Algorithmic problems in algebra and logic" (S.I.Adian seminar)
|
|||
|
The Post Correspondence Problem and Equalisers for Immersions of Free Groups A. Logan Heriot-Watt University |
|||
Abstract: 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. Language: English |