Read-once function: Difference between revisions

Revision as of 04:40, 18 May 2016

Revision as of 21:22, 4 June 2016

Line 14:

==Characterization==

The [[disjunctive normal form]] of a (positive) read-once function is not generally itself read-once. Nevertheless, it carries important information about the function. In particular, if one forms a ''co-occurrence graph'' in which the vertices represent variables, and edges connect pairs of variables that both occur in the same clause of the conjunctive normal form, then the co-occurrence graph of a read-once function is necessarily a [[cograph]]. More precisely, a positive Boolean function is read-once if and only if its co-occurrence graph is a cograph, and in addition every [[maximal clique (graph theory)|complete subgraph]] of the co-occurrence graph forms a subset of one of the conjunctions (prime implicants) of the disjunctive normal form.<ref>{{harvtxt|Golumbic|Gurvich|2011}}, Theorem 10.1, p.&nbsp;521; {{harvtxt|Golumbic|Mintz|Rotics|2006}}.</ref> That is, when interpreted as a function on sets of vertices of its co-occurrence graph, a read-once function is true for sets of vertices that contain a maximal clique, and false otherwise.
For instance the median function has the same co-occurrence graph as the conjunction of three variables, a [[triangle graph]], but the three-vertex complete subgraph of this graph (the whole graph) forms a subset of a clause only for the conjunction and not for the median.<ref>{{harvtxt|Golumbic|Gurvich|2011}}, Examples {{math|''f''₂}} and {{math|''f''₃}}, p.&nbsp;521.</ref>

Two variables of a positive read-once expression are adjacent in the co-occurrence graph if and only if their [[lowest common ancestor]] in the expression is a conjunction,<ref>{{harvtxt|Golumbic|Gurvich|2011}}, Lemma 10.1, p.&nbsp;529.</ref> so the expression tree can be interpreted as a cotree for the corresponding cograph.<ref>{{harvtxt|Golumbic|Gurvich|2011}}, Remark 10.4, pp.&nbsp;540–541.</ref>