Technical Report CS0677

TR#:CS0677
Class:CS
Title: SOME ASPECTS OF THE MEMBERSHIP PROBLEM FOR GRAPHOIDS
Authors: S. Ur and A. Paz
PDF - RevisedCS0677.revised.pdf
Abstract: Given a set of triplets $B = \{(X,Z,Y)\}$ of polynomial size over a finite (random variables, attributes), and a triplet $t = (P,Q,R)$ over the same domain, the membership problem is to ascertain whether $t$ is in the closure of $B$ under the graphoid axioms defined in the text. The closure of such $B$'s under the graphoid axioms (graphoids) are intended as models for representing irrelevance relations. The complexity of the membership problem is not known. In this paper we reduce the general membership problem to a polynomially equivalent simpler membership problem and we define an elementary membership problem whose complexity is also not known and which is a particular case of the simple membership problem.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0677), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion
admin