Constraint Satisfaction on Infinite Domains: Compactness and Other Properties
Jinbo Huang (NICTA)
NICTA SEMINARDATE: 2012-05-18
TIME: 12:00:00 - 13:00:00
LOCATION: NICTA - 7 London Circuit
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
Constraint satisfaction on infinite domains is widely used to model problems in qualitative spatial and temporal reasoning, and is also used to enhance the expressivity of description logics. In both cases, the domain, plus the relations defined thereon, is a relational structure whose properties play a key role in the decidability and tractability of the reasoning problems. This talk presents several new results regarding some of these properties including compactness, which is defined to hold if any infinite set of constraints (over the given domain and relations) is satisfiable whenever all its finite subsets are satisfiable. Specifically, I will present a sufficient condition for compactness, and a consequence of compactness in the form of a necessary and sufficient condition for another important property known as patchwork. I will then discuss implications of these general results for concrete problems in qualitative spatial and temporal reasoning.
