Identity checking problem for transformation monoids

DOI10.1007/s00233-012-9401-7zbMath1282.68117MaRDI QIDQ444673

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

zbMATH Keywords

computational complexity; transformation monoid; checking identities; finite semigroup

Mathematics Subject Classification ID

08A70: Applications of universal algebra in computer science

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, Identities of the Kauffman monoid K3, 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?

Cites Work

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