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

co-NP-complete problemscomputational complexitydecidability in polynomial timefinite semigroupsidentity checking problemsemigroups of transformationssolvable groups

Mathematics Subject Classification ID

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

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

• A 2EXPTIME complete varietal membership problem
• ALGORITHMIC PROBLEMS IN VARIETIES
• Complexity issues of checking identities in finite monoids
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• 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
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
• 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?)
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• On certain finitely based varieties of semigroups
• On Comparison of Finite Algebras
• Results on the equivalence problem for finite groups.
• SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
• The complexity of checking identities for finite matrix rings
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• 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
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM

Cited in

(27)

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

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)