Bicyclic Monoid: Not Concatenation?

  • Thread starter alexfloo
  • Start date
In summary, the Wikipedia article for the bicyclic monoid discusses three constructions, one of which involves a free semigroup. While the operation is described as concatenation, it is actually more complex and the product of the two generators can result in the empty string. The provision that pq=1 means that the p's and q's will collapse together, similar to concatenation. However, this also means that the usual "length" function on free monoids is not well-defined for the bicyclic monoid. It is also noted that the bicyclic monoid is the syntactic monoid of the Dyck language, where the p's and q's collapse together to form well-formed strings. This leads to the conclusion that
  • #1
alexfloo
192
0
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.
 
Physics news on Phys.org
  • #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.
 
  • #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.
 

1. What is a bicyclic monoid?

A bicyclic monoid is a mathematical structure that consists of two elements, one of which can be multiplied by itself, and the other can be multiplied by both itself and the first element. This structure is often used to model non-commutative operations, such as matrix multiplication.

2. How is a bicyclic monoid different from a regular monoid?

A regular monoid only has one element that can be multiplied by itself, while a bicyclic monoid has two. This allows for more complex and non-commutative operations to be modeled.

3. What is the significance of "not concatenation" in a bicyclic monoid?

In a bicyclic monoid, the operation between the two elements is not concatenation, meaning that the result of multiplying the two elements is not simply combining them in order. This allows for more diverse and complex operations to be defined within the structure.

4. How are bicyclic monoids used in real-world applications?

Bicyclic monoids have various applications in computer science and mathematics, such as in coding theory, cryptography, and algebraic structures. They can also be used to model non-commutative operations in physics and chemistry.

5. Can a bicyclic monoid have more than two elements?

Yes, a bicyclic monoid can have more than two elements, as long as the two elements that can be multiplied by themselves and each other are present. However, the structure will still be considered a bicyclic monoid as long as these key elements are present.

Similar threads

  • Linear and Abstract Algebra
Replies
3
Views
3K
  • Quantum Interpretations and Foundations
Replies
0
Views
1K
  • Programming and Computer Science
Replies
1
Views
3K
  • Linear and Abstract Algebra
Replies
6
Views
2K
  • High Energy, Nuclear, Particle Physics
Replies
6
Views
1K
  • General Engineering
Replies
7
Views
2K
  • Beyond the Standard Models
2
Replies
61
Views
5K
  • Beyond the Standard Models
Replies
1
Views
2K
  • Quantum Interpretations and Foundations
Replies
14
Views
2K
Back
Top