Author name cluster

Robert Schrag

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

AAAI Conference 1996 Conference Paper

Compilation for Critically Constrained Knowledge Bases

Robert Schrag

We show that many “critically constrained” Random 3SAT knowledge bases (KBs) can be compiled into disjunctive normal form easily by using a variant of the “Davis-Putnam” proof procedure. From these compiled KBs we can answer all queries about entailment of conjunctive normal formulas, also easily - compared to a “bruteforce” approach to approximate knowledge compilation into unit clauses for the same KBs. We exploit this fact to develop an aggressive hybrid approach which attempts to compile a KB exactly until a given resource limit is reached, then falls back to approximate compilation into unit clauses. The resulting approach handles all of the critically constrained Random 3SAT KBs with average savings of an order of magnitude over the brute-force approach.

PDF Details

AIJ Journal 1996 Journal Article

Implicates and prime implicates in Random 3-SAT

Robert Schrag
James M. Crawford

It has been observed previously that Random 3-SAT exhibits a phase transition at a critical ratio of constraints to variables, where the average frequency of satisfiability falls abruptly from near 1 to near 0. In this paper we look beyond satisfiability to implicates and prime implicates of non-zero length and show experimentally that, for any given length, these exhibit their own phase transitions. All of these phase transitions appear to share the same critical point as the well-known satisfiability phase transition. We also find a rich, regular pattern, in which phase transitions for longer implicates or prime implicates are less steep at a given problem size and all the phase transitions sharpen with increasing problem size. Implicates correspond in a one-to-one way to nogoods, and prime implicates correspond similarly to minimal nogoods. Knowledge about these phase transitions helps us to understand more about the behavior of search algorithms and knowledge compilation approaches in the context of Random 3-SAT.

Details DOI