COMPLEXITY OF SEMIGROUP IDENTITY CHECKING

DOI10.1142/S0218196704001840MaRDI QIDQ4824699zbMATH OpenFDO

Authors Andrzej Kisielewicz

Publication date 1 November 2004

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

computational complexitycommutative semigroupsfinite semigroupssemigroup identitiesco-NP-complete problemsidentity checking

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Commutative semigroups (20M14) Free semigroups, generators and relations, word problems (20M05)

Recommendations

• Complexity of the identity checking problem for finite semigroups.
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• Checking quasi-identities in a finite semigroup may be computationally hard.
• Complexity of the word problem for commutative semigroups of fixed dimension
• Complexity issues of checking identities in finite monoids

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• ALGORITHMIC PROBLEMS IN VARIETIES
• Bases for equational theories of semi-groups
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• Examples of varieties of semigroups
• The complexity of equivalence for commutative rings
• The equivalence problem for finite rings

Cited in

(15)

• An assertion concerning functionally complete algebras and NP-completeness
• Complexity of the word problem for commutative semigroups of fixed dimension
• Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$
• Identity checking problem for transformation monoids
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• Checking quasi-identities in a finite semigroup may be computationally hard.
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• Complexity of identity checking in transformation semigroups of rank 2.
• Complexity of the identity checking problem for finite semigroups.
• Word problem of the Perkins semigroup via directed acyclic graphs.
• Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\).
• Identities of the Kauffman monoid \(\mathcal{K}_3\)
• ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• Complexity issues of checking identities in finite monoids

This page was built for publication: COMPLEXITY OF SEMIGROUP IDENTITY CHECKING

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