COMPLEXITY OF SEMIGROUP IDENTITY CHECKING

DOI10.1142/S0218196704001840zbMATH Open1056.20040MaRDI QIDQ4824699FDOQ4824699

Authors: Andrzej Kisielewicz 

Publication date: 1 November 2004

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

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

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)

Cites Work

• Title not available (Why is that?)
• ALGORITHMIC PROBLEMS IN VARIETIES
• The equivalence problem for finite rings
• Bases for equational theories of semi-groups
• The complexity of equivalence for commutative rings
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• Examples of varieties of semigroups

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 PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• 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.
• 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)