@inproceedings{ef80c15bc8c5437381cd3a0fda7c1d93,
title = "The post correspondence problem and equalisers for certain free group and monoid morphisms",
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.",
keywords = "Free group, Free monoid, Immersion, Marked map, Post Correspondence Problem",
author = "Laura Ciobanu and Logan, {Alan D.}",
note = "Funding Information: Research supported by EPSRC grant EP/R035814/1. Publisher Copyright: {\textcopyright} Laura Ciobanu and Alan D. Logan; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).; 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 ; Conference date: 08-07-2020 Through 11-07-2020",
year = "2020",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.ICALP.2020.120",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Artur Czumaj and Anuj Dawar and Emanuela Merelli",
booktitle = "47th International Colloquium on Automata, Languages, and Programming, ICALP 2020",
}