Third International Workshop on Temporal Representation and Reasoning
A Recursive Temporal Algebra and Temporal Completeness
Mehmet A. Orgun
Department of Computing
Macquarie University
Sydney, NSW 2109, Australia
mehmet@mpce.mq.edu.au
http://www-comp.mpce.mq.edu.au/~mehmet
This paper introduces a recursive temporal algebra based on temporal semantics for querying time-varying data. The algebra, called \R{}, is based on a temporal relational data model in which a temporal database is modeled as a collection of time-varying relations. Each time-varying relation is a collection of ordinary relations indexed by moments in time. In \R{}, recursive queries (such as the transitive closure of a given relation) can be formulated through equations. It is shown that other forms of recursion, such as linear recursion, can also be expressed using iteration through time. Temporal completeness of \R{} is established, with respect to two other temporal algebras based on temporal semantics which offer linear recursive operators.
Reasoning with Sequences of Point Events
R. Wetprasit and A. Sattar
School of Comp. and Infor. Tech.
Griffith University
Nathan, Brisbane, 4111
AUSTRALIA
L. Khatib
Computer Science Program
Florida Institute of Technology
150 W. University Blvd.,
Melbourne, Fl. 32901, USA
We propose to model recurring events as multi-point events by extending Vilain and Kautz's point algebra. We then propose an exact algorithm (based on van Beek's exact algorithm) for finding feasible relations for multi-point event networks. The complexity of our method is compared with previously known results both for recurring and non-recurring events. We identify the special cases for which our multi-point based algorithm can find exact solution. Finally, we summarise our paper with brief discussion on ongoing and future research.
(A full version of this paper will appear in Proceedings of Canadian AI Conference 1996 (CSCSI-96)).
Using Temporal Logics for Planning and Control
Fahiem Bacchus
Department of Computer Science University of Waterloo
Waterloo, Ontario, Canada, N2L 3G1
Traditionally, planning work in Artificial Intelligence has focused on primitive actions and instantaneous states. Innovative work has been done on composing primitive actions so as to bring about desired final states. The thesis being advanced here is that instead of simply focusing on primitive actions, it is also useful to use representation and reasoning tools whose primitive objects are sequences of actions (or the associated sequences of states that they generate). Temporal logics are a useful tool for representing and reasoning about action sequences. In work over the past two years I and my colleagues have examined some different applications of temporal logics to problems of planning and control.
An Integrity Constraint Checking Method for Temporal Deductive Databases
C. Martin, J. Sistac
Universitat Politecnica de Catalunya.
Departament de Llenguatges i Sistemes Informatics.
Pau Gargallo, 5.
08028 Barcelona-Catalonia
e-mail: {martin/sistac}@lsi.upc.es
We propose a method for integrity checking in the context of temporal deductive databases. A temporal deductive database is a deductive database that suppports some aspect of time, in our case valid time, in which valid time is the time when the fact is true in the modelled reality. Our method augments a database with a set of transition and event rules, which explicitly define the insertions and deletions by database update. Standard SLDNF resolution can then be used to check satisfaction of integrity constraints. A temporal deductive database has to be consistent, that is, after performing an update the database must satisfy its set of integrity constraints. Using our method the temporal deductive database always is consistent because if a retroactive or proactive update violated some integrity constraint the update would be rejected.
Reasoning about Concurrent Actions within Features and Fluents
Choong-ho Yi
Department of Computer Science
University of Karlstad
S-651 88 Karlstad, Sweden
Choong-ho.Yi@hks.se
Sandewall proposed a systematic assessment method for temporal logics. In favour of the assessment of logics, we have introduced concurrency into his framework. The resulting formalism is capable of reasoning about interdependent as well as independent concurrent actions. We have then applied the entailment criteria PCM and PCMF to selecting intended models of common sense theories where concurrent actions are allowed, and proved that the criteria lead to only intended models for respective subsets of such theories.
A Theory of Time and Temporal Incidence based on Instants and Periods
Eddie Schwalb and Lluis Vila
Dept. of Information and Computer Science
University of California, Irvine.
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 throughout time. There are some problematic issues such as the expression of instantaneous events and instantaneous holding of fluents, the specification of the properties for the temporal holding of fluents and the Dividing Instant Problem.
This paper presents a theory of time and temporal incidence which is more natural than its predecessors and satisfactorily addresses the issues above. Our theory of time, called IP, is based on having instants and periods at equal level. We define a theory of temporal incidence upon it whose main original feature is the distinction between continuous and discrete fluents.
Characterizing temporal repetition,
Diana Cukierman and James Delgrande.
This paper is a preliminary investigation of temporal repetition. We review work in Artificial Intelligence of both formal and practical systems that deal with repetitive temporal objects (i.e. repetitive points and/or intervals). We analyze the essence of repetition, and present an extensive classification of types of repetition.
Temporal Knowledge Representation and Organization for Case-Based Reasoning.
I. Bichindaritz and E. Conlon
LIAP-5, UFR de Math-Informatique Universite Rene Descartes - Paris 5
45 rue des Saints-Peres
75006 Paris, France
This article presents the temporal knowledge representation and its organization in a case-based reasoning system called MNAOMIA. The general case-based reasoning methodology is grounded on a model of reasoning such that memory, learning and reasoning are inseparable. This particular focus forces pertinent knowledge representation and organization in the system memory. The main aspects of the temporal dimension of knowledge representation and organization of MNAOMIA are detailed in this paper, such as: the temporal representation language for the cases, the automatic learning of trends from the cases during the reasoning process, and the organization of the memory in generalization-based hierarchies of trends under which the cases are indexed.
Hybrid Temporal Reasoning for Planning and Scheduling
Silvana Badaloni
Dept. of Electronics and Computer Science
University of Padova
Via Gradenigo 6A
35100 Padova - Italy
tel +39+49 8295754
fax +39+49 8277699
email badaloni@ladseb.pd.cnr.it
Marina Berati
CSELT
Via Reiss Romoli 274
10148 Torino - Italy
tel +39+11 2286758
email berati@sun2.ladseb.pd.cnr.it
This paper address the problem of representing heterogeneous temporal information in a uniform framework. Metric information relative to intervals is combined with qualitative information in a homogeneous representation based on a temporal constraint network. We illustrate the properties of the new sub-algebra (called IDSA), the algorithms used to propagate temporal information and their complexity.
GUIDING AND REFINING SIMULATION USING TEMPORAL LOGIC
Giorgio Brajnik
Dip. di Matematica e Informatica
Universita' di Udine
33100 Udine, ITALY
giorgio@dimi.uniud.it
Daniel J. Clancy
Department of Computer Sciences
University of Texas at Austin
Austin, TEXAS 78712
clancy@cs.utexas.edu
We illustrate TeQSIM, a qualitative simulator for continuous dynamical systems. It combines the expressive power of qualitative differential equations with temporal logic by interleaving simulation with model checking to constrain and refine the resulting predicted behaviors. Temporal logic expressions are used to specify constraints that restrict the simulation to a region of the state space and to specify trajectories for input variables. A propositional linear-time temporal logic is adopted, which is extended to a three valued logic that allows a formula to be conditionally entailed when quantitative information specified in the formula can be applied to a behavior to refine it. We present a formalization of the logic with theoretical results concerning the adopted model checking algorithm (correctness and completeness). We show also an example of the simulation of a non-autonomous dynamical system and illustrate possible application tasks, ranging from simulation to monitoring and control of continuous dynamical systems, where TeQSIM can be applied.
A Topological Transition Based Logic for the Qualitative Motion of Objects
Denis Gagne
Alex Informatique
1930 rue Gagnon
Lachine, Que, Canada H8T 3M6
Andre Trudel
Jodrey School of Computer Science
Acadia University
Wolfville, NS, Canada B0P 1X0
We present a spatio-temporal ontology suitable for representing and reasoning about the qualitative motion of rigid bodies. This simple ontology provides a uniform treatment of motion in one, two, and three dimensional space. A succinct axiomatization is provided capturing the ontology. This first order logic is based on the transition of topological relations between objects.
Representing Interaction of Agents at Different Time Granularities(*)
Edjard Mota & David Robertson
Department of Artificial Intelligence
The University of Edinburgh
80 South Bridge, Edinburgh EH1 1HN Scotland
edjardm,dr@aisb.ed.ac.uk
In this paper we describe NatureTime logic which we use to represent and reason about the behaviour of interacting agents (in an ecological domain), which behave at different time granularities. Although the traditional application fields of temporal representation and reasoning still raise many interesting theoretical issues, we have been investigating some practical problems of ecological systems which suit different representations of time than those embodied in traditional simulation models of ecosystems. These seem well suited to reconstruction using temporal logic programs.
(*) This work and the first author (on leave for PhD from the Department of Computer Science of the University of Amazonas, Manaus, Brazil) are sponsored by the Brazilian Ministry of Education, grant n.o 01723/93-8/CAPES.
Handling Temporal Relations in Scheduling Dialogues for An MT System
Rocio Guillén, David Farwell, Janyce Wiebe
Computing Research Laboratory,
and Computer Science Department,
New Mexico State University,
Box 3CRL, Las Cruces, NM 88003
Handling temporal information has been a main concern of areas such as natural language processing, planning, and knowledge representation. In scheduling dialogues, i.e., dialogues whose goal is setting up a meeting in this paper, temporal reference is central, and the relations between temporal expressions contain much of the ellipsis and anaphora to be resolved. As a consequence, filling in missing information contributes to the understanding of the text. In this paper, we first identify the various binary relations present in this kind of dialogue, characterize them, and, finally, present a mechanism for processing with temporal relations that is based on using the constraints found during the analysis.
TIME ACCOUNTABILITY FOR LATTICE COMPUTERS
Mario R. Sanchez
High Performance Database Research Center
School of Computer Science
Florida International University
Miami, Florida
msanch03@fiu.edu
Anil M. Shende
Department of Mathematics, Computer Science & Physics
Roanoke College
Salem, Virginia
shende@abdabs.roanoke.edu
Computers that emulate reality must be bound by the same often inexplicable contentious concepts that we take for granted while producing meaningful results. We present three important aspects of time that are required by such emulating computers, the lattice computer, in order to accurately and effectively simulate motion of objects in real space. We first provide a mechanical overview of the lattice computer so as to afford an understanding of our methods and the associated time related issues. We apply a universal clock theory to lattice computers so as to synchronize message passing between processors. A linearly proportional correlation between the time element of motion in the lattice computer and that of an object in real space is described. Lastly, we define the means by which the lattice computer can account for the time continuum in order to accurately emulate factors inherent to motion in real space.
Irrelevance in Uncertain Temporal Reasoning
Ahmed Y. Tawfik and Eric M. Neufeld
Department of Computer Science
University of Saskatchewan
Saskatoon, Saskatchewan S7N 5A9,
Canada
{tawfik,eric}@cs.usask.ca
In the presence of uncertainty, relevance of information degenerates as time evolves. This work shows that this degeneration occurs in probabilistic temporal reasoning. A mechanism for analyzing this phenomenon uses a Markov chain representation and a degree of relevance measure called temporal extraneousness.
Efficiency of probabilistic temporal reasoning can be improved by ignoring irrelevant and weakly relevant information. The analysis introduced here allows us to identify the portion of event history affecting the time instant of interest. The duration of relevant history depends on the dynamic nature of the system and the chosen relevance threshold. These notions are used to prune time-sliced Bayesian networks which constitute a popular probabilistic temporal reasoning knwolege representation.
Managing Time Granularity of Narrative Clinical Information: The Temporal Data model TIME-NESIS
Carlo Combi (!), Francesco Pinciroli (!*) and Giuseppe Pozzi (^)
! Dipartimento di Bioingegneria del Politecnico di Milano
* Centro di Teoria dei Sistemi del CNR, Milano
^ Dipartimento di Elettronica e Informazione, Politecnico di Milano
p.zza Leonardo Da Vinci 32
20133 Milano - ITALY
email {combi, pincirol, pozzi}@elet.polimi.it
In the database field, the need of time management at different levels of granularity has been on for some years. It has been recently emphasized. Such a need is widespread when we have to manage medical clinical information. The temporal dimension is normally given at different granularities. In database systems based on the calendar time, granularity refers to uncertainty in specifying a temporal dimension as well as to use of different time-units. Thus, we need to set up modelling concepts and managing tools by which to establish temporal relationships between temporal clinical data. To manage the temporal dimension of data given at various and mixed levels of granularity, we defined the temporal data model TIME-NESIS (TIME in anamNESIS). The model provides temporal dimension to the data by using intervals that can be specified by different granularities. The model supports a three-valued logic, where True, False and Undefined are the truth values.
Engineering Time in Medical Knowledge-Based Systems through Time-Axes and Time-Objects
E.T.Keravnou
Department of Computer Science
University of Cyprus
Kallipoleos 75, P.O.Box 537
CY-1678 Nicosia
Cyprus
elpida@turing.cs.ucy.ac.cy
Starting from the premise that time representation and temporal reasoning must constitute integral aspects of a competent, knowledge-based, medical system, the paper presents the relevant requirements and discusses their realisation in terms of a generic temporal kernel to be embedded in such a system. The kernel has a layered architecture where the bottom layer gives the ontological primitives and their associated axioms, and the higher layers implement the required temporal reasoning. The principal primitives of the ontology are the time-axis and the time-object.
Temporal Representation for Multimedia Systems
Minglu Li; Yongqiang Sun; Huanye Sheng.
Dept. of Computer Science and Engineering
Shanghai Jiao Tong University
1954 Huashan Road
Shanghai, 200030, P.R.China
As multimedia systems integrate a variety of temporally related media objects, synchronization is an important issue in those systems. First, the question 'Which out of all possible temporal relations might be needed for multimedia?' is examined. Then, a brief overview of an interval-based indeterministic synchronization model presented by Wahl and Rothermel, called Wahl-Rothermel Synchronization Model(WRSM), is given. Next, the authors enhance the WRSM, and propose a new Generalized Synchronization Model(GSM), which has fewer, more powerful interval operators. It is followed by a formal description of a new Multimedia Synchronization Description Language(MSDL), which is based on the GSM, and as a preferred approach to specify multimedia systems. Additionally, how the MSDL can be used to describe a large number of present and future multimedia systems is demonstrated. (18 Refs.)
Dynamic Temporal Interpretation Contexts for Temporal Abstraction
Yuval Shahar
Section on Medical Informatics,
Medical School Office Building (MSOB) x215
Stanford University, Stanford, CA 94305 USA
shahar@camis.stanford.edu
The temporal-abstraction task is the task of abstracting higher-level concepts from time-stamped data in a context-sensitive manner. We have developed and implemented a formal knowledge-based framework for decomposing and solving that task that supports acquisition, maintenance, reuse, and sharing of temporal-abstraction knowledge.
We present the logical model underlying the representation and runtime formation of interpretation contexts. Interpretation contexts are relevant for abstraction of time-oriented data and are induced by input data, concluded abstractions, external events, goals of the temporal-abstraction process, and certain combinations of interpretation contexts. Knowledge about interpretation contexts is represented as a context ontology and as a dynamic induction relation over interpretation contexts and other proposition types. Induced interpretation contexts are either basic, composite, generalized, or nonconvex.
We discuss the advantages of separating explicitly interpretation-context propositions from the propositions inducing them and from the abstractions created within them.
First Order Modal Temporal Logics with Generalized Intervals
Ge'rard Becher
GREYC- CNRS URA 1526
University of Caen F-14032 Caen Cedex
becher@info.unicaen.fr
Following the work of G.~Ligozat who described the interval algebras A(S) whose elements are relations on generalized intervals, we propose a class of first order modal temporal logics where the possible worlds are points, standard intervals or unions of convex intervals and where the accessibility relations are elements of A(S). These logics have standard syntax and semantics with the unique exception that, whereas predicates are generally interpreted on intervals, the terms are always interpreted on points which are considered as elements of the intervals. We address also the problem of automated reasoning in such logics and define for that sake a satisfiability and validity preserving translation function into a standard two-sorted first order logic.
Temporal Reasoning in a Meta Constraint Logic Programming Architecture
Evelina Lamma(1), Michela Milano(1), Paola Mello(2)
(1) DEIS Universit\`a di Bologna Bologna 40136, Italy
elamma@deis.unibo.it
(2) Istituto di Ingegneria Universit\`a di Ferrara Ferrara 41100, Italy
Constraint Logic Programming (CLP) is a powerful programming paradigm combining the advantages of Logic Programming and the efficiency of constraint solving. However, CLP presents some limitations in dealing with temporal reasoning. First, it uses an ``arc consistency'' propagation algorithm which cannot be changed by the user and it is too weak in many temporal frameworks. Second, CLP is not able to deal with qualitative temporal constraints.
In this paper, we show how to overcome these limitations. In particular, we present a way of performing a path-consistency check without changing the propagation algorithm of the constraint solver. In addition, we show how to integrate qualitative and quantitative temporal reasoning by using a two module meta CLP architecture. Each module is a finite domain constraint solver (CLP(FD)). The object system (extended with the path- consistency algorithm) performs quantitative reasoning, while the meta-level reasons on constraints of the underlying system thus performing qualitative reasoning.
In this way, we can benefit of the efficiency of the constraint handling mechanism of CLP and the modularity, flexibility and scalability of meta- architectures.
A General Framework and Reasoning Models for Time Granularity
Claudio Bettini
Dept. of Information Science (DSI),
University of Milan, via Comelico, 39, Milan, 20135, ITALY.
bettini@dsi.unimi.it
X. Sean Wang and Sushil Jajodia
Dept. of Information & Software Systems Engineering,
George Mason University,
Fairfax,VA 22030.
{xywang,jajodia}@isse.gmu.edu
This paper presents a general framework to define time granularity systems. We identify the main choices differentiating the systems and investigate the formal relationships among granularities in these systems. The paper also introduces the notion of a network of temporal constraints with granularities emphasizing the semantical and computational differences from constraint networks with a single granularity. Consistency is shown to be NP-hard and an approximate algorithm proposed.
Time in a Causal Theory
A=EFcha MOKHTARI
Institut d'Informatique
USTHB
BP 32 El Alia Alger Alg=E9rie
mokhtari@ist.ibp.dz
Daniel KAYSER
LIPN URA 1507 du CNRS
Institut Galil=E9e Universit=E9 Paris-= Nord
93430 Villetaneuse France
Daniel.Kayser@ura1507.univ-paris13.fr
This paper discusses the temporal aspect of a causal theory based on an "interventionist" conception of causality, i.e. a preference to select causes among a set of actions which an agent has the ability to perform or not to perform (free will). Casting causal reasoning in this framework leads to explore the problem of reasoning about actions, generally considered as a nonmonotonic temporal reasoning. Most of the works on nonmonotonic temporal reasoning have used simple temporal ontologies, such as situation calculus, or temporal logic with discrete time. The theory presented in this paper also has a simple temporal ontology based on "time points" organized on branching "time lines", with the possibility of modelling continuous evolutions of the world for various futures (prediction) or pasts (diagnostic).
Combining Simultaneous Values and Temporal Data Dependencies
Avigdor Gal
Department of Computer Science
University of Toronto
Toronto
Ontario, M5S 3H5 CANADA
Dov Dori
Information Systems Engineering Department
Faculty of Industrial Engineering and Management
Technion - Israel Institute of Technology
Haifa, 32000, Israel
In temporal databases there are situations where multiple values of the same data item have overlapping validity times. In addition to the common case of multi-valued properties, there are several possible semantics to multiple values with overlapping validity times of the same data item. We refer to such data items as having {\it simultaneous values}. This paper presents a polynomial algorithm for efficient handling of simultaneous values in a database with temporal data dependencies, integrity rules that define relationships among values of different data items in a temporal database. The algorithm is demonstrated using a case study from the game theory area. An implementation of the algorithm is integrated in a prototype of a temporal active database.
Temporal Resolution: A Breadth-First Search Approach
Clare Dixon
Department of Computing
Manchester Metropolitan University
Manchester M1~5GD
United Kingdom
C.Dixon@doc.mmu.ac.uk
An approach to applying clausal resolution, a proof method for classical logics suited to mechanisation, to temporal logics has been developed by Fisher. The method involves translation to a normal form, classical style resolution within states and temporal resolution between states. The method consists of only one temporal resolution rule and is therefore particularly suitable as the basis of an automated temporal resolution theorem prover.
As the application of this temporal resolution rule is the most costly part of the method, involving search amongst graphs, it is on this area we focus. A breadth-first search approach to the application of this rule is presented and shown to be correct. Analysis of its operation is carried out and test results for its comparison to a previously developed depth-first style algorithm given.