Skip to main navigation Skip to search Skip to main content

A characterization of Boolean collections of set-valued functions

  • Université du Québec à Trois-Rivières
  • University of Ottawa
  • University of Novi Sad

Research output: Contribution to journal › Article › peer-review

Abstract

We consider functions on subsets of a finite element set r = {0,..., r - 1}. A small fraction of these functions are Boolean functions, i.e., functions that can be constructed from constants and variables, using union, intersection, and complementation. We introduce the notion of Boolean collection of sets, and explore several combinatorial aspects of these collections. A collection C is a set consisting of several n-tuples of subsets of r. We solve the following problem. Given n ≥ 1, characterize collections C for which there exists a Boolean function F: script P sign(r)n → script P sign(r) such that F(X1,...,Xn) = Ø if and only if (X1,..., Xn) ∈C, where X1,..., Xn ∈script P sign(r) and script P sign(r) is the set of subsets of r.

Original languageEnglish
Pages (from-to)195-204
Number of pages10
JournalInformation Sciences
Volume99
Issue number3-4
DOIs
StatePublished - Jul 1997

ASJC Scopus Subject Areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A characterization of Boolean collections of set-valued functions'. Together they form a unique fingerprint.

Cite this