The semantics of most logics of time and probability is given via a probability distribution over threads , where a thread is a structure specifying what will be true at different points in time (in the future). When assessing the probabilities of statements such as “Event a will occur within 5 units of time of event b ,” there are many different semantics possible, even when assessing the truth of this statement within a single thread. We introduce the syntax of annotated probabilistic temporal (APT) logic programs and axiomatically introduce the key notion of a frequency function (for the first time) to capture different types of intrathread reasoning, and then provide a semantics for intrathread and interthread reasoning in APT logic programs parameterized by such frequency functions. We develop a comprehensive set of complexity results for consistency checking and entailment in APT logic programs, together with sound and complete algorithms to check consistency and entailment. The basic algorithms use linear programming, but we then show how to substantially and correctly reduce the sizes of these linear programs to yield better computational properties. We describe a real world application we are developing using APT logic programs.

Spatial probabilistic temporal (SPOT) databases are a paradigm for reasoning with probabilistic statements about where a vehicle may be now or in the future. They express statements of the form "Object O is in spatial region R at some time t with some probability in the interval [L,U]." Past work on SPOT databases has developed selection operators based on selecting SPOT atoms that are entailed by the SPOT database-we call this "cautious" selection. In this paper, we study several problems. First, we note that the runtime of consistency checking and cautious selection algorithms in past work is influenced greatly by the granularity of the underlying Cartesian space. In this paper, we first introduce the notion of "optimistic" selection, where we are interested in returning all SPOT atoms in a database that are consistent with respect to a query, rather than having an entailment relationship. We then develop an approach to scaling SPOT databases that has three main contributions: 1) We develop methods to eliminate variables from the linear programs used in past work, thus greatly reducing the size of the linear programs used-the resulting advances apply to consistency checking, optimistic selection, and cautious selection. 2) We develop a host of theorems to show how we can prune the search space when we are interested in optimistic selection. 3) We use the above contributions to build an efficient index to execute optimistic selection queries over SPOT databases. Our approach is superior to past work in two major respects: First, it makes fewer assumptions than all past works on this topic except that in. Second, our experiments, which are based on real-world data about ship movements, show that our algorithms are much more efficient than those in.

There are numerous applications where there: is uncertainty over space and time. Examples of such uncertainty arise in vehicle tracking systems where we are not always sure where a vehicle is now (or may be in the future), and cell and satellite phone applications where we are not sure exactly where a phone may be, and so on. In this paper, we propose the concept of a Spatial Probabilistic Temporal (SPOT) database that contains statements of the form "Object O is in spatial region R at some time / with some probability in the interval [L, U]." We define the syntax and a declarative semantics for SPOT databases based on a mix of logic and linear programming, as well as query algebra. We show alternative implementations of some of these query algebra operators when the SPOT database has a disjoint/less property. Though the declarative semantics of SPOT databases is rooted in linear programming, we have found very efficient algorithms that do not use linear programming methods. We report on experiments we have conducted that show that the system scales to large numbers of SPOT atoms, as well as to fairly fine temporal and spatial granularity.