08/07/2020

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

Laura Ciobanu and Alan Logan

Keywords: Post Correspondence Problem, marked map, immersion, free group, free monoid

Abstract Paper Similar Papers

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.

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at ICALP 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 26:31 
 0
 0
 0
 0
 25:05 
 0
 0
 0
 0
 15:02 
 0
 0
 0
 0
 13:04 
 0
 0
 0
 0
 19:19 
 0
 0
 0
 0
 12:55 
 0
 0
 0
 0
 25:11 
 0
 0
 0
 0
 25:29 
 0
 0
 0
 0
 16:22 
 0
 0
 0
 0
 28:04 
 0
 0
 0
 0
 20:44 
 0
 0
 0
 0
 12:13 
 0
 0
 0
 0
 24:54 
 0
 0
 0
 0
 25:22 
 0
 0
 0
 0
 5:18 
 0
 0
 0
 0
 22:12 
 0
 0
 0
 0
 8:03 
 0
 0
 0
 0
 23:59 
 0
 0
 0
 0
 13:34 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 11:57 
 0
 0
 0
 0
 15:07 
 0
 0
 0
 0
 24:54 
 0
 0
 0
 0
 10:26 
 0
 0
 0
 0
 14:13 
 0
 0
 0
 0
 2:58 
 0
 0
 0
 0
 10:59 
 0
 0
 0
 0
 25:55 
 0
 0
 0
 0
 22:46 
 0
 0
 0
 0
 24:21 
 0
 0
 0
 0
 20:17 
 0
 0
 0
 0
 24:23 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 13:39 
 0
 0
 0
 0
 4:56 
 0
 0
 0
 0
 7:35 
 0
 0
 0
 0
 9:35 
 0
 0
 0
 0
 26:54 
 0
 0
 0
 0
 16:31 
 0
 0
 0
 0
 23:05