The Finite Basis Problem And Computational Complexity For Some Classes Of Semigroups

Let UT2(IF)be the monoid of all 2 x 2 upper triangular matrices with Os and/or 1s on the main diagonal over a field F,UTn(T)be the monoid of all n x n upper triangular tropical matrices over the tropical semiring T=R?{-?} and UT2±(IF)be the monoid of all 2 x 2 upper triangular matrices with Os and/or±1s on the main diagonal over a field IF.In this paper,we give a sufficient condition under which an involution semigroup is nonfinitely based.As an application,it is shown that UT2(IF)as involution semigroups under the adjoint transposition are nonfinitely based for any field IF.we apply a sufficient condition under which an involution semigroup admits no finite identity basis to show that UT2(T)as an involution semigroup under the skew transposition is nonfinitely based,and prove that the computational complexity of checking identities problem and polynomial not zero problem in(UT2(T),D)are all polynomial-time.we prove that UT2+(F2)has the same identity basis with its finitely based subsemigroup UT2(IF2),which implies that the monoid UT2±(IF2)and UT2(IF2)generate the same varieties.