TY - GEN

T1 - Post’s Correspondence Problem

T2 - 16th International Conference on Reachability Problems 2022

AU - Ciobanu, Laura

N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2022/10/12

Y1 - 2022/10/12

N2 - 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’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.

AB - 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’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.

KW - Decidability

KW - Free and hyperbolic groups

KW - Free monoids

KW - Nilpotent groups

KW - Post Correspondence Problem

UR - http://www.scopus.com/inward/record.url?scp=85141810625&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-19135-0_2

DO - 10.1007/978-3-031-19135-0_2

M3 - Conference contribution

AN - SCOPUS:85141810625

SN - 9783031191343

T3 - Lecture Notes in Computer Science

SP - 28

EP - 36

BT - Reachability Problems. RP 2022

A2 - Lin, Anthony W.

A2 - Zetzsche, Georg

A2 - Potapov, Igor

PB - Springer

Y2 - 17 October 2022 through 21 October 2022

ER -