The Post Correspondence Problem and equalisers for certain free group and monoid morphisms

Authors :: Ciobanu, Laura
Logan, Alan D.
Source :: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168, pp. 120:1-120:16
Publication Year :: 2020
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.<br />Comment: 16 pages, final version incorporating referees comments

Subjects :: Mathematics - Group Theory
Computer Science - Discrete Mathematics
Computer Science - Formal Languages and Automata Theory
Computer Science - Logic in Computer Science
20-06, 20E05, 20F10, 20M05, 68R15

Database :: arXiv
Journal :: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168, pp. 120:1-120:16
Publication Type :: Report
Accession number :: edsarx.2002.07574
Document Type :: Working Paper
Full Text :: https://doi.org/10.4230/LIPIcs.ICALP.2020.120

Full Text Access

Tools