Document Open Access Logo

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

Authors Laura Ciobanu , Alan D. Logan

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.120.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Laura Ciobanu
  • Heriot-Watt University, Edinburgh, Scotland, UK
Alan D. Logan
  • Heriot-Watt University, Edinburgh, Scotland, UK

Funding

Research supported by EPSRC grant EP/R035814/1.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ICALP.2020.120

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Complexity classes
  • Mathematics of computing → Combinatorics on words
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • Post Correspondence Problem
  • marked map
  • immersion
  • free group
  • free monoid

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Gilbert Baumslag, Alexei G. Myasnikov, and Vladimir Shpilrain. Open problems in combinatorial group theory. Second edition. In Combinatorial and geometric group theory (New York, 2000/Hoboken, NJ, 2001), volume 296 of Contemp. Math., pages 1-38. Amer. Math. Soc., Providence, RI, 2002. URL: https://doi.org/10.1090/conm/296/05067.
  2. George M. Bergman. Supports of derivations, free factorizations, and ranks of fixed subgroups in free groups. Trans. Amer. Math. Soc., 351(4):1531-1550, 1999. URL: https://doi.org/10.1090/S0002-9947-99-02087-5.
  3. Mladen Bestvina and Michael Handel. Train tracks and automorphisms of free groups. Ann. of Math. (2), 135(1):1-51, 1992. URL: https://doi.org/10.2307/2946562.
  4. Meera Blattner and Tom Head. Automata that recognize intersections of free submonoids. Information and Control, 35(3):173-176, 1977. Google Scholar
  5. Laura Ciobanu, Armando Martino, and Enric Ventura. The generic Hanna Neumann Conjecture and Post Correspondence Problem, 2008. URL: http://www-eupm.upc.es/~ventura/ventura/files/31t.pdf.
  6. Laura Ciobanu and Sasa Radomirovic. Restricted walks in regular trees. Electronic J. of Combinatorics, 13(R93), 2006. URL: https://doi.org/10.37236/1119.
  7. Warren Dicks and Enric Ventura. The group fixed by a family of injective endomorphisms of a free group, volume 195 of Contemporary Mathematics. American Mathematical Society, Providence, RI, 1996. URL: https://doi.org/10.1090/conm/195.
  8. Volker Diekert, Olga Kharlampovich, Markus Lohrey, and Alexei Myasnikov. Algorithmic problems in group theory. Dagstuhl seminar report 19131, 2019. URL: http://drops.dagstuhl.de/opus/volltexte/2019/11293/pdf/dagrep_v009_i003_p083_19131.pdf.
  9. A. Ehrenfeucht, J. Karhumäki, and G. Rozenberg. The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoret. Comput. Sci., 21(2):119-144, 1982. URL: https://doi.org/10.1016/0304-3975(89)90080-7.
  10. A. Ehrenfeucht and G. Rozenberg. Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci., 7(2):169-183, 1978. URL: https://doi.org/10.1016/0304-3975(78)90047-6.
  11. Vesa Halava, Mika Hirvensalo, and Ronald de Wolf. Marked PCP is decidable. Theoret. Comput. Sci., 255(1-2):193-204, 2001. URL: https://doi.org/10.1016/S0304-3975(99)00163-2.
  12. Tero Harju and Juhani Karhumäki. Morphisms. In Handbook of formal languages, Vol. 1, pages 439-510. Springer, Berlin, 1997. Google Scholar
  13. Štěpán Holub. Binary equality sets are generated by two words. J. Algebra, 259(1):1-42, 2003. URL: https://doi.org/10.1016/S0021-8693(02)00534-3.
  14. W. Imrich and E. C. Turner. Endomorphisms of free groups and their fixed points. Math. Proc. Cambridge Philos. Soc., 105(3):421-422, 1989. URL: https://doi.org/10.1017/S0305004100077781.
  15. Ilya Kapovich. Mapping tori of endomorphisms of free groups. Comm. Algebra, 28(6):2895-2917, 2000. URL: https://doi.org/10.1080/00927870008826999.
  16. Ilya Kapovich and Alexei Myasnikov. Stallings foldings and subgroups of free groups. J. Algebra, 248(2):608-668, 2002. URL: https://doi.org/10.1006/jabr.2001.9033.
  17. Juhani Karhumäki. A note on intersections of free submonoids of a free monoid. Semigroup Forum, 29(1-2):183-205, 1984. URL: https://doi.org/10.1007/BF02573324.
  18. Juhani Karhumäki and Aleksi Saarela. Noneffective regularity of equality languages and bounded delay morphisms. Discrete Math. Theor. Comput. Sci., 12(4):9-17, 2010. Google Scholar
  19. Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov. The Post correspondence problem in groups. J. Group Theory, 17(6):991-1008, 2014. URL: https://doi.org/10.1515/jgth-2014-0022.
  20. Turlough Neary. Undecidability in binary tag systems and the post correspondence problem for five pairs of words. In 32nd International Symposium on Theoretical Aspects of Computer Science, volume 30 of LIPIcs. Leibniz Int. Proc. Inform., pages 649-661. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015. Google Scholar
  21. Emil L. Post. A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc., 52:264-268, 1946. URL: https://doi.org/10.1090/S0002-9904-1946-08555-9.
  22. John R. Stallings. Graphical theory of automorphisms of free groups. In Combinatorial group theory and topology (Alta, Utah, 1984), volume 111 of Ann. of Math. Stud., pages 79-105. Princeton Univ. Press, Princeton, NJ, 1987. Google Scholar
  23. Bret Tilson. The intersection of free submonoids of a free monoid is free. Semigroup Forum, 4:345-350, 1972. URL: https://doi.org/10.1007/BF02570808.
  24. E. Ventura. Fixed subgroups in free groups: a survey. In Combinatorial and geometric group theory (New York, 2000/Hoboken, NJ, 2001), volume 296 of Contemp. Math., pages 231-255. Amer. Math. Soc., Providence, RI, 2002. URL: https://doi.org/10.1090/conm/296/05077.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact