Compositional Verification of Multi-Agent Systems in Temporal Multi-Epistemic Logic

Compositional verification aims at managing the complexity of theverification process by exploiting compositionality of the systemarchitecture. In this paper we explore the use of a temporal epistemiclogic to formalize the process of verification of compositionalmulti-agent systems. The specification of a system, its properties andtheir proofs are of a compositional nature, and are formalized within acompositional temporal logic: Temporal Multi-Epistemic Logic. It isshown that compositional proofs are valid under certain conditions.Moreover, the possibility of incorporating default persistence ofinformation in a system, is explored. A completion operation on aspecific type of temporal theories, temporal completion, is introducedto be able to use classical proof techniques in verification withrespect to non-classical semantics covering default persistence.     

Model Checking Temporal Aspects of Inconsistent Concurrent Systems Based on Paraconsistent Logic

Classical logic cannot be used to effectively reason about concurrent systems with inconsistencies (inconsistencies often occur, especially in the early stage of the development, when large and complex concurrent systems are developed). In this paper, we propose the use of a paraconsistent temporal logic (QCTL) for supporting the verification of temporal properties of such systems even where the consistent model is not available. We introduce a novel notion of paraKripke models, which grasps the paraconsistent character of the entailment relation of QCTL. Furthermore, we explore the methodology of model checking over QCTL, and describe the detailed algorithm of implementing QCTL model checker. In the sequel, a simple example is presented, showing how to exploit the proposed model checking technique to verify the temporal properties of inconsistent concurrent systems.     

基于时序逻辑的加密协议分析

形式化方法由于其精炼,简洁和无二义性,逐步成为分析加密协议的一条可靠和准确的途径,但是加密协议的形式化分析研究目前还不够深入,至今仍没有统一的加密协议验证体系,针对这一现状,该文从加密协议可能面临的最强大的攻击着手,提出了一种基于时序逻辑的加密协议描述方法,在该模型下,对协议行为,入侵者行为,安全需求等特性的描述均用时序逻辑公式表达,从而利用现有的统一的时空逻辑框架分析密码协议的性质,特别地,作者描述和检测了一个系统入侵者不能用任何代数和逻辑的办法获得消息的实例,通过对比,作者认为该方法具有形式化程度较高的特点。     

Model‐Based Visualization of Temporal Abstractions

We describe a new conceptual methodology and related computational architecture called Knowledge‐based Navigation of Abstractions for Visualization and Explanation (KNAVE). KNAVE is a domain‐independent framework specific to the task of interpretation, summarization, visualization, explanation, and interactive exploration, in a context‐sensitive manner, of 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 exploration operators are based on the relations defined in the knowledge‐based temporal‐abstraction problem‐solving method, which is used to abstract the data, and thus can directly use the domain‐specific knowledge base on which that method relies. Thus, the domain‐specific semantics are driving the domain‐independent visualization and exploration processes, and the data are viewed through a filter of domain‐specific knowledge. 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 exploration) the same domain model acquired for abstraction purposes. We focus here on the methodology, but also describe a preliminary evaluation of the KNAVE prototype in a medical domain. Our experiment incorporated seven users, a large medical patient record, and three complex temporal queries, typical of guideline‐based care, that the users were required to answer and/or explore. The results of the preliminary experiment have been encouraging. The new methodology has potentially broad implications for planning, monitoring, explaining, and interactive data mining of time‐oriented data.     

基于时序逻辑的面向实现的协议规范语言

在多种形式化描述语言和时序逻辑原理的研究之上；针对通讯协议的特点提出一个协议模型思想，并设计了实现此模型协议描述语言．本方法的特点是：基于时序逻辑；引入了面向对象的概念，对事件有强的描述能力，让描述更接近于现实；扩展了对事件的描述．能描述事件的随机发生，我们已将之成功地应用于对超文本协议的描述．     

Symmetry and model checking

We show how to exploit symmetry in model checking for concurrent systems containing many identical or isomorphic components. We focus in particular on those composed of many isomorphic processes. In many cases we are able to obtain significant, even exponential, savings in the complexity of model checking.The author's work was supported in part by NSF Grant CCR 941-5496, Semiconductor Research Corporation Contract 95-DP-388, and Texas Advanced Technology Program Grant 003658-250.The author's work was supported in part by NSF Grant CCR-9212183.     

基于状态可达图的离散事件系统时态性质分析

离散事件系统的许多重要性质可用时态逻辑方便，直接和简明地进行描述，系统的性质分析可转化成时态满足关系的判定。基于状态可达图，给出了有限系统时态特征的判定方法。     

基于模态逻辑的通信设备故障诊断系统研究

针对通信设备故障的复杂性、渐变性和知识的不确定性,提出了一个基于模态逻辑的通信设备故障诊断系统。首先,定义一个时态逻辑来预测设备状态,然后用改进的模态逻辑来对通信设备的故障进行知识表示和推理,通过对故障征兆和故障知识库的交互自动地识别出具体的故障,找出具体的维护方法,通过人机接口将结果提供给用户,并利用基于Agent的更新器来更新知识库。最后用一个故障诊断的例子来证明系统的可行性。     

An Interpretation of Default Logic in Minimal Temporal Epistemic Logic

When reasoning about complex domains, where information available is usually only partial, nonmonotonic reasoning can be an important tool. One of the formalisms introduced in this area is Reiter's Default Logic (1980). A characteristic of this formalism is that the applicability of default (inference) rules can only be verified in the future of the reasoning process. We describe an interpretation of default logic in temporal epistemic logic which makes this characteristic explicit. It is shown that this interpretation yields a semantics for default logic based on temporal epistemic models. A comparison between the various semantics for default logic will show the differences and similarities of these approaches and ours.     

反应系统的连续时序逻辑表示和验证

引进一个称为LTLC的连续时间时序逻辑,用来对反应系统进行规范与验证．LTLC的一个重要特点是它能在统一的逻辑框架下表示反应系统及其性质,这样就可将系统与性质问的满足关系转化为逻辑公式间的蕴涵关系．同时,采用非负实数集作为时间域还使我们可以利用标准的存在量词来表示变量隐藏,并可用逻辑蕴涵来表示反应系统间的求精关系．该文首先给出了LTLC的一个简单介绍,然后讨论了如何使用LTLC对反应系统进行表示与推理,最后证明了一个关于LTLC的可判定性结果．此结果可用于有穷状态反应系统的自动验证．     

基于时态逻辑的UML交互模型检测研究

该文详细介绍了统一建模语言和模型检测技术,在此基础上,该文研究了基于交互自动机和时态逻辑的UML交互模型性质检测方法,提出了模型检测所需的Marking算法。该算法通过对交互自动机全部状态的遍历,检测各状态的时态逻辑公式(CTL公式)的真值,以判断用户设计的UML交互模型是否符合计算机软件系统应满足的性质及规范。     

基于动态模糊逻辑(DFL)的一种时序推理模型

在我们的研究领域中 ,普遍存在动态模糊事件 .而当今 ,随着计算机科学技术的发展 ,人们又试图用计算机来模拟这些具有“动态模糊性”的事件 .因此 ,以往有关文献提出了动态模糊逻辑、动态模糊集、基于 DFL的一种学习模型及动态模糊主动数据库系统的设计方法和基本概念 ,这些理论的提出 ,虽然为人们解决具有动态模糊性的问题提供了一定的理论依据 ,但从整个动态模糊系统来看 ,这些工作仅仅是一些初步的工作 ,还有许多工作需要进一步研究 .文中给出的基于 DFL的时序推理模型正是这种工作的一个补充 .     

逻辑分析系统在数字电路测试中的应用

通过对逻辑分析系统基本原理的介绍,阐述了逻辑分析系统测试数字电路的主要方法和技巧。     

Naming Worlds in Modal and Temporal Logic

In this paper we suggest adding to predicate modal and temporal logic a locality predicate W which gives names to worlds (or time points). We also study an equal time predicate D(x, y)which states that two time points are at the same distance from the root. We provide the systems studied with complete axiomatizations and illustrate the expressive power gained for modal logic by simulating other logics. The completeness proofs rely on the fairly intuitive notion of a configuration in order to use a proof technique similar to a Henkin completion mixed with a tableau construction. The main elements of the completeness proofs are given for each case, while purely technical results are grouped in the appendix. This revised version was published online in August 2006 with corrections to the Cover Date.     

Using Program Transformations to Provide Safety Properties for Real-Time Systems

The process of showing that a program satisfies some particular properties with respect to its specification is called program verification. Axiomatic semantics is a verification method that makes assertions describing properties about the states of a program. There exists a transformation from the assertions of a program's verification proof to executable assertions. The latter may be embedded in the program to make it fault tolerant. An axiomatic proof system for concurrent programs is applied to generate executable assertions in a real time distributed environment. A train set example is used as modelproblem.     

基于线性时序逻辑的实时系统建模与求精

线性时序逻辑语言XYZ／E在统一的语义框架下．能表示从高层需求规范到低层实现模型之间的不同抽象层次的系统描述，也适于描述实时系统的模型和逐步求精过程．本文提出了一种基于构件的实时系统求精方法，并给出一个具体实例一电梯控制系统，采用XYZ／E语言描述了该系统的模型及其求精过程．