Model checking temporal knowledge and commitments in multi-agent systems using reduction

Though modeling and verifying Multi-Agent Systems (MASs) have long been under study, there are still challenges when many different aspects need to be considered simultaneously. In fact, various frameworks have been carried out for modeling and verifying MASs with respect to knowledge and social commitments independently. However, considering them under the same framework still needs further investigation, particularly from the verification perspective. In this article, we present a new technique for model checking the logic of knowledge and commitments (CTLKC⁺). The proposed technique is fully-automatic and reduction-based in which we transform the problem of model checking CTLKC⁺ into the problem of model checking an existing logic of action called ARCTL. Concretely, we construct a set of transformation rules to formally reduce the CTLKC⁺ model into an ARCTL model and CTLKC⁺ formulae into ARCTL formulae to get benefit from the extended version of NuSMV symbolic model checker of ARCTL. Compared to a recent approach that reduces the problem of model checking CTLKC⁺ to another logic of action called GCTL¹, our technique has better scalability and efficiency. We also analyze the complexity of the proposed model checking technique. The results of this analysis reveal that the complexity of our reduction-based procedure is PSPACE-complete for local concurrent programs with respect to the size of these programs and the length of the formula being checked. From the time perspective, we prove that the complexity of the proposed approach is P-complete with regard to the size of the model and length of the formula, which makes it efficient. Finally, we implement our model checking approach on top of extended NuSMV and report verification results for the verification of the NetBill protocol, taken from business domain, against some desirable properties. The obtained results show the effectiveness of our model checking approach when the system scales up.     

Proving termination of GHC programs

A transformational approach for proving termination of parallel logic programs such as GHC programs is proposed. A transformation from GHC programs to term rewriting systems is developed; it exploits the fact that unifications in GHC-resolution correspond to matchings. The termination of a GHC program for a class of queries is implied by the termination of the resulting rewrite system. This approach facilitates the applicability of a wide range of termination techniques developed for rewrite systems in proving termination of GHC programs. The method consists of three steps: (a) deriving moding information from a given GHC program, (b) transforming the GHC program into a term rewriting system using the moding information, and finally (c) proving termination of the resulting rewrite system. Using this method, the termination of many benchmark GHC programs such as quick-sort, merge-sort, merge, split, fair-split and append, etc., can be proved. This is a revised and extended version of Ref. 12). The work was partially supported by the NSF Indo-US grant INT-9416687 Kapur was partially supported by NSF Grant nos. CCR-8906678 and INT-9014074. M. R. K. Krishna Rao, Ph.D.: He currently works as a senior research fellow at Griffith University, Brisbane, Australia. His current interests are in the areas of logic programming, modular aspects and noncopying implementations of term rewriting, learning logic programs from examples and conuterexamples and dynamics of mental states in rational agent architectures. He received his Ph.D in computer science from Tata Institute of Fundamental Research (TIFR), Bombay in 1993 and worked at TIFR and Max Planck Institut für Informatik, Saarbrücken until January 1997. Deepak Kapur, Ph.D.: He currently works as a professor at the State University of New York at Albany. His research interests are in the areas of automated reasoning, term rewriting, constraint solving, algebraic and geometric reasoning and its applications in computer vision, symbolic computation, formal methods, specification and verification. He obtained his Ph.D. in Computer Science from MIT in 1980. He worked at General Electric Corporate Research and Development until 1987. Prof. Kapur is the editor-in-chief of the Journal of Automated Reasoning. He also serves on the editorial boards of Journal of Logic Programming, Journal on Constraints, and Journal of Applicable Algebra in Engineering, Communication and Computer Science. R. K. Shyamasundar, Ph.D.: He currently works as a professor at Tata Institute of Fundamental Research (TIFR), Bombay. His current intersts are in the areas of logic programming, reactive and real time programming, constraint solving, formal methods, specification and verification. He received his Ph.D in computer science from Indian Institute of Science, Bangalore in 1975 and has been a faculty member at Tata Institute of Fundamental Research since then. He has been a visiting/regular faculty member at Technological University of Eindhoven, University of Utrecht, IBM TJ Watson Research Centre, Pennsylvania State University, University of Illinois at Urbana-Champaign, INRIA and ENSMP, France. He has served on (and chaired) Program Committees of many International Conferences and has been on the Editorial Committees.     

��Ȼ����������ϵͳ�ļ춨��У׼

当前我国管道天然气计量系以体积表示，就其计量器具而言，差压式流量计、容积式流量计和速变式流量计都有，但大流量计量大多仍采用标准孔板差压式流量计，其流量计量标准招待我国SY／T6143－1996《天然气流量的标准孔板计量方法》。文章介绍目前常用的三种流量计的优缺点比较；天然气标准孔板差压式流量计算机自动计量系统的检定，其中包括：标准孔板节流装置，静压、差压变送器、温度传感器、数据采集系统等组件的检定；以及计量器具的正确使用和维护。最后，文章指出目前流量计量的发展主要是二次仪表的发展，籍助应用计算机大大提高流量法的测量范围和准确度，但对用户来说，应选择性／价比合适的仪表，并要考虑所选用仪表要便于检定、维护，同时，计量检定部门则应跟上发展，为广大用户提供技术支持。     

HTR-10燃料元件装卸系统冷态调试

10MW高温气冷实验堆（HTR－10）是一座球床堆，由燃料元件装卸系统实现燃料元件的装卸和循环，且不需要停堆，为保证HTR－10的正常运行，燃料元件装卸系统必须安全，可靠，为此，必须对燃料元件装卸系统进行周密，细致的调试试验和验证，本文介绍了燃料元件装卸系统冷调试的主要调试项目，调试方法和调试结果。     

Safety,liveness and fairness in temporal logic

In this paper we present syntactic characterization of temporal formulas that express various properties of interest in the verification of concurrent programs. Such a characterization helps us in choosing the right techniques for proving correctness with respect to these properties. The properties that we consider include safety properties, liveness properties and fairness properties. We also present algorithms for checking if a given temporal formula expresses any of these properties.This work is partly supported by NSF grant CCR-9212183. A preliminary version of this paper appeared in the Fourth ACM Symposium on Principles of Distributed Computing.     

Formal methods: The next generation of system design tools

Because of the growing demand for increasingly complex computer-based systems there is now an urgent need to provide tools to assist during the design of such systems. Formal specifications and formal methods provide such assistance but their widespread adoption has been hindered by the so-called ‘math fear’ and the perception that the tools are too difficult, too time consuming and too costly to use in a commercial environment. The aim of this article is to dispel the mystery surrounding the topic and to explain what formal methods are, how and why they are used, the benefits that accrue and why the technology should be accepted on a broader front. The application of formal methods to the design of computer-based systems will be discussed without resorting to jargon or mathematics. The discussion will concentrate more on the software content of systems but the arguments apply equally well to hardware. Some of the available tools will also be introduced.     

小型别墅中央空调的新风设计

提出了小型别墅中央空调新风处理的方法，就某别墅采用本方法作中央空调新风设计，并以其计算数据为依据，验证了本方法的可行性。     

X射线机不是计量器具

计量学的基本理论指出，X射线机不具有计量器具的属性。国家的计量法规并未将X射线机定为计量器具。目前存在的JJG 40—2001《X射线探伤机》检定规程，将X射线探伤机与X射线检测技术相互混淆，将X射线探伤机的某些技术性能，说成所谓的X射线探伤机的“计量性能”，不仅违反计量学基本理论，而且也不符合射线检测技术实际。从计量学理论和射线检验实际经验只能得到X射线机不是计量器具的结论。     

Modeling and verifying probabilistic Multi-Agent Systems using knowledge and social commitments

Multi-Agent Systems (MASs) have long been modeled through knowledge and social commitments independently. In this paper, we present a new method that merges the two concepts to model and verify MASs in the presence of uncertainty. To express knowledge and social commitments simultaneously in uncertain settings, we define a new multi-modal logic called Probabilistic Computation Tree Logic of Knowledge and Commitments (PCTL^kc in short) which combines two existing probabilistic logics namely, probabilistic logic of knowledge PCTLK and probabilistic logic of commitments PCTLC. To model stochastic MASs, we present a new version of interpreted systems that captures the probabilistic behavior and accounts for the communication between interacting components. Then, we introduce a new probabilistic model checking procedure to check the compliance of target systems against some desirable properties written in PCTL^kc and report the obtained verification results. Our proposed model checking technique is reduction-based and consists in transforming the problem of model checking PCTL^kc into the problem of model checking a well established logic, namely PCTL. So doing provides us with the privilege of re-using the PRISM model checker to implement the proposed model checking approach. Finally, we demonstrate the effectiveness of our approach by presenting a real case study. This framework can be considered as a step forward towards closing the gap of capturing interactions between knowledge and social commitments in stochastic agent-based systems.     

基于实时UML顺序图的物联网交互模型

物联网是一个集计算、通信和控制于一体的智能系统,它通过监控和收集物理进程信息并将这些信息进行计算和分析,最终生成正确的控制指令用以执行,从而使物理环境变得更加安全和可靠。在物联网中,各物体通过网络连接或者本地连接的方式进行交互,这些交互具有时间性和地域性。物联网的建模和验证是物联网研究中一个重要的领域。文中提出一种基于实时UML顺序图的物联网交互模型,该模型将物联网中所有参与交互的物体建模为交互对象,并且通过实时UML顺序图对交互对象间的交互进行建模。使用时间自动机对交互对象的内部状态变化进行建模,以形成对交互模型的补充。最后根据转换规则将交互模型转换为时间自动机的形式以便于验证。通过一个实例,显示了如何具体应用物联网交互模型。进一步提出了物联网系统应该满足的一些性质,并使用UPPAAL模型检测工具对物联网交互模型进行分析和验证。