On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total Operations

Miguel Couceiro 1 Lucien Haddad 2 Victor Lagerkvist 3 Biman Roy 4
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
2 RMCC - Royal Military College of Canada
3 Institut für Algebra [Dresden]
4 Linköpings universitet
Abstract : A strong partial clone is a set of partial operations closed under composition and containing all partial projections. Let X be the set of all Boolean strong partial clones whose total operations are the projections. This set is of practical interest since it induces a partial order on the complexity of NP-complete constraint satisfaction problems. In this paper we study X from the algebraic point of view, and prove that there exists two intervals in X , corresponding to natural constraint satisfaction problems, such that one is at least countably infinite and the other has the cardinality of the continuum.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download
https://hal.inria.fr/hal-01504012
Contributor : Miguel Couceiro <>
Submitted on : Saturday, April 8, 2017 - 1:17:27 AM
Last modification on : Tuesday, December 18, 2018 - 4:38:02 PM
Long-term archiving on : Sunday, July 9, 2017 - 12:12:30 PM

File

maximal_partial_subclones_revi...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01504012, version 1

Collections

INSMI | INRIA | LORIA | LORIA-NLPKD | UNIV-LORRAINE

Citation

Miguel Couceiro, Lucien Haddad, Victor Lagerkvist, Biman Roy. On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total Operations. 47th IEEE International Symposium on Multiple-Valued Logic (ISMVL), May 2017, Novi Sad, Serbia. ⟨hal-01504012⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

613

Files downloads

108

Contact


archive-ouverte@inria.fr