Identity checking problem for transformation monoids

DOI10.1007/S00233-012-9401-7zbMATH Open1282.68117OpenAlexW1994353492MaRDI QIDQ444673FDOQ444673

Authors: Ondřej Klíma 

Publication date: 16 August 2012

Published in: Semigroup Forum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00233-012-9401-7

Recommendations

• Complexity issues of checking identities in finite monoids
• Complexity of the identity checking problem for finite semigroups.
• Complexity of identity checking in transformation semigroups of rank 2.
• The complexity of properties of transformation semigroups
• COMPLEXITY OF SEMIGROUP IDENTITY CHECKING

zbMATH Keywords

computational complexitytransformation monoidchecking identitiesfinite semigroup

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Applications of universal algebra in computer science (08A70)

Cites Work

• Title not available (Why is that?)
• Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\).
• The equivalence problem for finite rings
• THE COMPLEXITY OF CHECKING IDENTITIES OVER FINITE GROUPS
• Dichotomies in the complexity of solving systems of equations over finite semigroups
• Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
• 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
• Title not available (Why is that?)
• 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 the identity checking problem for finite semigroups.

Cited In (13)

• Identities and transductions
• Words separation and positive identities in symmetric groups
• Characterization of idempotent transformation monoids
• Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$
• Checking quasi-identities in a finite semigroup may be computationally hard.
• Complexity of identity checking in transformation semigroups of rank 2.
• Complexity of the identity checking problem for finite semigroups.
• Identities of the Kauffman monoid \(\mathcal{K}_3\)
• Lower bounds on words separation: are there short identities in transformation semigroups?
• The complexity of checking identities for finite matrix rings
• The complexity of the equivalence and equation solvability problems over meta-abelian groups
• Complexity issues of checking identities in finite monoids
• RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS

This page was built for publication: Identity checking problem for transformation monoids

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