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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Polynomially Closed Co-clones
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology. Univ London, Dept Comp Sci, London WC1E 7HU, England.
Number of Authors: 2
2014 (English)In: 2014 IEEE 44TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2014), IEEE Computer Society, 2014, 85-90 p.Conference paper, Published paper (Refereed)
Abstract [en]

Two well-studied closure operators for relations are based on primitive positive (p.p.) definitions and quantifier free p.p. definitions. The latter do however have limited expressiveness and the corresponding lattice of strong partial clones is uncountable. We consider implementations allowing polynomially many existentially quantified variables and obtain a dichotomy for co-clones where such implementations are enough to implement any relation and prove (1) that all remaining coclones contain relations requiring a superpolynomial amount of quantified variables and (2) that the strong partial clones corresponding to two of these co-clones are of infinite order whenever the set of invariant relations can be finitely generated.

Place, publisher, year, edition, pages
IEEE Computer Society, 2014. 85-90 p.
Series
International Symposium on Multiple-Valued Logic, ISSN 0195-623X
National Category
Natural Sciences Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-112915DOI: 10.1109/ISMVL.2014.23ISI: 000361020700015ISBN: 9781479935369 (print)OAI: oai:DiVA.org:liu-112915DiVA: diva2:773692
Conference
IEEE 44th International Symposium on Multiple-Valued Logic (ISMVL-2014)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2015-10-07

Open Access in DiVA

No full text

Other links

Publisher's full textFulltext

Authority records BETA

Lagerkvist, VictorWahlström, Magnus

Search in DiVA

By author/editor
Lagerkvist, VictorWahlström, Magnus
By organisation
Software and SystemsThe Institute of TechnologyTCSLAB - Theoretical Computer Science Laboratory
Natural SciencesComputer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 46 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf