Abstract
Systems of Boolean constraints which allow negative constraints such as f ⊈ g are investigated. The results form a basis for algorithms to determine satisfiability, validity, implication, equivalence and variable elimination for such systems. These algorithms have applications in spatial query decomposition, machine reasoning and constraint logic programming. Proofs of the results rely on independence of inequations, which enables results for systems with a single inequation to be lifted to systems with many inequations.
| Original language | English |
|---|---|
| Pages (from-to) | 365-380 |
| Number of pages | 16 |
| Journal | Theoretical Computer Science |
| Volume | 160 |
| Issue number | 1-2 |
| DOIs | |
| Publication status | Published - 10 Jun 1996 |
Cite this
}
Negative Boolean constraints. / Marriott, Kim; Odersky, Martin.
In: Theoretical Computer Science, Vol. 160, No. 1-2, 10.06.1996, p. 365-380.Research output: Contribution to journal › Article › Research › peer-review
TY - JOUR
T1 - Negative Boolean constraints
AU - Marriott, Kim
AU - Odersky, Martin
PY - 1996/6/10
Y1 - 1996/6/10
N2 - Systems of Boolean constraints which allow negative constraints such as f ⊈ g are investigated. The results form a basis for algorithms to determine satisfiability, validity, implication, equivalence and variable elimination for such systems. These algorithms have applications in spatial query decomposition, machine reasoning and constraint logic programming. Proofs of the results rely on independence of inequations, which enables results for systems with a single inequation to be lifted to systems with many inequations.
AB - Systems of Boolean constraints which allow negative constraints such as f ⊈ g are investigated. The results form a basis for algorithms to determine satisfiability, validity, implication, equivalence and variable elimination for such systems. These algorithms have applications in spatial query decomposition, machine reasoning and constraint logic programming. Proofs of the results rely on independence of inequations, which enables results for systems with a single inequation to be lifted to systems with many inequations.
UR - http://www.scopus.com/inward/record.url?scp=0030169428&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(95)00209-X
DO - 10.1016/0304-3975(95)00209-X
M3 - Article
VL - 160
SP - 365
EP - 380
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
IS - 1-2
ER -