COMPLEXITY OF SEMIGROUP IDENTITY CHECKING

DOI10.1142/S0218196704001840zbMath1056.20040MaRDI QIDQ4824699

Andrzej P. Kisielewicz

Publication date: 1 November 2004

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

zbMATH Keywords

computational complexityfinite semigroupscommutative semigroupssemigroup identitiesco-NP-complete problemsidentity checking

Mathematics Subject Classification ID

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

Related Items (9)

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. ⋮ Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\). ⋮ Identities of the Kauffman monoid K3 ⋮ Identity checking problem for transformation monoids ⋮ The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. ⋮ Word problem of the Perkins semigroup via directed acyclic graphs. ⋮ An assertion concerning functionally complete algebras and NP-completeness ⋮ The complexity of the equivalence and equation solvability problems over meta-abelian groups

Cites Work

• Unnamed Item
• The complexity of equivalence for commutative rings
• The equivalence problem for finite rings
• Bases for equational theories of semi-groups
• Examples of varieties of semigroups
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• ALGORITHMIC PROBLEMS IN VARIETIES

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