Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Ciobanu, Laura; Logan, Alan D. https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-125271
URL:

;

The Post Correspondence Problem and Equalisers for Certain Free Group and Monoid Morphisms

pdf-format:


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.

BibTeX - Entry

@InProceedings{ciobanu_et_al:LIPIcs:2020:12527,
  author =	{Laura Ciobanu and Alan D. Logan},
  title =	{{The Post Correspondence Problem and Equalisers for Certain Free Group and Monoid Morphisms}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{120:1--120:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12527},
  URN =		{urn:nbn:de:0030-drops-125271},
  doi =		{10.4230/LIPIcs.ICALP.2020.120},
  annote =	{Keywords: Post Correspondence Problem, marked map, immersion, free group, free monoid}
}

Keywords: Post Correspondence Problem, marked map, immersion, free group, free monoid
Seminar: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue date: 2020
Date of publication: 29.06.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI