Identities in unitriangular and gossip monoids

Abstract: We establish a criterion for a semigroup identity to hold in the monoid of

n i m e s n

upper unitriangular matrices with entries in a commutative semiring

S

. This criterion is combinatorial modulo the arithmetic of the multiplicative identity element of

S

. In the case where

S

is idempotent, the generated variety is the variety

m a t h b f J_{n - 1}

, which by a result of Volkov is generated by any one of: the monoid of unitriangular Boolean matrices, the monoid

R_{n}

of all reflexive relations on an

n

element set, or the Catalan monoid

C_{n}

. We propose

S

-matrix analogues of these latter two monoids in the case where

S

is an idempotent semiring whose multiplicative identity element is the `top' element with respect to the natural partial order on

S

, and show that each generates

m a t h b f J_{n - 1}

. As a consequence we obtain a complete solution to the finite basis problem for lossy gossip monoids.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Identities in unitriangular and gossip monoids