@inproceedings{363e0e9f0a0c4bcc87347efdbaff2e23,
title = "Post{\textquoteright}s Correspondence Problem: From Computer Science to Algebra",
abstract = "In this short survey we describe recent advances on the Post Correspondence Problem in group theory that were inspired by results in computer science. These algebraic advances can, in return, provide a source of interesting problems in more applied, computational settings. Post{\textquoteright}s Correspondence Problem (PCP) is a classical decision problem in theoretical computer science that asks whether for a pair of free monoid morphisms g, h: Σ∗→ Δ∗ there is any non-trivial x∈ Σ∗ such that g(x) = h(x). One can similarly phrase a PCP for general groups, rather than free monoids, by asking whether pairs g, h of group homomorphisms agree on any inputs. This leads to interesting and unexpected (un)decidability results for PCP in groups.",
keywords = "Decidability, Free and hyperbolic groups, Free monoids, Nilpotent groups, Post Correspondence Problem",
author = "Laura Ciobanu",
note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 16th International Conference on Reachability Problems 2022, RP 2022 ; Conference date: 17-10-2022 Through 21-10-2022",
year = "2022",
month = oct,
day = "12",
doi = "10.1007/978-3-031-19135-0_2",
language = "English",
isbn = "9783031191343",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "28--36",
editor = "Lin, {Anthony W.} and Georg Zetzsche and Igor Potapov",
booktitle = "Reachability Problems. RP 2022",
address = "United States",
}