Intersection of two monoids generated by two element codes

Štěpán Holub 📧 and Štěpán Starosta 📧

January 3, 2023

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.


This article provides a formalization of the classification of intersection \( \{x,y\}^* \cap \{u,v\}^*\) of two monoids generated by two element codes. Namely, the intersection has one of the following forms \( \{\beta,\gamma\}^* \quad \text{ or } \quad \left(\beta_0 + \beta(\gamma(1+\delta+ \cdots + \delta^t))^*\epsilon\right)^*.\) Note that it can be infinitely generated. The result is due to [Karhumäki, 84]. Our proof uses the terminology of morphisms which allows us to formulate the result in a shorter and more transparent way.


BSD License


August 17, 2023
Updated to version v1.10.1.


Related publications

  • Karhumäki, J. (n.d.). A note on intersections of free submonoids of a free monoid. Lecture Notes in Computer Science, 397–407.
  • Development repository

Session Two_Generated_Word_Monoids_Intersection