Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bicyclic Monoid: Not Concatenation?

  1. Feb 7, 2012 #1
    The Wikipedia article for the bicyclic monoid gives three constructions, one of which starts with a free semigroup. It describes the operation for the bicyclic monoid as concatenation, but the remain descriptions are definitely not concatenation (e.g. the product of the two generators is the empty string).

    My intuition is that they intended to say that it is "something similar to concatenation," but I just wanted to double-check and make sure I'm not missing something here.
  2. jcsd
  3. Feb 7, 2012 #2
    I think I understand this now. The provision that pq=1 means that the p's "at the end" of the left operand will collapse together with the q's "at the beginning" of the right operand. In fact we are concatenating, except that we have a more complex algebraic structure than in the free monoid, and the empty string is in the image space of the operation.

    Furthermore, this means that the usual recursively defined "length" function on free monoids is not well-defined on the bicyclic monoid.
  4. Feb 7, 2012 #3
    One more thing! I stumbled across the bicyclic monoid trying to understand syntactic monoids (since it is the syntactic monoid of the Dyck language).

    Based on what I can say about the relationship between B and the Dyck language, is it correct to say that:
    - The underlying set of a syntactic monoid is the alphabet of the language.
    - All strings in the language are equal to the empty string according to the monoid operation.

    This appears to be what is happening with the Dyck language: the p's and q's collapse together like pairs of parentheses, if and only if we have a well-formed Dyck string.

    However, I doubt that my generalization is correct, since it appears that a language not containing the empty string would not have a syntactic monoid.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook