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

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

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〉

Partager

Métriques

Consultations de la notice

408

Téléchargements de fichiers

39