| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [15 references]
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
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)