Read-once function

<h2 id="examples">Examples</h2>
For example, for three variables a, b, and c, the expressions

a
        ∧
        b
        ∧
        c
      
    
    {\displaystyle a\wedge b\wedge c}

a
        ∧
        (
        b
        ∨
        c
        )
      
    
    {\displaystyle a\wedge (b\vee c)}

(
        a
        ∧
        b
        )
        ∨
        c
      
    
    {\displaystyle (a\wedge b)\vee c}
  
, and

a
        ∨
        b
        ∨
        c
      
    
    {\displaystyle a\vee b\vee c}

are all read-once (as are the other functions obtained by permuting the variables in these expressions). However, the Boolean <a href="/facts/Median_algebra/pyo7wJTj">median</a> operation, given by the expression

(
        a
        ∨
        b
        )
        ∧
        (
        a
        ∨
        c
        )
        ∧
        (
        b
        ∨
        c
        )
      
    
    {\displaystyle (a\vee b)\wedge (a\vee c)\wedge (b\vee c)}

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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="characterization">Characterization</h2>
The <a href="/facts/Disjunctive_normal_form/hsw2pRPu">disjunctive normal form</a> 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 <a href="/facts/Cograph/c3lYz8fV">cograph</a>. More precisely, a positive Boolean function is read-once if and only if its co-occurrence graph is a cograph, and in addition every <a href="/facts/Maximal_clique/XK9ppLz5">maximal clique</a> of the co-occurrence graph forms one of the conjunctions (prime implicants) of the disjunctive normal form.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> 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 <a href="/facts/Triangle_graph/Ws7RAQKN">triangle graph</a>, 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.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
Two variables of a positive read-once expression are adjacent in the co-occurrence graph if and only if their <a href="/facts/Lowest_common_ancestor/lUuLKAGk">lowest common ancestor</a> in the expression is a conjunction,<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> so the expression tree can be interpreted as a cotree for the corresponding cograph.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
Another alternative characterization of positive read-once functions combines their disjunctive and <a href="/facts/Conjunctive_normal_form/B3sY1lTW">conjunctive normal form</a>. A positive function of a given system of variables, that uses all of its variables, is read-once if and only if every prime implicant of the disjunctive normal form and every clause of the conjunctive normal form have exactly one variable in common.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="recognition">Recognition</h2>
It is possible to recognize read-once functions from their disjunctive normal form expressions in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
It is also possible to find a read-once expression for a positive read-once function, given access to the function only through a "black box" that allows its evaluation at any <a href="/facts/Truth_assignment/goPmjjQG">truth assignment</a>, using only a quadratic number of function evaluations.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Dana_Angluin/9aEoCNKK">Angluin, Dana</a>; Hellerstein, Lisa; <a href="/facts/Marek_Karpinski/XPxNRbPA">Karpinski, Marek</a> (1993), "Learning read-once formulas with queries", <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>, 40 (1): 185–210, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.5033">10.1.1.7.5033</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F138027.138061">10.1145/138027.138061</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1202143">1202143</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6671840">6671840</a>.</li>
<li><a href="/facts/Martin_Charles_Golumbic/jjoIMseL">Golumbic, Martin C.</a>; Gurvich, Vladimir (2011), <a href="http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf">"Read-once functions"</a> (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1017%2FCBO9780511852008">10.1017/CBO9780511852008</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-84751-3, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2742439">2742439</a>.</li>
<li><a href="/facts/Martin_Charles_Golumbic/jjoIMseL">Golumbic, Martin Charles</a>; Mintz, Aviad; Rotics, Udi (2006), "Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees", <a href="/facts/Discrete_Applied_Mathematics/0xgV889h">Discrete Applied Mathematics</a>, 154 (10): 1465–1477, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.dam.2005.09.016">10.1016/j.dam.2005.09.016</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2222833">2222833</a>.</li>
<li><a href="/facts/Martin_Charles_Golumbic/jjoIMseL">Golumbic, Martin Charles</a>; Mintz, Aviad; Rotics, Udi (2008), "An improvement on the complexity of factoring read-once Boolean functions", <a href="/facts/Discrete_Applied_Mathematics/0xgV889h">Discrete Applied Mathematics</a>, 156 (10): 1633–1636, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.dam.2008.02.011">10.1016/j.dam.2008.02.011</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2432929">2432929</a>.</li>
<li>Gurvič, V. A. (1977), <a href="https://mi.mathnet.ru/eng/umn3055">"Repetition-free Boolean functions"</a>, <a href="/facts/Russian_Mathematical_Surveys/g3lszK89">Uspekhi Matematicheskikh Nauk</a>, 32 (1(193)): 183–184, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0441560">0441560</a>.</li>
<li>Karchmer, M.; <a href="/facts/Nati_Linial/YDkX3Dyk">Linial, N.</a>; Newman, I.; <a href="/facts/Michael_Saks_(mathematician)/DmMG4Cy1">Saks, M.</a>; <a href="/facts/Avi_Wigderson/CVHaUAdI">Wigderson, A.</a> (1993), "Combinatorial characterization of read-once formulae", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 114 (1–3): 275–282, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2893%2990372-Z">10.1016/0012-365X(93)90372-Z</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1217758">1217758</a>.</li>
<li>Mundici, Daniele (1989), "Functions computed by monotone Boolean formulas with no repeated variables", <a href="/facts/Theoretical_Computer_Science_(journal)/Apbc0PDL">Theoretical Computer Science</a>, 66 (1): 113–114, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0304-3975%2889%2990150-3">10.1016/0304-3975(89)90150-3</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1018849">1018849</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Golumbic & Gurvich (2011), p. 519. - Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439 <a href="http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf" target="_blank">http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Golumbic & Gurvich (2011), p. 520. - Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439 <a href="http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf" target="_blank">http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Golumbic & Gurvich (2011), Theorem 10.1, p. 521; Golumbic, Mintz & Rotics (2006). - Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439 <a href="http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf" target="_blank">http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Golumbic & Gurvich (2011), Examples f2 and f3, p. 521. - Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439 <a href="http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf" target="_blank">http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Golumbic & Gurvich (2011), Lemma 10.1, p. 529. - Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439 <a href="http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf" target="_blank">http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Golumbic & Gurvich (2011), Remark 10.4, pp. 540–541. - Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439 <a href="http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf" target="_blank">http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Gurvič (1977); Mundici (1989); Karchmer et al. (1993). - Gurvič, V. A. (1977), "Repetition-free Boolean functions", Uspekhi Matematicheskikh Nauk, 32 (1(193)): 183–184, MR 0441560 <a href="https://mi.mathnet.ru/eng/umn3055" target="_blank">https://mi.mathnet.ru/eng/umn3055</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Golumbic & Gurvich (2011), Theorem 10.8, p. 541; Golumbic, Mintz & Rotics (2006); Golumbic, Mintz & Rotics (2008). - Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439 <a href="http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf" target="_blank">http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Golumbic & Gurvich (2011), Theorem 10.9, p. 548; Angluin, Hellerstein & Karpinski (1993). - Golumbic, Martin C.; Gurvich, Vladimir (2011), "Read-once functions" (PDF), in Crama, Yves; Hammer, Peter L. (eds.), Boolean functions, Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, pp. 519–560, doi:10.1017/CBO9780511852008, ISBN 978-0-521-84751-3, MR 2742439 <a href="http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf" target="_blank">http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Read-once function open-in-new

Read-once function