liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Bounded Bases of Strong Partial Clones
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
Department of Computer Science, Royal Holloway, University of London, Great Britain.
GREYC, Normandie Université, UNICAEN, CNRS, ENSICAEN, Franc.
2015 (Engelska)Ingår i: Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on, IEEE , 2015, s. 189-194Konferensbidrag, Publicerat paper (Refereegranskat)
Resurstyp
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.

Ort, förlag, år, upplaga, sidor
IEEE , 2015. s. 189-194
Serie
International Symposium on Multiple-Valued Logic. Proceedings, ISSN 0195-623X
Nyckelord [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
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:liu:diva-123384DOI: 10.1109/ISMVL.2015.33ISI: 000380463600033ISBN: 978-1-4799-1777-8 (tryckt)OAI: oai:DiVA.org:liu-123384DiVA, id: diva2:882537
Konferens
2015 IEEE 45th International Symposium on Multiple-Valued Logic, 18–20 May 2015, Waterloo, Ontario, Canada
Tillgänglig från: 2015-12-15 Skapad: 2015-12-15 Senast uppdaterad: 2018-01-10Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Lagerkvist, VicktorWahlström, Magnus

Sök vidare i DiVA

Av författaren/redaktören
Lagerkvist, VicktorWahlström, Magnus
Av organisationen
Programvara och systemTekniska fakulteten
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 14 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf