Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
sav08:polynomial_algorithm_for_horn_clauses [2008/03/12 10:43] vkuncak |
sav08:polynomial_algorithm_for_horn_clauses [2008/03/12 14:10] vkuncak |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Polynomial Algorithm for Horn Clauses ====== | + | ====== Boolean Constraint Propagation and Polynomial Algorithm for Horn Clauses ====== |
| A Horn clause is a clause that has at most one positive literal. | A Horn clause is a clause that has at most one positive literal. | ||
| - | Such clause is either of the form $\{p\}$ where $p \in V$ is a variable, or of the form $\{\lnot p_1, \ldots, \lnot p_n, q$ for $n \ge 1$, that is $p_1 \land \ldots \land p_n \rightarrow q$. | + | Such clause is either of the form $\{p\}$ where $p \in V$ is a variable, or $\{\lnot p\}$ for $p \in V$, or of the form $\{\lnot p_1, \ldots, \lnot p_n, q\}$ for $n \ge 1$, that is $p_1 \land \ldots \land p_n \rightarrow q$. |
| The following algorithm eliminates clauses of the form $\{p\}$, keeping only clauses that have at least one assumption. | The following algorithm eliminates clauses of the form $\{p\}$, keeping only clauses that have at least one assumption. | ||