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 in Q? is co-NP-complete while the question Does a given identity hold in Q? can be answered in linear time.

Categories

Keywords

Reprint years

2005

DOI

10.1007/s11225-005-0356-5

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,290

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

Flat algebras and the translation of universal Horn logic to equational logic.Marcel Jackson - 2008 - Journal of Symbolic Logic 73 (1):90-128.
The greatest extension of s4 into which intuitionistic logic is embeddable.Michael Zakharyaschev - 1997 - Studia Logica 59 (3):345-358.
Quasi-varieties: A special access.Hans-Jürgen Hoehnke - 2004 - Studia Logica 78 (1-2):249 - 260.
On some Kripke complete and Kripke incomplete intermediate predicate logics.Dmitrij Skvortsov - 1998 - Studia Logica 61 (2):281-292.
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.
On relative universality and Q-universality.V. Koubek & J. Sichler - 2004 - Studia Logica 78 (1-2):279-291.
Finite quasivarieties and self-referential conditions.Alexei Vernitski - 2004 - Studia Logica 78 (1-2):337 - 348.
The Quasi-lattice of Indiscernible Elements.Mauri Cunha do Nascimento, Décio Krause & Hércules Araújo Feitosa - 2011 - Studia Logica 97 (1):101-126.
Kripke incompleteness of predicate extensions of the modal logics axiomatized by a canonical formula for a frame with a nontrivial cluster.Tatsuya Shimura - 2000 - Studia Logica 65 (2):237-247.
On Pretabular Extensions of Relevance Logic.Asadollah Fallahi & James Gordon Raftery - 2024 - Studia Logica 112 (5):967-985.

Analytics

Added to PP
2009-01-28

Downloads
44 (#498,365)

6 months
16 (#178,571)

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