Checking quasi-identities in a finite semigroup may be computationally hard.

DOI10.1007/s11225-005-0356-5zbMath1076.20043OpenAlexW2005496785MaRDI QIDQ1770618

Mikhail V. Volkov

Publication date: 7 April 2005

Published in: Studia Logica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11225-005-0356-5

zbMATH Keywords

identitiesNP-completenessfinite semigroupsquasi-identities

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Varieties and pseudovarieties of semigroups (20M07) Free semigroups, generators and relations, word problems (20M05) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quasivarieties (08C15)

Related Items (2)

Word problem of the Perkins semigroup via directed acyclic graphs. ⋮ INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity issues of checking identities in finite monoids
• Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM

This page was built for publication: Checking quasi-identities in a finite semigroup may be computationally hard.