Post’s Correspondence Problem: From Computer Science to Algebra

Laura Ciobanu*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationReachability Problems. RP 2022
EditorsAnthony W. Lin, Georg Zetzsche, Igor Potapov
Number of pages9
ISBN (Electronic)9783031191350
ISBN (Print)9783031191343
Publication statusPublished - 12 Oct 2022
Event16th International Conference on Reachability Problems 2022 - Kaiserslautern, Germany
Duration: 17 Oct 202221 Oct 2022

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Conference on Reachability Problems 2022
Abbreviated titleRP 2022


  • Decidability
  • Free and hyperbolic groups
  • Free monoids
  • Nilpotent groups
  • Post Correspondence Problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Post’s Correspondence Problem: From Computer Science to Algebra'. Together they form a unique fingerprint.

Cite this