A relativistic temporal algebra for efficient design of distributed systems

Adequate methods for checking the specification and design of distributed systems must allow for reasoning about asynchronous activities; efficient methods must perform the reasoning in polynomial time. This paper lays the groundwork for such an efficient deductive system by providing a very general temporal relation algebra that can be used by constraint propagation techniques to perform the required reasoning. Major choices exist when selecting an appropriate temporal model: discrete/dense, linear/nonlinear, and point/interval. James Allen and others have indicated the possible atomic relations between two intervals for the dense-linear-interval model, while Anger, Ladkin, and Rodriguez have shown those needed for a dense-branching-interval model. Rodriguez and Anger further developed a dense-relativistic-interval model based on Lamport'sprecede andcan affect arrows, determining a large number of atomic relations. This paper shows that those same atomic relations are exactly the correct ones for intervals in dense relativistic space-time if intervals are taken as pairs of points (E _s ,E _f ) in space-time such that it is possible to move fromE _s toE _f at less than the speed of light. The relations are defined and named consistently with the earlier work of Rodriguez and Anger, and the relationship between the two models is pursued. The relevance of the results to the verification of distributed specifications and algorithms is discussed.     

Using Constraint Propagation to Reason about Unsynchronized Clocks

Numerous AI problems in planning, robot motion, distributed systems, cooperating agents, and intelligence gathering have domains with sub-collections of events or actions over time which are measured on incomparable or unsynchronized time scales from one to another. In such situations, a temporal model providing only a partial order on time moments is appropriate. Unlike a branching-time model, no sense of a common past and divergent futures occurs; unlike a parallel worlds model, check points or intercommunication between the sub-collections of events may exist, providing a true, rich partially ordered set of temporal information. In applications for which temporal intervals and their relations are appropriate, constraint propagation is a recognized reasoning tool. We discuss several temporal interval models and their relationship to one another but particularly focus on the general partial order model. In each model the emphasis is on the atomic relations, so we amplify on the meaning of atomic and show that what is atomic in one model may not be so in another. Utilizing results established earlier about the lattice properties of the models, the paper describes the closure of the atomic relations under composition and conjunction, relating the structures of relations in linear time, partially ordered time, and relativistic time. Lattice and algebraic isomorphisms explain what appeared to be only coincidental similarities between different models. The results are shown to provide especially efficient representations for constraint propagation algorithms.     

DOMAIN-INDEPENDENT TEMPORAL REASONING WITH RECURRING EVENTS

Numerous examples of temporal reasoning involve a process of abstraction from the number of times an event is to occur or the number of times events stand in a temporal relation. For example, scheduling a recurring event such as one's office hours may consider things like the relative temporal ordering of the office hours and a number of other events in a given work day. The number of times office hours will actually be held may be unknown, even irrelevant, at the time of scheduling them. The objective of this article is to formulate a domain-independent framework for reasoning about recurring events and their relations. To achieve this end, we propose an ontology of recurrence based on the model-theoretic structure underlying collective predication using plural noun phrases. We offer a calculus of binary temporal relations for temporal collections based on a well-defined transformation of interval temporal relations into recurrence relations. Finally, we describe a reasoning framework based on manipulating knowledge stored in temporal relation networks, which is in turn a specialization of the CSP (constraint satisfaction problem) framework. The reasoner manipulates recurrence relations in the network to determine the network's consistency or to generate scenarios.     

不确定时态信息表示的统一模型

时态信息表示和推理是人工智能研究中的一个重要课题,现有的模型大多只能表示确定时态信息,然而现实生活中很多事件的发生结束等时态信息都是不确定的。故提出了一个表示不确定时态信息的统一模型,可用于描述各种具有确定或不确定时态信息的事件。该模型首先定义各类时态对象(如时间点、时间区间)以及它们之间的关系,并给出时态对象间的传递关系表,利用该表能进行时态一致性约束满足问题的求解。最后,给出了两个不确定时态推理的例子,表明了该模型的实际应用意义。     

Similarity of Legal Cases: From Temporal Relations of Affairs

Case-based reasoning has played an important role in legal reasoning systems. As one criteria for similarity of cases, temporal relationsamong affairs in legal cases should be compared. Thus far in many legalreasoning systems, cases have been described as sequences of pointwiseevents, or at best, simple time intervals, and they have been related bypredicates such as before, after, while,and so on. However, such relations may depend on each implementer'spersonal view, and also require much labor to write down by hand. In this paper, we first propose a classification of affair types by their temporal features, and according to those types, we propose several assumption rules that prescribe the temporal relations between affair types. The temporal relations are automatically generated by these rules. Thereafter, we discuss how thesetemporal relations work in the comparison of similarity of cases. Inthe process of comparison, inadequate temporal relations need to beamended. For this purpose, we introduce revision rules, that refute theresults of assumption rules.     

Expressing Time Intervals and Repetition Within a Formalization of Calendars

We investigate a formal representation of time units , calendars , and time unit instances as restricted temporal entities for reasoning about repeated events. We generalize Allen's interval relations to a class level, and based on interval classes we define time units. We examine characteristics of time units, and provide a categorization of the hierarchical relations among them. Hence we define an abstract hierarchical unit structure (a calendar structure ) that expresses specific relations and properties among the units that compose it. Specific objects in the time line are represented based on this formalism, including nonconvex intervals corresponding to repeated events. A goal of this research is to be able to represent and reason efficiently about repetition in time.     

扩展时段时序逻辑的推理机制

该文在扩展时段时序逻辑的基础上提出了一种推理机制，这种推理机制基于时间Petri网模型及基本不等式规则，可由一组已知的扩展时段时序关系推出一些未知的扩展时段时序关系，对不确定时间段内发生的事件及其相互关系具有较好的描述能力，这种推理机制的优势在于定性地对扩展时段之间的时序关系进行推理分析，利用时间Petri网模型，可以对复杂时序逻辑关系进行化简，比单纯利用不等式规则的推理更直观，也更简单，是一种行之有效的方法。     

Temporal Granularity and Indeterminacy in Reasoning About Actions and Change: An Approach Based on the Event Calculus

In many real-world applications, temporal information is often imprecise about the temporal location of events (indeterminacy) and comes at different granularities. Formalisms for reasoning about events and change, such as the Event Calculus (EC) and the Situation Calculus, do not usually provide mechanisms for handling such information, and very little research has been devoted to the goal of extending them with these capabilities. In this paper, we propose TGIC (Temporal Granularity and Indeterminacy event Calculus), an approach based on the EC ontology to represent events with imprecise location and to deal with them on different timelines.     

Representation and Reasoning with Multi-Point Events

Allen's Interval Algebra (IA) and Vilain & Kautz's Point Algebra (PA) consider an interval and a point as basic temporal entities (i.e., events) respectively. However, in many situations we need to deal with recurring events that include multiple points, multiple intervals or combinations of points and intervals. In this paper, we present a framework to model recurring events as multi-point events (MPEs) by extending point algebra. The reasoning tasks are formulated as binary constraint satisfaction problems. We propose a polynomial time algorithm (based on van Beek's algorithm) for finding all feasible relations. For the problem of finding a consistent scenario, we propose a backtracking method with a local search heuristic. We also describe an implementation and a detail empirical evaluation of the proposed algorithms. Our empirical results indicate that the MPE-based approach performs better than the existing approaches.     

Reasoning about networks of temporal relations and its applications to problem solving

An interval algebra (IA) has been proposed as a model for representing and reasoning about qualitative temporal relations between time intervals. Unfortunately, reasoning tasks with IA that involve deciding the satisfiability of the temporal constraints, or providing all the satisfying instances of the temporal constraints, areNP-complete. That is, solving these problems are computationally exponential in the worst case. However, several directions in improving their computational performance are still possible. This paper presents a new backtracking algorithm for finding a solution called consistent scenario. This algorithm has anO(n ³) best-case complexity, compared toO(n ⁴) of previous known backtrack algorithms, wheren denotes the number of intervals. By computational experiments, we tested the performance of different backtrack algorithms on a set of randomly generated networks with the results favoring our proposal. In this paper, we also present a new path consistency algorithm, which has been used for finding approximate solutions towards the minimal labeling networks. The worst-case complexity of the proposed algorithm is stillO(n ³); however, we are able to improve its performance by eliminating the unnecessary duplicate computation as presented in Allen's original algorithm, and by employing a most-constrained first principle, which ensures a faster convergence. The performance of the proposed scheme is evaluated through a large set of experimental data.     

Extending CLIPS to support temporal representation and reasoning

Applications using expert systems for monitoring and control problems often require the ability to represent temporal knowledge and to apply reasoning based on that knowledge. Incorporating temporal representation and reasoning into expert systems leads to two problems in development: dealing with an implied temporal order of events using a non-procedural tool; and maintaining the large number of temporal relations that can occur among facts in the knowledge base. In this paper we explore these problems by using an expert system shell, CLIPS (C Language Integrated Production System), to create temporal relations using common knowledge-based constructs. We also build an extension to CLIPS through a user-defined function which generates the temporal relations from those facts. We use the extension to create and maintain temporal relations in a workflow application that monitors and controls an engineering design change review process. We also propose a solution to ensure truth maintenance among temporally related facts that links our temporal extension to the CLIPS facility for truth maintenance.     

Integrated Temporal Reasoning with Periodic Events

In many areas of Computer Science, including planning, workflows, guidelines, and protocol management, one has to deal with abstract plans, procedures, or schedules involving temporal constraints between classes of actions that have to be repeated at periodic times and may be instantiated in different ways for different executions of the plans (procedures, schedules). In this paper we propose an integrated framework to deal with both qualitative temporal constraints on classes of actions and temporal constraints between instances of actions, in which temporal reasoning is used to amalgamate both types of constraints and to check their consistency. In particular, we consider an expressive formalism to deal with temporal constraints between classes of actions (with special attention to periodic actions) which takes into account different components such as frame times, numeric quantification, periods, and qualitative relations. We define the notions of (contextual) concretization of qualitative temporal constraints between classes and use this notion to formally define the consistency of a knowledge base of temporal constraints between classes and a set of temporal constraints on instances, and to define the algorithm for checking such a consistency. An application for scheduling lessons in a school is shown in an example.     

Relation Algebras and their Application in Temporal and Spatial Reasoning

Qualitative temporal and spatial reasoning is in many cases based on binary relations such as before, after, starts, contains, contact, part of, and others derived from these by relational operators. The calculus of relation algebras is an equational formalism; it tells us which relations must exist, given several basic operations, such as Boolean operations on relations, relational composition and converse. Each equation in the calculus corresponds to a theorem, and, for a situation where there are only finitely many relations, one can construct a composition table which can serve as a look up table for the relations involved. Since the calculus handles relations, no knowledge about the concrete geometrical objects is necessary. In this sense, relational calculus is pointless. Relation algebras were introduced into temporal reasoning by Allen (1983, Communications of the ACM 26(1), 832–843) and into spatial reasoning by Egenhofer and Sharma (1992, Fifth International Symposium on Spatial Data Handling, Charleston, SC). The calculus of relation algebras is also well suited to handle binary constraints as demonstrated e.g. by Ladkin and Maddux (1994, Journal of the ACM 41(3), 435–469). In the present paper I will give an introduction to relation algebras, and an overview of their role in qualitative temporal and spatial reasoning.     

Future Event Prediction Based on Temporal Knowledge Graph Embedding

Accurate prediction of future events brings great benefits and reduces losses for society in many domains, such as civil unrest, pandemics, and crimes. Knowledge graph is a general language for describing and modeling complex systems. Different types of events continually occur, which are often related to historical and concurrent events. In this paper, we formalize the future event prediction as a temporal knowledge graph reasoning problem. Most existing studies either conduct reasoning on static knowledge graphs or assume knowledges graphs of all timestamps are available during the training process. As a result, they cannot effectively reason over temporal knowledge graphs and predict events happening in the future. To address this problem, some recent works learn to infer future events based on historical event-based temporal knowledge graphs. However, these methods do not comprehensively consider the latent patterns and influences behind historical events and concurrent events simultaneously. This paper proposes a new graph representation learning model, namely Recurrent Event Graph ATtention Network (RE-GAT), based on a novel historical and concurrent events attention-aware mechanism by modeling the event knowledge graph sequence recurrently. More specifically, our RE-GAT uses an attention-based historical events embedding module to encode past events, and employs an attention-based concurrent events embedding module to model the associations of events at the same timestamp. A translation-based decoder module and a learning objective are developed to optimize the embeddings of entities and relations. We evaluate our proposed method on four benchmark datasets. Extensive experimental results demonstrate the superiority of our RE-GAT model comparing to various baselines, which proves that our method can more accurately predict what events are going to happen.     

Time representation: A taxonomy of temporal models

The objective of the paper is to provide a taxonomy of temporal systems according to three fundamental considerations: the assumed axiomatic theory, the expressiveness, and the mechanisms for inference which are provided. There is an discussion of the significance of the key features of the taxonomy for computer modelling of temporal events. A review considers the most significant representative systems with respect to these issues, including those due to Bruce, Allen and Hayes, Vilain, McDermott, Dechteret al., Kahn and Gorry, Kowalski and Sergot, Bacchuset al., and Knight and Ma. A tabular comparison of systems is given according to their main structural features. In conclusion, the characteristics of a general axiomatic system capable of representing all the features of these models is discussed.     

命题线性时序逻辑的对偶模型问题的复杂性

定义了一个命题线性时序逻辑的对偶模型的概念.一个公式f的对偶模型是指f的满足以下条件的两个模型(即状态的w序列):在每个位置上这两个模型对原子命题的赋值都是对偶的.然后,对于确定一个公式f是否有对偶模型的判定问题(记为DM)和在一个Kripke-结构中确定是否存在从两个给定状态出发的对偶模型满足给定公式f的判定问题(记为KDM)的复杂性进行了研究.证明了以下结果:对于只含有F("Future")算子的命题线性时序逻辑,DM和KDM都是NP完全的;而对于以下命题线性时序逻辑,DM和KDM都是PSPACE完全的:含有F,X ("Next")算子的逻辑、含有U("Until")算子的逻辑、含有U,S,X算子的逻辑以及由Wolper给出的含有正规语言算子的逻辑(一般称为扩展时序逻辑,简称ETL).     

FS-Net: Frequency Statistical Network for Temporal Knowledge Graph Reasoning

Temporal Knowledge Graph (TKG) reasoning has attracted wide attention of researchers. Existing TKG reasoning methods have made great progress through modeling historical information. However, the time variability and unseen entities (relations) are still two major challenges that hinder the further improvement of this field. Moreover, since the structural information and temporal dependencies of the historical subgraph sequence have to be modeled, the traditional embedding-based methods often have high time consumption in the training and predicting processes, which greatly limits the application of the reasoning model in real-world scenarios. To address these issues, in this paper we propose a frequency statistical network for TKG reasoning, namely FS-Net. On the one hand, FS-Net continuously generates time-varying scores for the predictions at the changing timestamps based on the latest short-term historical fact frequency statistics; on the other hand, based on the fact frequency statistics at the current timestamp, FS-Net supplements the historical unseen entities (relations) for the predictions; in particular, FS-Net does not need training and has a very high time efficiency. Plenty of experiments on two TKG benchmark datasets demonstrate that FS-Net outperforms the baseline models.     

Topological Spatio–Temporal Reasoning and Representation

We present here a theory of motion from a topological point of view, in a symbolic perspective. Taking space–time histories of objects as primitive entities, we introduce temporal and topological relations on the thus defined space–time to characterize classes of spatial changes. The theory thus accounts for qualitative spatial information, dealing with underspecified, symbolic information when accurate data are not available or unnecessary. We show that these structures give a basis for commonsense spatio–temporal reasoning by presenting a number of significant deductions in the theory. This can serve as a formal basis for languages describing motion events in a qualitative way.