Variations on the Post Correspondence Problem for Free Groups

Laura Ciobanu, Alan D. Logan

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. DLT 2021
EditorsNelma Moreira, Rogério Reis
PublisherSpringer
Pages90-102
Number of pages13
ISBN (Electronic)9783030815080
ISBN (Print)9783030815073
DOIs
Publication statusPublished - 2021
Event25th International Conference on Developments in Language Theory 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Publication series

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

Conference

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

Keywords

  • Free group
  • Post Correspondence Problem
  • Rational constraint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this