Negative Boolean constraints

Kim Marriott; Martin Odersky

doi:10.1016/0304-3975(95)00209-X

Negative Boolean constraints

Kim Marriott, Martin Odersky

Department of Human Centred Computing

Research output: Contribution to journal › Article › Research › peer-review

10 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 language	English
Pages (from-to)	365-380
Number of pages	16
Journal	Theoretical Computer Science
Volume	160
Issue number	1-2
DOIs	https://doi.org/10.1016/0304-3975(95)00209-X
Publication status	Published - 10 Jun 1996

Access to Document

10.1016/0304-3975(95)00209-X

Link to publication in Scopus

Cite this

@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 = jun,

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",

}

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

AN - SCOPUS:0030169428

VL - 160

SP - 365

EP - 380

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-2

ER -