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)

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’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
PublisherSpringer
Pages28-36
Number of pages9
ISBN (Electronic)9783031191350
ISBN (Print)9783031191343
DOIs
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
Volume13608
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Reachability Problems 2022
Abbreviated titleRP 2022
Country/TerritoryGermany
CityKaiserslautern
Period17/10/2221/10/22

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this