liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Bounded Bases of Strong Partial Clones
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Department of Computer Science, Royal Holloway, University of London, Great Britain.
GREYC, Normandie Université, UNICAEN, CNRS, ENSICAEN, Franc.
2015 (English)In: Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on, IEEE , 2015, 189-194 p.Conference paper (Refereed)Text
Abstract [en]

Partial clone theory has successfully been applied to study the complexity of the constraint satisfaction problem parameterized by a set of relations (CSP(G)). Lagerkvist & Wahlstroï¿œm (ISMVL 2014) however shows that the partial polymorphisms of G (?P?I(G)) cannot be finitely generated for finite, Boolean G if CSP(G) is NP-hard (assuming P?NP). In this paper we consider stronger closure operators than functional composition which can generate ?P?I(G) from a finite set of partial functions, a bounded base. Determining bounded bases for finite languages provides a complete characterization of their partial polymorphisms and we provide such bases for k-SAT and 1-in-k-SAT.

Place, publisher, year, edition, pages
IEEE , 2015. 189-194 p.
Series
, International Symposium on Multiple-Valued Logic. Proceedings, ISSN 0195-623X
Keyword [en]
computational complexity;functions;set theory;G (?P?I(G));bounded base;closure operators;partial functions;partial polymorphisms;strong partial clone;Assistive technology;Cloning;Context;Electronic mail;Lattices;NP-hard problem;Clone theory;constraint satisfaction;partial clone theory
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-123384DOI: 10.1109/ISMVL.2015.33ISI: 000380463600033ISBN: 978-1-4799-1777-8OAI: oai:DiVA.org:liu-123384DiVA: diva2:882537
Conference
2015 IEEE 45th International Symposium on Multiple-Valued Logic, 18–20 May 2015, Waterloo, Ontario, Canada
Available from: 2015-12-15 Created: 2015-12-15 Last updated: 2016-08-19Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lagerkvist, VicktorWahlström, Magnus
By organisation
Software and SystemsFaculty of Science & Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
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: 7 hits
ReferencesLink to record
Permanent link

Direct link