Complexity of the identity checking problem for finite semigroups.

DOI10.1007/s10958-009-9397-zzbMath1213.20052OpenAlexW2044956773MaRDI QIDQ843593

S. V. Goldberg, Jorge Almeida, Mikhail V. Volkov

Publication date: 15 January 2010

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10958-009-9397-z

zbMATH Keywords

computational complexityfinite semigroupssolvable groupssemigroups of transformationsco-NP-complete problemsdecidability in polynomial timeidentity checking problem

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$ ⋮ Lower bounds on words separation: are there short identities in transformation semigroups? ⋮ Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\). ⋮ Identities of the Kauffman monoid K3 ⋮ Representations and identities of Baxter monoids with involution ⋮ Representations and identities of hypoplactic monoids with involution ⋮ Identities in twisted Brauer monoids ⋮ Identity checking problem for transformation monoids ⋮ The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. ⋮ Unnamed Item ⋮ 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
• Unnamed Item
• The complexity of equivalence for commutative rings
• On certain finitely based varieties of semigroups
• 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
• Complexity issues of checking identities in finite monoids
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
• A 2EXPTIME Complete Varietal Membership Problem
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• The complexity of the word-problem for finite matrix rings
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• ALGORITHMIC PROBLEMS IN VARIETIES
• The complexity of the equivalence problem for nonsolvable groups
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
• On Comparison of Finite Algebras

This page was built for publication: Complexity of the identity checking problem for finite semigroups.