The post correspondence problem and equalisers for certain free group and monoid morphisms

Laura Ciobanu, Alan D. Logan

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

Abstract

A marked free monoid morphism is a morphism for which the image of each generator starts with a different letter, and immersions are the analogous maps in free groups. We show that the (simultaneous) PCP is decidable for immersions of free groups, and provide an algorithm to compute bases for the sets, called equalisers, on which the immersions take the same values. We also answer a question of Stallings about the rank of the equaliser. Analogous results are proven for marked morphisms of free monoids.

Original languageEnglish
Title of host publication47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
EditorsArtur Czumaj, Anuj Dawar, Emanuela Merelli
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959771382
DOIs
Publication statusPublished - 29 Jun 2020
Event47th International Colloquium on Automata, Languages, and Programming 2020 - Virtual, Online, Germany
Duration: 8 Jul 202011 Jul 2020

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume168
ISSN (Print)1868-8969

Conference

Conference47th International Colloquium on Automata, Languages, and Programming 2020
Abbreviated titleICALP 2020
CountryGermany
CityVirtual, Online
Period8/07/2011/07/20

Keywords

  • Free group
  • Free monoid
  • Immersion
  • Marked map
  • Post Correspondence Problem

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'The post correspondence problem and equalisers for certain free group and monoid morphisms'. Together they form a unique fingerprint.

  • Cite this

    Ciobanu, L., & Logan, A. D. (2020). The post correspondence problem and equalisers for certain free group and monoid morphisms. In A. Czumaj, A. Dawar, & E. Merelli (Eds.), 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) [120] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 168). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2020.120