liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Inngår i: Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on, IEEE , 2015, s. 189-194Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
IEEE , 2015. s. 189-194
Serie
International Symposium on Multiple-Valued Logic. Proceedings, ISSN 0195-623X
Emneord [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
HSV kategori
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
Konferanse
2015 IEEE 45th International Symposium on Multiple-Valued Logic, 18–20 May 2015, Waterloo, Ontario, Canada
Tilgjengelig fra: 2015-12-15 Laget: 2015-12-15 Sist oppdatert: 2018-01-10bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Lagerkvist, VicktorWahlström, Magnus

Søk i DiVA

Av forfatter/redaktør
Lagerkvist, VicktorWahlström, Magnus
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 14 treff
RefereraExporteraLink to record
Permanent link

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