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: 91,423

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.
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.
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.
Game logic is strong enough for parity games.Dietmar Berwanger - 2003 - Studia Logica 75 (2):205 - 219.
Every Finitely Reducible Logic has the Finite Model Property with Respect to the Class of ♦-Formulae.Stéphane Demri & Ewa Orłowska - 1999 - Studia Logica 62 (2):177-200.
On Finite Models of the Lambek Calculus.Maciej Farulewski - 2005 - Studia Logica 80 (1):63-74.
Finite quasivarieties and self-referential conditions.Alexei Vernitski - 2004 - Studia Logica 78 (1-2):337-348.
Not every "tabular" predicate logic is finitely axiomatizable.Dmitrij Skvortsov - 1997 - Studia Logica 59 (3):387-396.
Annotation Theories over Finite Graphs.Dov M. Gabbay & Andrzej Szałas - 2009 - Studia Logica 93 (2):147-180.
A non-finitely based quasi-variety of De Morgan algebras.Hernando Gaitán & Milton Perea - 2004 - Studia Logica 78 (1-2):237-248.
Loosely guarded fragment of first-order logic has the finite model property.Ian Hodkinson - 2002 - Studia Logica 70 (2):205 - 240.
Finite basis problems and results for quasivarieties.Miklós Maróti & Ralph Mckenzie - 2004 - Studia Logica 78 (1-2):293-320.
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.

Analytics

Added to PP
2016-02-15

Downloads
4 (#1,604,214)

6 months
1 (#1,506,218)

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