Show simple item record

A complete classification of equational classes of threshold functions included in clones

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorCouceiro, Miguel
HAL ID: 1498
hal.structure.identifierUniversity of Luxembourg, Computer Science Department
dc.contributor.authorLehtonen, Erkko
HAL ID: 737805
ORCID: 0000-0002-9255-5876
hal.structure.identifierMathematics Research Unit
dc.contributor.authorSchölzel, Karsten
dc.date.accessioned2017-08-28T14:49:56Z
dc.date.available2017-08-28T14:49:56Z
dc.date.issued2015
dc.identifier.issn1290-3868
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16638
dc.language.isoenen
dc.subjectBoolean functionsen
dc.subjectthreshold functionsen
dc.subjectconstraintsen
dc.subjectclonesen
dc.subjectequational classesen
dc.subject.ddc512en
dc.titleA complete classification of equational classes of threshold functions included in clonesen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe class of threshold functions is known to be characterizable by functional equations or, equivalently, by pairs of relations, which are called relational constraints. It was shown by Hellerstein that this class cannot be characterized by a finite number of such objects. In this paper, we investigate classes of threshold functions which arise as intersections of the class of all threshold functions with clones of Boolean functions, and provide a complete classification of such intersections in respect to whether they have finite characterizations. Moreover, we provide a characterizing set of relational constraints for each class of threshold functions arising in this way.en
dc.relation.isversionofjnlnameRAIRO - Operations Research
dc.relation.isversionofjnlvol49en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2015-01
dc.relation.isversionofjnlpages39-66en
dc.relation.isversionofdoi10.1051/ro/2014034en
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-01090621en
dc.subject.ddclabelAlgèbreen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-07-24T08:54:54Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record