Complexity issues of checking identities in finite monoids

DOI10.1007/s00233-009-9180-yzbMath1185.68345OpenAlexW2064411534MaRDI 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

complexityfinite semigroupschecking identities

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (15)

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. ⋮ Satisfiability in MultiValued Circuits ⋮ 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 ⋮ On finitely related semigroups. ⋮ The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. ⋮ A minimal nonfinitely based semigroup whose variety is polynomially recognizable. ⋮ Monoids with sub-log-exponential free spectra. ⋮ Checking quasi-identities in a finite semigroup may be computationally hard. ⋮ From \(A\) to \(B\) to \(Z\) ⋮ Evaluation of polynomials over finite rings via additive combinatorics ⋮ The complexity of the equivalence and equation solvability problems over meta-abelian groups

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

This page was built for publication: Complexity issues of checking identities in finite monoids