Title: A Model for Time Granularity in Natural Language

Author(s): Gerard Becher, Françoise Clérin-Debart, Patrice Enjalbert

E-mail(s): {becher, debart, patrice}@info.unicaen.fr

Abstract: We propose here a model for dealing with time granularity in natural language. In contrast with many other fields where granularity levels are essentially quantitative, in natural language we are confronted with a more subtle and qualitative kind of granularity where the different levels are not always precisely defined. Our model for representing such phenomena is based on time units and intervals. Time units are considered as indivisible chunks of time and correspond in many aspects to the usual notion of temporal points with the difference that the former are durative whereas the latter represent traditionally instantaneous events. Relations between time units and/or intervals are exhaustively studied and a relation algebra is defined which extends the traditional algebra on points and intervals. In particular, a containment relation is introduced in order to express changes in granularity. A logic with restricted quantifiers is proposed for formalizing temporal knowledge and some examples are discussed which show the relevance of the model for natural language.

Top Of Abstracts Page

Title: Uncertain Temporal Reasoning for the Distributed Transportai on Scheduling Problem

Author(s): Maroua Bouzid and Abdel-Illah Mouaddib

E-mail(s): (bouzid,mouaddib)@cril.univ-artois.f

Abstract: Distributed Artificial Intelligence (DAI) is suitable to applications where there is no central control. One of these applications with which we are concerned is Transportation Scheduling. We noticed that all the approaches dedicated to this application use a weak representation of time and a simple reasoning. Furthermore, these approaches ignore the uncertainty behavior of agents. What we propose is an approach based on Fuzzy Temporal Characteristic Functions (FTCF) which allow a powerful representation of agent companies behaviors making us informed at each time on the degree that the agent is available. Thinks to this representation, we develop a temporal reasoning allowing a cooperation inter and intra companies to allocate trucks and delegate orders.

Top Of Abstracts Page

Title: Event Calculus with Explicit Quantifiers

Author(s): (1) Iliano Cervesato, (2) Massimo Franceschet, (3) Angelo Montanari

E-mail(s): (1) University of Stanford, CA (iliano@cs.stanford.edu), (2) Universita' di Torino, Italy (franzesc@dimi.uniud.it), (3) Universita' di Udine, Italy (montana@dimi.uniud.it)

Abstract: Kowalski and Sergot's Event Calculus (EC) is a simple temp oral formalism that, given a set of event occurrences, derives the maximal validity intervals (MVIs) over which properties initiated or terminated by these events hold. We extend the range of queries accepted by EC, so far limited to boolean combinations of MVI verification or computation requests, to admit arbitrary quantification over events and properties. We demonstrate the added expressive power by encoding a medical diagnosis problem as a case study. Moreover, we give an implementation of the resulting formalism and analyze the computational complexity of the extended calculus.

Top Of Abstracts Page

Title: Accounting for temporal evolutions in highly reactive decision-making

Author(s): Silvia Coradeschi and Thierry Vidal

E-mail(s): silco@ida.liu.se, thierry@enit.fr

Abstract: In the application domain of aircraft combat simulation, one needs to merge dynamic supervision and real-time decision-making: actions and observations interact in a reactive and continuous way, and delays between them must be accounted for. We start from a decision-tree model, which provides strong context handling capabilities, but only statically match a decision to the current state of the world. To get a more dynamical view of what happens, we improve this model by matching temporal chronicles, i.e. time-constrained possible scenarios, to the context. The classical situation assessment technique in this framework only allows to match a decision to the complete recognition of a chronicle, whereas our highly reactive application domain requires anticipated decision-making, comparing possible evolutions to take the best decision in real-time. We hence dynamically compute a timed game automaton synthesizing from the chronicles the predicted possible next steps, and propose an algorithm that deduces from this simple controller model the best decision to make.

Top Of Abstracts Page

Title: The Set of Support Strategy in Temporal Resolution

Author(s): Clare Dixon and Michael Fisher

E-mail(s): C,Dixon@doc.mmu.ac.uk, M.Fisher@doc.mmu.ac.uk

Abstract: A variety of proof methods have been developed to support the effective mechanisation of temporal logic. While clausal temporal resolution has been successfully employed for a range of problems, a number of improvements are still required. In particular, as there is no consistent control strategy underlying the method, a large amount of irrelevant information may sometimes be generated.

Following on from classical resolution, where the Set of Support strategy has been used very successfully, we here introduce, justify and apply a temporal version of this strategy, thus allowing the supporting set to be carried over between the different phases of the resolution method. This not only restricts the production of irrelevant information but, under certain conditions, retains the completeness of the refutation process.

Top Of Abstracts Page

Title: Tackling the Qualification Problem using Fluent Dependency Constraints: Preliminary Report

Author(s): P. Doherty and J. Kvarnström???

E-mail(s): patdo@ida.liu.se, jonkv@ida.liu.se

Abstract: The use of causal rules or fluent dependency constraints have proven to provide a versatile means of dealing with the ramification problem. In this paper we show how fluent dependency constraints together with the use of durational fluents can be used to deal with problems associated with action qualification. We provide both a weak and strong form of qualification and demonstrate the approach using an action scenario which combines solutions to the frame, ramification and qualification problems in the context of actions with duration, concurrent actions, non-deterministic actions and the use of both boolean and non-boolean fluents. The circumscription policy used for the combined problems is reducible to the 1st-order case. In addition, we demonstrate the use of a research tool VITAL, for querying and visualizing action scenarios.

Top Of Abstracts Page

Title: Quantitative Structural Temporal Constraints on Repeating Events

Author(s): Robert A. Morris and Lina Khatib

E-mail(s): morris@cs.fit.edu and lina@cs.fit.edu

Abstract: This paper presents a model of the temporal structure of repeating events. This model allows for the specification of constraints dealing with the part-whole structure of these events. The temporal structure of repeating events is viewed as being composed of six aspects: sub-interval number, gap number, sub-interval duration, gap duration, period and extent. A set of constraints involving these aspects collectively specifies the conditions under which repeating events can be assigned times, and thus partially formalizes a solution to the scheduling problem for repeating events. The consistency and tightness of a set of such constraints can be tested by identifying determinacy relationships among the different aspects. These relationships can also be used to infer constraints about one structural aspect from others.

This paper also introduces a new category of quantitative temporal constraints involving repeating events which specifies that the duration or period of events be distributed randomly over a set of values. The proposed model is motivated by a real scheduling problem involving repeating events.

Top Of Abstracts Page

Title: Model-Based Abstraction of Temporal Visualizations

Authors: Yuval Shahar and Cleve Cheng

E-mails: shahar@smi.stanford.edu; cleve@cs.stanford.edu

Abstract: We describe a domain-independent framework (KNAVE) specific to the task of interpretation, summarization, visualization, explanation, and interactive navigation in a context-sensitive manner through time-oriented raw data and the multiple levels of higher-level, interval-based concepts that can be abstracted from these data. The KNAVE domain-independent navigation operators access the domain-specific knowledge base, which is modeled by the formal ontology of the knowledge-based temporal-abstraction method; the method generates the temporal abstractions from the time-oriented database. Thus, domain-specific knowledge underlies the semantics of the domain-independent visualization and navigation processes. By accessing the domain-specific temporal-abstraction knowledge base and the domain-specific time-oriented database, the KNAVE modules enable users to query for domain-specific temporal abstractions and to change the focus of the visualization, thus reusing for a different task (visualization and navigation) the domain model that has been acquired from the domain experts for the purpose of temporal abstraction. Initial evaluation of the KNAVE prototype has been encouraging. The KNAVE methodology has potentially broad implications for tasks such as planning, monitoring, explanation, and data mining.

Selected Areas: Temporal logics and ontologies; Temporal databases; human-computer interfaces; Data mining

Top Of Abstracts Page

Title: Extended Message Sequence Charts With Time-Interval Semantics

Author(s): Paulo S. Muniz Silva

E-mail(s): psmuniz@pcs.usp.br

Abstract: The paper describes the main ideas of an extension of Message Sequence Charts (MSCs) in a time-interval structure to improve the temporal knowledge of the environment where a software system will be built. The extended MSC could be used at the requirements analysis phase and its interpretation is not limited to the analysis of real-time software systems (where MSCs are mostly used), but rather is aimed for helping the qualitative temporal analysis of the application domain, whatever the software solution for the system. The paper briefly overviews MSCs, describes the goals of the proposed interpretation for basic MSCs (MSCs without branching or loop), and defines their syntax and semantics.

Top Of Abstracts Page

Title: Generating Instantiations of Contextual Scenarios of Periodic Events

Author: Paolo Terenziani

E-mail: terenz@di.unito.it

Abstract: In this paper, we consider an expressive formalism to deal with temporal constraints between periodic events which takes into account different components such as frame times, numeric quantification, periods, and qualitative temporal constraints. We define the notions of (contextual) concretization of a temporal constraint and of (contextual) scenario of a KB of temporal constraints. We then use these notions in order to introduce an algorithm which generates an instantiation of events which satisfies a scenario.

Top Of Abstracts Page

Title:Qualitative and Quantitative Temporal Reasoning with Points and Durations

Authors: Rattana Wetprasit and Abdul Sattar

E-mail: R.Wetprasit@cit.gu.edu.au

Abstract: This paper extends the point duration network (PDN) to represent both qualitative and quantitative information about point events. An algorithm to solve reasoning tasks such as finding a consistent scenario with minimal domains is briefly described. We also propose further extension to capture quantitative information about durations.

Top Of Abstracts Page

Title: An Approach to Model and Query Event-Based Temporal Data

Author(s): Elisa Bertino, Elena Ferrari,Giovanna Guerrini

E-mail(s): {bertino,ferrarie}@dsi.unimi.it, guerrini@disi.unige.it

Abstract: Temporal database systems support all functions related to the management of large amounts of constantly changing data. However, current temporal database systems support a flat view of the history of data changes, in that all the changes are considered equally relevant and are, therefore, all stored in the database. However, many applications, such as monitoring and planning applications, call for more flexibility. Monitoring applications, in particular, may require that the temporal history of a data item is stored only whenever a certain event occurs. For other applications the history of data changes may be less important than the event causing the changes. In this paper we propose an event-based temporal object model which allows to keep track of selected values within the temporal history of a data object attribute. The portions, within the temporal history of a data object, which are actually stored into the database are identified by relating them to events. In the paper, besides defining the data model, we investigate the problem of querying a database with incomplete temporal information.

Top Of Abstracts Page

Title: Ockhamistic Logics and True Futures of Counterfactual Moments

Author(s): Torben Brauner, Per Hasle and Peter Xhrstrxm

E-mail(s): torbenb@hum.auc.dk, Phasle@cfk.hum.aau.dk and poe@hum.auc.dk

Abstract: In this paper various Ockhamistic logics are compared with the aim of making clear the role of true futures of counterfactual moments, that is, true futures of moments outside the true chronicle. First we give an account of Prior's original Ockhamistic semantics where truth of a formula is relative to a moment and a chronicle. We prove that this is equivalent to a semantics put forward by Thomason and Gupta where truth is relative to a moment and a so-called chronicle function which assigns a chronicle to each moment. This is the case because true futures of counterfactual moments do not matter in Thomason and Gupta's semantics. Later we discuss how two options considered by Belnap and Green might be formalised. They come about by assuming either a chronicle or a chronicle function to be given once and for all. The first of the two options is unable to give an account of certain statements from natural language and the second option invalidates an intuitively valid formula. We propose a new Ockhamistic semantics where the formula in question is valid, and furthermore, where true futures of counterfactual moments are taken into account. Finally, we discuss possible applications within Artificial Intelligence.

Top Of Abstracts Page

Title: Representing and Learning Temporal Relationships among Experimental Variabl es

Author(s): Vanathi Gopalakrishnan and Bruce G. Buchanan Intelligent Systems Lab, Department of Computer Science University of Pittsburgh, Pittsburgh PA

E-mail(s): {vanathi@cs.pitt.edu, buchanan@cs.pitt.edu}

Abstract: We describe the necessity to capture temporal information in scientific experiment design for analysis by machine learning algorithms that can learn useful temporal patterns among experimental variables. We have identified three types of temporal information, namely, duration, rate of change, and sequence of application of laboratory operators that are useful to learn from experimental data. Our motivation stems from study of experiment design in the domain of macromolecular crystallography. In this preliminary paper, we identify the challenges posed by both, the domain as well as the types of temporal information, on machine learning programs. We then outline our method of temporal specialization for inducing temporal patterns, and illustrate with an example from the domain.

Top Of Abstracts Page

Title: A Visualization Method of Time Expressions Using Starting/Ending Point Plan e

Author(s): Mitsunori Matsushita, Masakatsu Ohta, and Toshiyuki Iida

E-mail(s): mat@cslab.kecl.ntt.co.jp

Abstract: We propose a method that visualizes the time transitions in written time expressions in order to analyze how the author used them. The method represents time expressions as points on a plane and connects them with lines. We apply the method to an adventure story and a company's history story and discovered two characteristics: First, during the progression of the text, the durations implied by the time expressions change from long to short. Second, at the start of a new paragraph, expressions tend to refer to events or periods of longer duration again.

Top Of Abstracts Page

Title: Time, Communication and Synchronisation in an Agent-Based Programming Language

Author(s): Rafael Ramirez

E-mail(s): rafael@iscs.nus.sg

Abstract: In this paper, we describe an approach to the representation, specification and implementation of multi-agent real-time systems. The approach is based on the notion of concurrent object-oriented systems where processes are represented as objects. As argued in the past, this is a highly suitable base for extension to distributed AI and multi-agent application platforms. In our approach, the behaviour of an agent (its safety properties and time requirements) is declaratively stated as a set of temporal constraints among events which provides great advantages in writing multi-agent systems and manipulating them while preserving correctness. The temporal constraints have a procedural interpretation that allows them to be executed, also concurrently. In this way, the specification of an agent behaviour is directly executed, thus eliminating the need to verify that the implementation satisfies its specification. The approach also provides a framework in which algorithms for a variety of concurrent programming paradigms may be expressed, compared and manipulated.

Top Of Abstracts Page