Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields

DOI10.1007/s00233-005-0510-4zbMath1089.68046OpenAlexW2055685510MaRDI QIDQ2491185

Steve Seif, Csaba Szabó

Publication date: 26 May 2006

Published in: Semigroup Forum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00233-005-0510-4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05)

Related Items (16)

Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$ ⋮ Complexity of the identity checking problem for finite semigroups. ⋮ Complexity issues of checking identities in finite monoids ⋮ A survey on varieties generated by small semigroups and a companion website ⋮ Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\). ⋮ Identities of the Kauffman monoid K3 ⋮ Identity checking problem for transformation monoids ⋮ The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. ⋮ ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM ⋮ Word problem of the Perkins semigroup via directed acyclic graphs. ⋮ An assertion concerning functionally complete algebras and NP-completeness ⋮ Monoids with sub-log-exponential free spectra. ⋮ Evaluation of polynomials over finite rings via additive combinatorics ⋮ On the rank of the Rees–Sushkevich varieties ⋮ THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS ⋮ The complexity of the equivalence and equation solvability problems over meta-abelian groups

This page was built for publication: Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields