Studia Logica
Volume 78, Numbers 1-2, 349-356, DOI: 10.1007/s11225-005-0356-5

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

M. V. Volkov

View Related Documents

Abstract

We exhibit a 10-element semigroup Q such that the question ldquoDoes a given quasi-identity hold in Q?rdquo is co-NP-complete while the question ldquoDoes a given identity hold in Q?rdquo can be answered in linear time.

Keywords  semigroup - identity - quasi-identity - NP-completeness

Special issue of Studia Logica: ldquoAlgebraic Theory of Quasivarietiesrdquo Presented by M. E. Adams, K. V. Adaricheva, W. Dziobiak, and A. V. Kravchenko

Fulltext Preview

Image of the first page of the fulltext document