Representations and identities of Baxter monoids with involution

Abstract

Let $({\mathsf{baxt}}_n,{}^{♯})$ be the Baxter monoid of finite rank $n$ with Schützenberger's involution ${}^{♯}$. In this paper, it is shown that $({\mathsf{baxt}}_n,{}^{♯})$ admits a faithful representation by an involution monoid of upper triangular matrices over any semiring from a large class including the tropical semiring under the skew transposition. Then a transparent combinatorial characterization of the word identities satisfied by $({\mathsf{baxt}}_n,{}^{♯})$ is given. Further, it is proved that $({\mathsf{baxt}}_n,{}^{♯})$ is finitely based if and only if $n\ne 3$, and shown that the identity checking problem for $({\mathsf{baxt}}_n,{}^{♯})$ can be done in polynomial time.

arXiv admin note: substantial text overlap with arXiv:2301.12449