Content deleted Content added
Citation bot (talk | contribs) m Alter: issue. Add: citeseerx. Formatted dashes. | You can use this bot yourself. Report bugs here. | User-activated. |
Added short description Tags: Mobile edit Mobile app edit Android app edit App suggested edit App description add |
||
| (4 intermediate revisions by 3 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\
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. 520.</ref>
Line 40 ⟶ 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 68 ⟶ 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
}}.
*{{citation
| last1 = Golumbic | first1 = Martin Charles | author1-link = Martin Charles Golumbic
Line 80 ⟶ 82:
| title = An improvement on the complexity of factoring read-once Boolean functions
| volume = 156
| year = 2008
}}.
*{{citation
| last = Gurvič | first = V. A.
Line 104 ⟶ 107:
| title = Combinatorial characterization of read-once formulae
| volume = 114
| year = 1993
}}.
*{{citation
| last = Mundici | first = Daniele
Line 114 ⟶ 118:
| title = Functions computed by monotone Boolean formulas with no repeated variables
| volume = 66
| year = 1989
}}.
{{refend}}
| |||