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.
Type de document :
Communication dans un congrès
47th IEEE International Symposium on Multiple-Valued Logic (ISMVL), May 2017, Novi Sad, Serbia. IEEE Computer Society, 2017
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01504012
Contributeur : Miguel Couceiro <>
Soumis le : samedi 8 avril 2017 - 01:17:27
Dernière modification le : jeudi 5 avril 2018 - 09:56:01
Document(s) archivé(s) le : dimanche 9 juillet 2017 - 12:12:30

Fichier

maximal_partial_subclones_revi...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01504012, version 1

Collections

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

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. IEEE Computer Society, 2017. 〈hal-01504012〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

394

Téléchargements de fichiers

37

Contact


archive-ouverte@inria.fr