Relations and GUHA-Style Data Mining II

摘要

The problem of representability of a (finite) Boolean algebra with an additional binary relation by a data matrix (information structure) and a binary generalized quantifier is studied for various classes of (associational) quantifiers. The computational complexity of the problem for the class of all associational quantifiers and for the class of all implicational quantifiers is determined and the problem is related to (generalized) threshold functions and (positive) assumability.