Post’s Correspondence Problem: From Computer Science to Algebra

Laura Ciobanu

doi:10.1007/978-3-031-19135-0_2

Post’s Correspondence Problem: From Computer Science to Algebra

Laura Ciobanu^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Reachability Problems. RP 2022
Editors	Anthony W. Lin, Georg Zetzsche, Igor Potapov
Publisher	Springer
Pages	28-36
Number of pages	9
ISBN (Electronic)	9783031191350
ISBN (Print)	9783031191343
DOIs	https://doi.org/10.1007/978-3-031-19135-0_2
Publication status	Published - 12 Oct 2022
Event	16th International Conference on Reachability Problems 2022 - Kaiserslautern, Germany Duration: 17 Oct 2022 → 21 Oct 2022

Publication series

Name	Lecture Notes in Computer Science
Volume	13608
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference on Reachability Problems 2022
Abbreviated title	RP 2022
Country/Territory	Germany
City	Kaiserslautern
Period	17/10/22 → 21/10/22

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

@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",

}

TY - GEN

T1 - Post’s Correspondence Problem

T2 - 16th International Conference on Reachability Problems 2022

AU - Ciobanu, Laura

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 -