Polynomially Closed Co-clones
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 (Refereed)
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.
, International Symposium on Multiple-Valued Logic, ISSN 0195-623X
Natural Sciences Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-112915DOI: 10.1109/ISMVL.2014.23ISI: 000361020700015ISBN: 9781479935369OAI: oai:DiVA.org:liu-112915DiVA: diva2:773692
IEEE 44th International Symposium on Multiple-Valued Logic (ISMVL-2014)