Complexity issues of checking identities in finite monoids

DOI10.1007/s00233-009-9180-yzbMath1185.68345MaRDI QIDQ2655464

Ondřej Klíma

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

zbMATH Keywords

complexity; finite semigroups; checking identities

Mathematics Subject Classification ID

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item