Jump to content

Read-once function

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 21:22, 4 June 2016 (→Characterization: what the function means graph-theoretically). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 appears only once.

More precisely, the expression is required to use only the operations of logical conjunction, logical disjunction, and negation. By applying De Morgan's laws, such an expression can be transformed into one in which negation is used only on individual variables (still with each variable appearing only once). By replacing each negated variable with a new positive variable representing its negation, such a function can be transformed into an equivalent positive read-once Boolean function, represented by a read-once expression without negations.[1]

Examples

For example, for three variables a, b, and c, the expressions

, and

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

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.[2]

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 of the co-occurrence graph forms one of the conjunctions (prime implicants) of the disjunctive normal form.[3] 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.[4] 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,[5] so the expression tree can be interpreted as a cotree for the corresponding cograph.[6]

Another alternative characterization of positive read-once functions combines their disjunctive and conjunctive normal form. 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.[7]

Recognition

It is possible to recognize read-once functions from their disjunctive normal form expressions in polynomial time.[8] 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 truth assignment, using only a quadratic number of function evaluations.[9]

Notes

  1. ^ Golumbic & Gurvich (2011), p. 519.
  2. ^ Golumbic & Gurvich (2011), p. 520.
  3. ^ Golumbic & Gurvich (2011), Theorem 10.1, p. 521; Golumbic, Mintz & Rotics (2006).
  4. ^ Golumbic & Gurvich (2011), Examples f2 and f3, p. 521.
  5. ^ Golumbic & Gurvich (2011), Lemma 10.1, p. 529.
  6. ^ Golumbic & Gurvich (2011), Remark 10.4, pp. 540–541.
  7. ^ Gurvič (1977); Mundici (1989); Karchmer et al. (1993).
  8. ^ Golumbic & Gurvich (2011), Theorem 10.8, p. 541; Golumbic, Mintz & Rotics (2006); Golumbic, Mintz & Rotics (2008).
  9. ^ Golumbic & Gurvich (2011), Theorem 10.9, p. 548; Angluin, Hellerstein & Karpinski (1993).

References

  • Angluin, Dana; Hellerstein, Lisa; Karpinski, Marek (1993), "Learning read-once formulas with queries", Journal of the ACM, 40 (1): 185–210, doi:10.1145/138027.138061, MR 1202143.
  • 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.
  • Golumbic, Martin Charles; 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", Discrete Applied Mathematics, 154 (10): 1465–1477, doi:10.1016/j.dam.2005.09.016, MR 2222833.
  • Golumbic, Martin Charles; Mintz, Aviad; Rotics, Udi (2008), "An improvement on the complexity of factoring read-once Boolean functions", Discrete Applied Mathematics, 156 (10): 1633–1636, doi:10.1016/j.dam.2008.02.011, MR 2432929.
  • Gurvič, V. A. (1977), "Repetition-free Boolean functions", Uspekhi Matematicheskikh Nauk, 32 (1(193)): 183–184, MR 0441560.
  • Karchmer, M.; Linial, N.; Newman, I.; Saks, M.; Wigderson, A. (1993), "Combinatorial characterization of read-once formulae", Discrete Mathematics, 114 (1–3): 275–282, doi:10.1016/0012-365X(93)90372-Z, MR 1217758.
  • Mundici, Daniele (1989), "Functions computed by monotone Boolean formulas with no repeated variables", Theoretical Computer Science, 66 (1): 113–114, doi:10.1016/0304-3975(89)90150-3, MR 1018849.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Read-once_function&oldid=723729058"