Complexity issues of checking identities in finite monoids
From MaRDI portal
Publication:2655464
DOI10.1007/s00233-009-9180-yzbMath1185.68345MaRDI QIDQ2655464
Publication date: 25 January 2010
Published in: Semigroup Forum (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00233-009-9180-y
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$, Satisfiability in MultiValued Circuits, Identities of the Kauffman monoid K3, A survey on varieties generated by small semigroups and a companion website, Identity checking problem for transformation monoids, The complexity of the equivalence and equation solvability problems over nilpotent rings and groups., Complexity of the identity checking problem for finite semigroups., Checking quasi-identities in a finite semigroup may be computationally hard., Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\)., On finitely related semigroups., From \(A\) to \(B\) to \(Z\), Evaluation of polynomials over finite rings via additive combinatorics, A minimal nonfinitely based semigroup whose variety is polynomially recognizable., The complexity of the equivalence and equation solvability problems over meta-abelian groups, Monoids with sub-log-exponential free spectra.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of equivalence for commutative rings
- Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
- The equivalence problem for finite rings
- Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
- Results on the equivalence problem for finite groups.
- The complexity of checking identities for finite matrix rings
- THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
- The complexity of the equivalence problem for nonsolvable groups
- THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM