Zeitschriftenartikel:
E. De Panafieu, D. Gardy, B. Gittenberger, M. Kuba:
"2-XOR revisited: satisfiability and probabilities of functions";
Algorithmica,
76
(2016),
4;
S. 1035
- 1076.
Kurzfassung englisch:
The problem 2-Xor-Sat asks for the probability that a random expression, built as a conjunction of clauses x⊕y , is satisfiable. We revisit this classical problem by giving an alternative, explicit expression of this probability. We then consider a refinement of it, namely the probability that a random expression computes a specific Boolean function. The answers to both problems involve a description of 2-Xor expressions as multigraphs and use classical methods of analytic combinatorics by expressing probabilities through coefficients of generating functions.
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.