1 Search Results for "Logan, Alan D."


Document
Track B: Automata, Logic, Semantics, and Theory of Programming
The Post Correspondence Problem and Equalisers for Certain Free Group and Monoid Morphisms

Authors: Laura Ciobanu and Alan D. Logan

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 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.

Cite as

Laura Ciobanu and Alan D. Logan. The Post Correspondence Problem and Equalisers for Certain Free Group and Monoid Morphisms. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 120:1-120:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ciobanu_et_al:LIPIcs.ICALP.2020.120,
  author =	{Ciobanu, Laura and Logan, Alan D.},
  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 =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.120},
  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}
}
  • Refine by Author
  • 1 Ciobanu, Laura
  • 1 Logan, Alan D.

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 Post Correspondence Problem
  • 1 free group
  • 1 free monoid
  • 1 immersion
  • 1 marked map

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail