Positive and Horn decomposability of partially defined Boolean functions (Q1356507)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Positive and Horn decomposability of partially defined Boolean functions
scientific article

    Statements

    Positive and Horn decomposability of partially defined Boolean functions (English)
    0 references
    0 references
    0 references
    0 references
    29 October 1997
    0 references
    Let \(T\) be a set of positive examples, \(F\) a set of negative examples, i.e. \(T,F\subset\{0,1\}^n\), \(T\cap F=\emptyset\), and let \((T,F)\) be the partially defined Boolean function (pdBf), defined by \[ (T,F)(\nu)=\begin{cases} 1\text{ if }\nu\in T\\ 0\text{ if }\nu\in F\end{cases} \] Given a pdBf \((T,F)\) and a family of subsets \(S_i\subseteq\{1,2,\dots,n\}\), \(i=0,\dots,k\), the decomposability problem is to decide the existence of Boolean functions \(h_1,\dots,h_k\), \(g\) such that the function \(f(\nu)=g(\nu[S_0],h_1(\nu[S_1]),h_2(\nu[S_2]),\dots,h_k(\nu[S_k]))\) is an extension of the pdBf \((T,F)\), where \(\nu[S]\) denotes the projection of the vector \(\nu\) on the subset \(S\) of indices. Let \(P\), \(H\) denote classes of positive and Horn functions and let, e.g., \(P(S_0,P(S_1),\dots,P(S_k))\) be a decomposition \(g(\nu[S_0],h_1(\nu[S_1]),h_2(\nu[S_2]),\dots,h_k(\nu[S_k]))\) where all functions \(g\), \(h_i\) are positive. Several results on the complexity of finding decompositions have been obtained, e.g., it is shown that for schemes \(P(S_0,P(S_1),P(S_2),P(S_3))\), \(P(S_0,P(S_1),H(S_2))\) the decomposability problem is NP-complete, but \(P(P(S_1),H(S_2))\) and \(H(P(S_1),P(S_2))\) both can be solved in polynomial time.
    0 references
    partial Boolean functions
    0 references
    complexity
    0 references
    positive functions
    0 references
    positive examples
    0 references
    negative examples
    0 references
    Horn functions
    0 references
    decomposition
    0 references
    decomposability
    0 references
    NP-complete
    0 references
    0 references

    Identifiers