Complexity of the identity checking problem for finite semigroups.

DOI10.1007/S10958-009-9397-ZzbMATH Open1213.20052OpenAlexW2044956773MaRDI QIDQ843593FDOQ843593

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• ALGORITHMIC PROBLEMS IN VARIETIES
• Title not available (Why is that?)
• The equivalence problem for finite rings
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• Title not available (Why is that?)
• On certain finitely based varieties of semigroups
• SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
• 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
• The complexity of the word-problem for finite matrix rings
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• The complexity of the equivalence problem for nonsolvable groups
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• The complexity of equivalence for commutative rings
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS
• A 2EXPTIME complete varietal membership problem
• On Comparison of Finite Algebras

Cited In (24)

• Representations and identities of Baxter monoids with involution
• Representations and identities of hypoplactic monoids with involution
• Words separation and positive identities in symmetric groups
• The intersection problem for finite semigroups
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING
• Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$
• The intersection problem for finite semigroups
• 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.
• Identities in twisted Brauer monoids
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• Effective dimension of finite semigroups.
• On the complexity of inverse semigroup conjugacy
• 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
• Lower bounds on words separation: are there short identities in transformation semigroups?
• Evaluation of polynomials over finite rings via additive combinatorics
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• Complexity issues of checking identities in finite monoids
• The complexity of properties of transformation 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)