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

Miguel Couceiro, Erkko Lehtonen, Karsten Schölzel

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

The 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.

Original languageBritish English
Pages (from-to)39-66
Number of pages28
JournalRAIRO - Operations Research
Volume49
Issue number1
DOIs
StatePublished - 1 Jan 2015

Keywords

  • Boolean functions
  • Clones
  • Constraints
  • Equational classes
  • Threshold functions

Fingerprint

Dive into the research topics of 'A complete classification of equational classes of threshold functions included in clones'. Together they form a unique fingerprint.

Cite this