Recent work in knowledge compilation suggests that relations which can be described precisely by either Horn theories or tree constraint networks are identifiable in output polynomial time. Algorithms for computing approximations using these languages were also proposed. Upon testing such approximations on artificially generated and real life data, it was immediately observed that they yield numerous superfluous models. As a result, although certain entailment queries can be answered reliably, these methods may be ineffective for a large class of membership queries.

To improve the approximation quality, we investigate here the k-decomposition problem, that is, determining whether a relation can be described by a disjunction of k tractable theories. The paper discusses the complexity of this task, outlines several algorithms for computing both exact and approximate k-decompositions, and evaluates the potential of this approach empirically. We focus on the class of tree constraint networks and Horn theories and report results on artificially generated relations and on three real life cases. Our experiments show that for uniform random relations, the quality of upper bound approximations improves as k increases. However, when we require very high accuracy, decomposition is not effective since k grows linearly with the size of the data. When the data comes from a near-tractable source, the approach is useful. Experiments show that for the King Rook King problem the generalizing power of such methods is comparable to that of recently developed learning algorithms.

Path-consistency algorithms, which are polynomial for discrete problems, are exponential when applied to problems involving quantitative temporal information. The source of complexity stems from specifying relationships between pairs of time points as disjunction of intervals. We propose a polynomial algorithm, called ULT, that approximates path-consistency in Temporal Constraint Satisfaction Problems (TCSPs). We compare ULT empirically to path-consistency and directional path-consistency algorithms. When used as a preprocessing to backtracking, ULT is shown to be 10 times more effective then either DPC or PC-2.

In this work we combine logic programming and temporal constraint processing techniques. We propose TCLP, which augments logic programs in Temporal Constraint Networks are applied. We identify a decidable fragment called, Simple TCLP, which can be viewed as extending Datalog with limited functions to accomodate intervals of occurrence and temporal constraints between them. Some of the restrictions introduced by Simple TCLP are overcome by a syntactic structure which provides with the benefits of reification. The latter allows quantification on temporal occurrences and relation symbols.

Time is fundamental in representing and reasoning about changing domains. A proper temporal representation requires characterizing two notions: (1) time itself, and (2) temporal incidence, i.e. the domain-independent properties for the truth-value of fluents and events through-out time. Formally defining them involves some problematic issues such as (i) the expression of instantaneous events and instantaneous holding of fluents, (ii) the dividing instant problem and (iii) the formalization of the properties for non-instantaneous holding of fluents.

This paper discusses how previous attempts fail to address all these issues and presents a simple theory of time and temporal incidence which satisfactorily overcomes all of them.

Our theory of time, called IP, is based on having instants and periods at equal level. Our theory of temporal incidence is defined upon IP. Its key insight is the distinction between continuous and discrete fluents.

We propose a propositional language for temporal reasoning that is computationally effective yet expressive enough to describe information about fluents, events and temporal constraints. Although the complete inference algorithm is exponential, we characterize a tractable core with limited expressibility and inferential power. Our results render a variety of constraint propagation techniques applicable for reasoning with constraints on fluents.