We provide an efficient method for consistency checking of temporal relations in the Point Algebra (PA-relations) extended by binary disjunctions of PA-relations. Such disjunctions add a great deal of expressive power, including the ability to stipulate disjointness of temporal intervals, which is important in planning applications. The method is basede on two main steps: the first preprocesses the initial set of disjunctions reducing it to a logically equivalent subset, while the second performs a search which uses a form of selective backtracking and a "forward propagation" technique to greatly enhance efficiency. The preprocessing phase is worst-case polynomial, and in principle is strong enough ti subsume consistency checking for Nebel and Bürckert's ORD-Horn class of interval relations. Experimental results using a specialized algorithm for binary disjunctions of inequalities show that our method is very efficient especially when the number of disjunctions is limited relative to the number of PA-relations, and that although consistency testing is NP-complete, in practice our algorithms tend to perform polynomially

An Efficient Method for Managing Disjunctions in Qualitative Temporal Reasoning

1994-01-01

Abstract

We provide an efficient method for consistency checking of temporal relations in the Point Algebra (PA-relations) extended by binary disjunctions of PA-relations. Such disjunctions add a great deal of expressive power, including the ability to stipulate disjointness of temporal intervals, which is important in planning applications. The method is basede on two main steps: the first preprocesses the initial set of disjunctions reducing it to a logically equivalent subset, while the second performs a search which uses a form of selective backtracking and a "forward propagation" technique to greatly enhance efficiency. The preprocessing phase is worst-case polynomial, and in principle is strong enough ti subsume consistency checking for Nebel and Bürckert's ORD-Horn class of interval relations. Experimental results using a specialized algorithm for binary disjunctions of inequalities show that our method is very efficient especially when the number of disjunctions is limited relative to the number of PA-relations, and that although consistency testing is NP-complete, in practice our algorithms tend to perform polynomially
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11582/1007
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact