On some equations in free partially commutative monoids (Q1084189)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On some equations in free partially commutative monoids |
scientific article |
Statements
On some equations in free partially commutative monoids (English)
0 references
1986
0 references
Let A be a finite alphabet and \(\theta\) be a symmetric relation on A. Then the monoid M(A,\(\theta)\) is called a free partially commutative monoid if it is a quotient monoid of \(A^*\) by the smallest congruence \(\sim\) such that xy\(\sim yx\) for every x,y\(\in \theta\). Let \(e,e'\in \{u,v\}^*\). For every free partially commutative monoid M(A,\(\theta)\) all pairs m,n\(\in M(A,\theta)\) are described such that \(e=e'\) holds in M(A,\(\theta)\) when m and n are substituted for u and v, respectively. We say that m and n are transposed if there exist x, y with \(m=xy\), \(n=yx\), m and n are conjugate if there exists x with \(mx=xn\). In free partially commutative monoids the transitive closure of the transposition relation is the conjugacy relation, and moreover, both relations coincide iff M(A,\(\theta)\) is a product of free monoids. Finally, for every free partially commutative monoid M(A,\(\theta)\) and for every m,n\(\in M(A,\theta)\) the set \(\{\) \(x\in M(A,\theta)\); \(mx=xn\}\) is recognizable in M(A,\(\theta)\).
0 references
free partially commutative monoids
0 references
transposition relation
0 references
conjugacy relation
0 references
product of free monoids
0 references
recognizable
0 references