Read-once function: Difference between revisions

Revision as of 00:54, 18 May 2016

Latest revision as of 10:13, 28 August 2024

(7 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Special type of Boolean function}}

In mathematics, a '''read-once function''' is a special type of [[Boolean function]] that can be described by a [[Boolean expression]] in which each [[Variable (mathematics)|variable]] appears only once.

Line 10 ⟶ 11:

:<math>a\vee b\vee c</math>

are all read-once (as are the other functions obtained by permuting the variables in these expressions). However, the Boolean [[Median algebra|median]] operation, given by the expression

:<math>(a\vee b)\wedge (a\vee c)\wedge (b\wedgevee c)</math>

is not read-once: this formula has more than one copy of each variable, and there is no equivalent formula that uses each variable only once.<ref>{{harvtxt|Golumbic|Gurvich|2011}}, p.&nbsp;520.</ref>

==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>

Line 39 ⟶ 41:

| title = Learning read-once formulas with queries

| volume = 40

| year = 1993| citeseerx = 10.1.1.7.5033 | s2cid = 6671840 }}.

*{{citation

| last1 = Golumbic | first1 = Martin C. | author1-link = Martin Charles Golumbic

Line 67 ⟶ 69:

| title = Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial {{mvar|k}}-trees

| volume = 154

| year = 2006}}.| doi-access = free

}}.

*{{citation

| last1 = Golumbic | first1 = Martin Charles | author1-link = Martin Charles Golumbic

Line 79 ⟶ 82:

| title = An improvement on the complexity of factoring read-once Boolean functions

| volume = 156

| year = 2008}}.| doi-access = free

}}.

*{{citation

| last = Gurvič | first = V. A.

| issue = 1(193)

| journal = Uspehi[[Russian MatematičeskihMathematical Surveys|Uspekhi Matematicheskikh Nauk]]

| mr = 0441560

| pages = 183–184

Line 97 ⟶ 101:

| last5 = Wigderson | first5 = A. | author5-link = Avi Wigderson

| doi = 10.1016/0012-365X(93)90372-Z

| issue = 1-31–3

| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]

| mr = 1217758

Line 103 ⟶ 107:

| title = Combinatorial characterization of read-once formulae

| volume = 114

| year = 1993}}.| doi-access = free

}}.

*{{citation

| last = Mundici | first = Daniele

Line 113 ⟶ 118:

| title = Functions computed by monotone Boolean formulas with no repeated variables

| volume = 66

| year = 1989}}.| doi-access = free

}}.

{{refend}}