Complexity of the identity checking problem for finite semigroups.

DOI10.1007/S10958-009-9397-ZMaRDI QIDQ843593zbMATH OpenOpenAlexFDO

Authors S. V. Goldberg, Jorge Almeida, M. 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 complexitysolvable groupsfinite semigroupssemigroups of transformationsco-NP-complete problemsdecidability in polynomial timeidentity checking problem

Mathematics Subject Classification ID

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

Recommendations

• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• Complexity of identity checking in transformation semigroups of rank 2.
• Checking quasi-identities in a finite semigroup may be computationally hard.
• On the computational complexity of matrix semigroup problems
• The complexity of properties of transformation semigroups
• Identity checking problem for transformation monoids
• scientific article; zbMATH DE number 4068272
• Complexity issues of checking identities in finite monoids
• Improved lower bounds for the complexity of finite semigroups
• Decidability of semigroup identities in soluble groups

Cites work

• scientific article; zbMATH DE number 3875506 (Why is no real title available?)
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A 2EXPTIME complete varietal membership problem
• ALGORITHMIC PROBLEMS IN VARIETIES
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
• Complexity issues of checking identities in finite monoids
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• On Comparison of Finite Algebras
• On certain finitely based varieties of semigroups
• Results on the equivalence problem for finite groups.
• SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• The complexity of checking identities for finite matrix rings
• The complexity of equivalence for commutative rings
• The complexity of the equivalence problem for nonsolvable groups
• The complexity of the word-problem for finite matrix rings
• The equivalence problem for finite rings

Cited in

(24)

• Words separation and positive identities in symmetric groups
• Representations and identities of hypoplactic monoids with involution
• Complexity issues of checking identities in finite monoids
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\).
• Complexity of identity checking in transformation semigroups of rank 2.
• Lower bounds on words separation: are there short identities in transformation semigroups?
• Effective dimension of finite semigroups.
• Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$
• Representations and identities of Baxter monoids with involution
• Identity checking problem for transformation monoids
• The intersection problem for finite semigroups
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• Identities of the Kauffman monoid \(\mathcal{K}_3\)
• The complexity of the equivalence and equation solvability problems over nilpotent rings and groups.
• Evaluation of polynomials over finite rings via additive combinatorics
• Checking quasi-identities in a finite semigroup may be computationally hard.
• The complexity of properties of transformation semigroups
• ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS
• On the complexity of inverse semigroup conjugacy
• The intersection problem for finite semigroups
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• Identities in twisted Brauer monoids

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

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