Negative Boolean constraints

Kim Marriott, Martin Odersky

Research output: Contribution to journalArticleResearchpeer-review

10 Citations (Scopus)


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 languageEnglish
Pages (from-to)365-380
Number of pages16
JournalTheoretical Computer Science
Issue number1-2
Publication statusPublished - 10 Jun 1996

Cite this