Change search
ReferencesLink to record
Permanent link

Direct link
Weak bases of Boolean co-clones
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
2014 (English)In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 114, no 9, 462-468 p.Article in journal (Refereed) Published
Abstract [en]

Universal algebra has proven to be a useful tool in the study of constraint satisfaction problems (CSP) since the complexity, up to logspace reductions, is determined by the clone of the constraint language. But two CSPs corresponding to the same clone may still differ substantially with respect to worst-case time complexity, which makes clones ill-suited when comparing running times of CSP problems. In this article we instead consider an algebra where each clone splits into an interval of strong partial clones such that a strong partial clone corresponds to the CSPs that are solvable within the same O(c(n)) bound. We investigate these intervals and give relational descriptions, weak bases; of the largest elements. They have a highly regular form and are in many cases easily relatable to the smallest members in the intervals, which suggests that the lattice of strong partial clones has a simpler structure than the lattice of partial clones.

Place, publisher, year, edition, pages
Elsevier , 2014. Vol. 114, no 9, 462-468 p.
Keyword [en]
Computational complexity; Clone theory; Boolean relations; Constraint satisfaction problems
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-108789DOI: 10.1016/j.ipl.2014.03.011ISI: 000336877100002OAI: diva2:732922
Available from: 2014-07-07 Created: 2014-07-06 Last updated: 2014-08-21

Open Access in DiVA

fulltext(589 kB)58 downloads
File information
File name FULLTEXT01.pdfFile size 589 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Lagerkvist, Victor
By organisation
Software and SystemsThe Institute of Technology
In the same journal
Information Processing Letters
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 58 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 37 hits
ReferencesLink to record
Permanent link

Direct link