EBElazar Birnbaum

Elazar Birnbaum

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Elazar Birnbaum has a total of 1 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The Good Old Davis-Putnam Procedure Helps Counting Models

    by E. Birnbaum, E. L. Lozinskii

    As was shown recently, many important AI problems require counting the number of models of propositional formulas. The problem of counting models of such formulas is, according to present knowledge, computationally intractable in a worst case. Based on the Davis-Putnam procedure, we present an algorithm, CDP, that computes the exact number of models of a propositional CNF or DNF formula F. Let m and n be the number of clauses and variables of F, respectively, and let p denote the probability that a literal l of F occurs in a clause C of F, then the average running time of CDP is shown to be O(nm^d), where d=-1/log(1-p). The practical performance of CDP has been estimated in a series of experiments on a wide variety of CNF formulas.

  • Consistent subsets of inconsistent systems: structure and behaviour

    by Elazar Birnbaum, Eliezer L. Lozinskii

    A large Knowledge System operating for a long time almost inevitably becomes ‘polluted’ by wrong data that make the system inconsistent. Despite this fact, a sizeable part of the system remains unpolluted, and retains useful information. It is widely adopted that a maximally consistent subset of a system (mc-subset) contains a significant portion of unpolluted data. So, determining mc-subsets is a necessary step towards reasoning with inconsistent knowledge. We consider extensions of the MAX-SAT problem, investigate characteristic features of mc-subsets, present algorithms for computing all or major mc-subsets of inconsistent sets of clauses, and, report results of experiments evaluating parameters of mc-subsets.