HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01504012
Contributor : Miguel Couceiro Connect in order to contact the contributor
Submitted on : Saturday, April 8, 2017 - 1:17:27 AM
Last modification on : Wednesday, November 3, 2021 - 7:57:51 AM
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

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⟩

Share

Metrics

Record views

460

Files downloads

96