Functional clones and expressibility of partition functions
We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions f0; 1gk ! R≥0) closed under (essentially) multiplication, summation and limits. Functional clones naturally form a lattice under set inclusion and are closely related to counting Constraint Satisfaction Pr...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2017
|
| _version_ | 1826279562467606528 |
|---|---|
| author | Bulatov, A Goldberg, L Jerrum, M Richerby, D Zivny, S |
| author_facet | Bulatov, A Goldberg, L Jerrum, M Richerby, D Zivny, S |
| author_sort | Bulatov, A |
| collection | OXFORD |
| description | We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions f0; 1gk ! R≥0) closed under (essentially) multiplication, summation and limits. Functional clones naturally form a lattice under set inclusion and are closely related to counting Constraint Satisfaction Problems (CSPs). We identify a sublattice of interesting functional clones and investigate the relationships and properties of the functional clones in this sublattice. |
| first_indexed | 2024-03-07T00:00:36Z |
| format | Journal article |
| id | oxford-uuid:75cde23b-2cf4-41ac-9b90-6d5458ea5d38 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:00:36Z |
| publishDate | 2017 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:75cde23b-2cf4-41ac-9b90-6d5458ea5d382022-03-26T20:11:40ZFunctional clones and expressibility of partition functionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:75cde23b-2cf4-41ac-9b90-6d5458ea5d38Symplectic Elements at OxfordElsevier2017Bulatov, AGoldberg, LJerrum, MRicherby, DZivny, SWe study functional clones, which are sets of non-negative pseudo-Boolean functions (functions f0; 1gk ! R≥0) closed under (essentially) multiplication, summation and limits. Functional clones naturally form a lattice under set inclusion and are closely related to counting Constraint Satisfaction Problems (CSPs). We identify a sublattice of interesting functional clones and investigate the relationships and properties of the functional clones in this sublattice. |
| spellingShingle | Bulatov, A Goldberg, L Jerrum, M Richerby, D Zivny, S Functional clones and expressibility of partition functions |
| title | Functional clones and expressibility of partition functions |
| title_full | Functional clones and expressibility of partition functions |
| title_fullStr | Functional clones and expressibility of partition functions |
| title_full_unstemmed | Functional clones and expressibility of partition functions |
| title_short | Functional clones and expressibility of partition functions |
| title_sort | functional clones and expressibility of partition functions |
| work_keys_str_mv | AT bulatova functionalclonesandexpressibilityofpartitionfunctions AT goldbergl functionalclonesandexpressibilityofpartitionfunctions AT jerrumm functionalclonesandexpressibilityofpartitionfunctions AT richerbyd functionalclonesandexpressibilityofpartitionfunctions AT zivnys functionalclonesandexpressibilityofpartitionfunctions |