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

Studia Logica 78 (1-2):349-356 (2004)
  Copy   BIBTEX

Abstract

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

Categories

Keywords

Reprint years

2005

DOI

10.1007/s11225-005-0356-5

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,932

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Checking quasi-identities in a finite semigroup may be computationally hard.M. V. Volkov - 2004 - Studia Logica 78 (1-2):349 - 356.
The greatest extension of s4 into which intuitionistic logic is embeddable.Michael Zakharyaschev - 1997 - Studia Logica 59 (3):345-358.
An application of a Theorem of Ash to finite covers.Karl Auinger, Gracinda M. S. Gomes, Victoria Gould & Benjamin Steinberg - 2004 - Studia Logica 78 (1-2):45-57.
Flat algebras and the translation of universal Horn logic to equational logic.Marcel Jackson - 2008 - Journal of Symbolic Logic 73 (1):90-128.
Finite quasivarieties and self-referential conditions.Alexei Vernitski - 2004 - Studia Logica 78 (1-2):337 - 348.
Finite quasivarieties and self-referential conditions.Alexei Vernitski - 2004 - Studia Logica 78 (1-2):337-348.
Priestley duality for quasi-stone algebras.Hernando Gaitán - 2000 - Studia Logica 64 (1):83-92.
A non-finitely based quasi-variety of De Morgan algebras.Hernando Gaitán & Milton Perea - 2004 - Studia Logica 78 (1-2):237-248.
A non-finitely based quasi-variety of de Morgan algebras.Hernando Gaitán & Milton H. Perea - 2004 - Studia Logica 78 (1-2):237 - 248.
Quasi-completeness in non-Fregean logic.Roman Suszko - 1971 - Studia Logica 29 (1):7-16.

Analytics

Added to PP
2016-02-15

Downloads
4 (#1,645,111)

6 months
4 (#1,005,098)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references