Journal article icon

Journal article

Functional clones and expressibility of partition functions

Abstract:
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.
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1016/j.tcs.2017.05.001

Authors


Bulatov, A More by this author
More by this author
Department:
Oxford, MPLS, Computer Science
More by this author
Department:
Oxford, MPLS, Computer Science
More by this author
Department:
Oxford, MPLS, Computer Science
More from this funder
Funding agency for:
Goldberg, LA
Expand funders...
Publisher:
Elsevier Publisher's website
Journal:
Theoretical Computer Science Journal website
Volume:
687
Pages:
11-39
Publication date:
2017-05-11
Acceptance date:
2017-05-01
DOI:
ISSN:
0304-3975
Pubs id:
pubs:692038
URN:
uri:75cde23b-2cf4-41ac-9b90-6d5458ea5d38
UUID:
uuid:75cde23b-2cf4-41ac-9b90-6d5458ea5d38
Local pid:
pubs:692038

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP