The European Journal on Artificial Intelligence

In this work we address the problem of representing and reasoning with temporal knowledge in a very general and flexible manner. To this aim we propose a model of integration of quantitative and qualitative temporal information affected by vagueness and uncertainty. We extend our fuzzy qualitative temporal framework IA^fuz integrating the treatment of fuzzy quantitative constraints modeled as trapezoidal distributions. To do this, we extend the treatment of fuzzy temporal constraints considered in the literature and we generalize in a fuzzy direction the classical hybrid approach of temporal constraints integration proposed by Meiri. To show the full expressiveness of the new system, we apply it to represent the fuzzy temporal knowledge in a typical scheduling example.

A main challenge when designing constraint based systems in general and those involving temporal constraints in particular, is the ability to deal with constraints in a dynamic and evolutive environment. That is to check, anytime a new constraint is added, whether a consistent scenario continues to be consistent when a new constraint is added and if not, whether a new scenario satisfying the old and new constraints can be found. We talk then about on line temporal constraint based systems capable of reacting, in an efficient way, to any new external information during the constraint resolution process. In this paper, we will investigate the applicability of systematic versus approximation methods for solving incremental temporal constraint problems. In order to handle both numeric and symbolic constraints, the systematic method is based on constraint propagation performed at both the qualitative and quantitative levels. The approximation methods are respectively based on stochastic local search and genetic algorithms. Experimental evaluation of the performance in time and the quality of the solution returned (number of violated constraints) of the different techniques has been performed on randomly generated temporal constraint problems. The results favour the exact method for problems with reasonable size while the approximation techniques are the methods of choice for very large problems in the case where we want to trade the quality of the solution for the process time. Indeed, while the approximation methods are faster for large problems, they do not guarantee, in general, the completeness of the solution returned.

Dechter et al. [5] proposed solving the Temporal Constraint Satisfaction Problem (TCSP) by modeling it as a meta‐CSP, which is a finite CSP with a unique global constraint. The size of this global constraint is exponential in the number of time points in the original TCSP, and generalized‐arc consistency is equivalent to finding the minimal network of the TCSP, which is NP‐hard. We introduce ▵AC, an efficient consistency algorithm for filtering the meta‐CSP. This algorithm significantly reduces the domains of the variables of the meta‐CSP without guaranteeing arc‐consistency. We use ▵AC as a preprocessing step to solving the meta‐CSP. We show experimentally that it dramatically reduces the size of a meta‐CSP and significantly enhances the performance of search for finding the minimal network of the corresponding TCSP.

Many formalisms for qualitative spatial and temporal reasoning fit into a pattern exemplified by Allen's temporal interval calculus. Constraint‐based reasoning using Allen's calculus can benefit from some of its main properties: (a) the underlying constraint algebra is a relation algebra, in Tarski's sense; (b) testing path‐consistency is a complete method for testing consistency for well‐determined subclasses of relations; (c) atomic path‐consistent networks are consistent and determine unique qualitative configurations; (d) the first order theory associated to the calculus is aleph‐zero categorical. When considering analogous calculi, many of the properties mentioned above no longer hold. The main object of this paper is to examine some of the new questions which arise. In order to do so, we use the idea of weak representations of the algebras as a unifying concept.

We consider Boolean algebras endowed with a contact relation which are abstractions of Boolean algebras of regular closed sets together with Whitehead's connection relation [17], in which two non‐empty regular closed sets are connected if they have a non‐empty intersection. These are standard examples for structures used in qualitative reasoning, mereotopology, and proximity theory. We exhibit various methods how such algebras can be constructed and give several non‐standard examples, the most striking one being a countable model of the Region Connection Calculus in which every proper region has infinitely many holes.

We propose an ontological theory that is powerful enough to describe both complex spatio‐temporal processes and the enduring entities that participate therein. For this purpose we introduce the notion of a directly depicting ontology.

Directly depicting ontologies are based on relatively simple languages and fall into two major categories: ontologies of type SPAN and ontologies of type SNAP. These represent two complementary perspectives on reality and employ distinct though compatible systems of categories. A SNAP (snapshot) ontology comprehends enduring entities such as organisms, geographic features, or qualities as they exist at some given moment of time. A SPAN ontology comprehends perduring entities such as processes and their parts and aggregates as they unfold themselves through some temporal interval. We give an axiomatic account of the theory of directly depicting ontologies and of the core parts of the meta‐ontological fragment within which they are embedded.

In this paper, we elaborate on the fundamental characteristics of ecological ontologies, and draw attention to the importance of space and time in the structure of these ontologies. First, we argue that a key to the specification of eco‐ontologies is the notion of teleological organization grounded in a notion of recursion. Second, we introduce the notion of roles to characterize the generalized and interactive teleological aspects of ecological systems. Third, we also introduce a preliminary set of temporal and spatial concepts intended to represent ecological space and time in the formalization of eco‐ontologies. Fourth, we show how some important epistemological constraints on cognition are fundamentally ecological in nature. This work is informed by Kant's investigations into the foundations of biology, by the hermeneutic investigations of Heidegger and Gadamer, and by mathematical investigations into recursive logic and their application to biology by Spencer‐Brown, Maturana, Varela, and Kauffman.