Dependency Calculus: Reasoning in a General Point Relation Algebra

摘要

Reasoning about complex dependencies between events is a crucial task. However, qualitative reasoning has so far concentrated on spatial and temporal issues. In contrast, we present a new dependency calculus (DC) that is created for specific questions of reasoning about causal relations and consequences. Applications in the field of spatial representation and reasoning are, for instance, modeling traffic networks, ecological systems, medical diagnostics, and Bayesian Networks. Several extensions of the fundamental linear point algebra have been investigated, for instance on trees or on nonlinear structures. DC is an improved generalization that meets all requirements to describe dependencies on networks. We investigate this structure with respect to satisfiability problems, construction problems, tractable subclassses, and embeddings into other relation algebras. Finally, we analyze the associated interval algebra on network structures.