THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM

DOI10.1142/S0218196705002293zbMath1101.68037OpenAlexW2132524082MaRDI QIDQ5461667

Steve Seif

Publication date: 26 July 2005

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218196705002293

zbMATH Keywords

computational complexityword problemidentity-checking problemPerkins semigroupTerm-equivalence problem

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Word problems (aspects of algebraic structures) (08A50)

Related Items

Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$, Complexity of the identity checking problem for finite semigroups., Complexity issues of checking identities in finite monoids, A survey on varieties generated by small semigroups and a companion website, Identities of the Kauffman monoid K3, Identity checking problem for transformation monoids, On finitely related semigroups., Word problem of the Perkins semigroup via directed acyclic graphs., A minimal nonfinitely based semigroup whose variety is polynomially recognizable., On the representation number of a crown graph, Monoids with sub-log-exponential free spectra., Bases of identities for semigroups of bounded rank transformations of a set., Checking quasi-identities in a finite semigroup may be computationally hard., From \(A\) to \(B\) to \(Z\), INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS, On free spectra of finite completely regular semigroups and monoids., COLLAPSING WORDS: A PROGRESS REPORT, On the rank of the Rees–Sushkevich varieties, Word-representability of Toeplitz graphs

Cites Work

• Unnamed Item
• The complexity of equivalence for commutative rings
• Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem
• The equivalence problem for finite rings
• Bases for equational theories of semi-groups
• Free Objects in Certain Varieties of Inverse Semigroups
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory