Arrow Research search

Author name cluster

Daher Kaiss

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

Possible papers

2

LPAR Conference 2006 Conference Paper

Boolean Rings for Intersection-Based Satisfiability

  • Nachum Dershowitz
  • Jieh Hsiang
  • Guan-Shieng Huang
  • Daher Kaiss

Abstract A potential advantage of using a Boolean-ring formalism for propositional formulæ is the large measure of simplification it facilitates. We propose a combined linear and binomial representation for Boolean-ring polynomials with which one can easily apply Gaussian elimination and Horn-clause methods to advantage. We demonstrate that this framework, with its enhanced simplification, is especially amenable to intersection-based learning, as in recursive learning and the method of Stålmarck. Experiments support the idea that problem variables can be eliminated and search trees can be shrunk by incorporating learning in the form of Boolean-ring saturation.

Details

SAT Conference 2004 Conference Paper

Boolean Ring Satisfiability

  • Nachum Dershowitz
  • Jieh Hsiang
  • Guan-Shieng Huang
  • Daher Kaiss

We propose a method for testing satisfiability based on Boolean rings. It makes heavy use of simplification, but avoids the potential size increase associated with application of the distributive law by employing a combined linear and binomial representation. Several complexity results suggest why the method may be relatively effective in many cases. The framework is also amenable to learning from intersections, as in Stålmarck’s method. Some experiments have been undertaken.

Details