Negative Boolean constraints

Kim Marriott, Martin Odersky

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

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

Cite this

Marriott, Kim ; Odersky, Martin. / Negative Boolean constraints. In: Theoretical Computer Science. 1996 ; Vol. 160, No. 1-2. pp. 365-380.
@article{8434c61f5a404fd09aa3f8cf39aa3010,
title = "Negative Boolean constraints",
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.",
author = "Kim Marriott and Martin Odersky",
year = "1996",
month = "6",
day = "10",
doi = "10.1016/0304-3975(95)00209-X",
language = "English",
volume = "160",
pages = "365--380",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-2",

}

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 journalArticleResearchpeer-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 -