On a class of generalised solutions to the kinetic Hookean dumbbell model for incompressible dilute polymeric fluids: existence and macroscopic closure
Dębiec, T Süli, E (29 Jun 2023)
Fast and Slow Optimal Trading with Exogenous Information
Cont, R Micheli, A Neuman, E
Cross-Relation Characterization of Knowledge Networks
Tokuda, E Lambiotte, R Costa, L (27 Jun 2023)
Raphtory: The temporal graph engine for Rust and Python
Steer, B Arnold, N Ba, C Lambiotte, R Yousaf, H Jeub, L Murariu, F Kapoor, S Rico, P Chan, R Chan, L Alford, J Clegg, R Cuadrado, F Barnes, M Zhong, P Biyong, J Alnaimi, A (28 Jun 2023)
Aspects of Categorical Symmetries from Branes: SymTFTs and Generalized Charges
Apruzzi, F Bonetti, F Gould, D Schafer-Nameki, S (28 Jun 2023)
Symmetries of many-body systems imply distance-dependent potentials
Utterson, J Erban, R Physical Review E volume 108 (21 Jul 2023)
Mean-field Analysis of Generalization Errors
Aminian, G Cohen, S Szpruch, Ł (20 Jun 2023)
Data for paper "The effect of pore-scale contaminant distribution on the reactive decontamination of porous media"
Luckins, E Breward, C Griffiths, I Please, C (01 Jan 2023)
Fluid-flow effects in the reactive decontamination of porous materials driven by chemical swelling or contraction
Geng, Y Kamilova, A Luckins, E Journal of Engineering Mathematics volume 141 (05 Aug 2023)
Tue, 28 Nov 2023
15:00
L1

Fixed points of group homomorphisms and the Post Correspondence Problem

Laura Ciobanu
Abstract

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).

Subscribe to