Variations on the Post Correspondence Problem for free groups

Laura Ciobanu*, Alan David Logan

*Corresponding author for this work

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

Abstract

The Post Correspondence Problem is a classical decision problem about equalisers of free monoid homomorphisms. We prove connections between several variations of this classical problem, but in the setting of free groups and free group homomorphisms. Among other results, and working under certain injectivity assumptions, we prove that computing the rank of the equaliser of a pair of free group homomorphisms can be applied to computing a basis of this equaliser, and also to solve the “generalised” Post Correspondence Problem for free groups.

Original languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings
EditorsNelma Moreira, Rogério Reis
PublisherSpringer Science and Business Media
Pages90-102
Number of pages13
ISBN (Electronic)9783030815080
ISBN (Print)9783030815073
DOIs
Publication statusPublished - 6 Aug 2021
Event25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12811 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Conference on Developments in Language Theory, DLT 2021
CityVirtual, Online
Period16/08/2120/08/21

Keywords

  • Post Correspondence Problem
  • Free group
  • Rational constraint

Fingerprint

Dive into the research topics of 'Variations on the Post Correspondence Problem for free groups'. Together they form a unique fingerprint.

Cite this