Complexity issues of checking identities in finite monoids

DOI10.1007/S00233-009-9180-YMaRDI QIDQ2655464zbMATH OpenOpenAlexFDO

Authors 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

checking identitiescomplexityfinite semigroups

Mathematics Subject Classification ID

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

Recommendations

• Identity checking problem for transformation monoids
• Complexity of the identity checking problem for finite semigroups.
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• Checking quasi-identities in a finite semigroup may be computationally hard.
• scientific article; zbMATH DE number 1834675

Cites work

• Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• scientific article; zbMATH DE number 5535222 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1759404 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• 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 equivalence for commutative rings
• The complexity of the equivalence problem for nonsolvable groups
• The equivalence problem for finite rings
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM

Cited in

(24)

• Complexity results on the conjugacy problem for monoids
• Computations over finite monoids and their test complexity
• Checking quasi-identities in a finite semigroup may be computationally hard.
• Equivalence and equation solvability problems for the alternating group A₄.
• 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.
• The complexity of checking identities for finite matrix rings
• Checking identities is computationally intractable NP-hard and therefore human provers will always be needed
• The membership problem in aperiodic transformation monoids
• Identity checking problem for transformation monoids
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• 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 \(\mathcal{K}_3\)
• A survey on varieties generated by small semigroups and a companion website
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• Hardness of equations over finite solvable groups under the exponential time hypothesis
• Circuit equivalence in 2-nilpotent algebras
• Flexible constraint satisfiability and a problem in semigroup theory
• Complexity of the identity checking problem for finite semigroups.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2655464)