An inheritance-based technique for building simulation proofs incrementally

Idit Keidar

doi:10.1145/504087.504090

2002-01-01

PRE

Idit Keidar

Roger Khazan

Nancy Lynch

DOI：10.1145/504087.504090

原文链接

原文求助

摘要

En 中文

This paper presents a formal technique for incremental construction of system specifications, algorithm descriptions, and simulation proofs showing that algorithms meet their specifications. The technique for building specifications and algorithms incrementally allows a child specification or algorithm to inherit from its parent by two forms of incremental modification: (a) signature extension, where new actions are added to the parent, and (b) specialization (subtyping), where the child's behavior is a specialization (restriction) of the parent's behavior. The combination of signature extension and specialization provides a powerful and expressive incremental modification mechanism for introducing new types of behavior without overriding behavior of the parent; this mechanism corresponds to the subclassing for extension form of inheritance. In the case when incremental modifications are applied to both a parent specification S and a parent algorithm A, the technique allows a simulation proof showing that the child algorithm A' implements the child specification S' to be constructed incrementally by extending a simulation proof that algorithm A implements specification S. The new proof involves reasoning about the modifications only, without repeating the reasoning done in the original simulation proof. The paper presents the technique mathematically, in terms of automata. The technique has been used to model and verify a complex middleware system; the methodology and results of that experiment are summarized in this paper.

Keyword:

verification

Inheritance by specialization and subclassing for extension

simulation proofs

refinements

incremental proof techniques

proof reuse

AI总结

对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

ACM Transactions on Software Engineering and Methodology

IF:

6.2

论文数:

1.2K

被引数:

3.4K

机构

暂无机构信息

引用论文

STROKE IN PEDIATRIC CARDIAC SURGICAL PATIENTS ON EXTRACORPOREAL MEMBRANE OXYGENATION: AN ANALYSIS OF THE EXTRACORPOREAL LIFE SUPPORT ORGANIZATION DATABASE

Journal of the American College of Cardiology

IF0

2014-04-01

OAAI

David Werho; Sara Pasquali; Sunkyung Yu; Janet Donohue; Gail Annich; Ravi Thiagarajan; Jennifer Hirsch; Michael Gaies

Structural Basis for Blocking Sugar Uptake into the Malaria Parasite Plasmodium falciparum

Cell

IF0

2020-10-01

OAAI

Xin Jiang; Yafei Yuan; Jian Huang; Shuo Zhang; Shuchen Luo; Nan Wang; Debing Pu; Na Zhao; Qingxuan Tang; Kunio Hirata; Xikang Yang; Yaqing Jiao; Tomoyo Sakata-Kato; Jia-Wei Wu; Chuangye Yan; Nobutaka Kato; Hang Yin; Nieng Yan

π-Bonding and tetragonality in dchloro- and dibromo-tetrapyridinecobalt(II) and diacetylacetonatodipyridinecobalt(II)D-氯-和二溴-四吡啶ecobalt(II) 和二乙酰基丙酮二吡啶ecobalt(II) 中的 π-键合和四方性

J. Chem. Soc., Dalton Trans.

IF0

1976-01-01

PREAI

Malcolm Gerloch; Robert F. McMeeking; Anthony M. White

Postcardiotomy Mechanical Circulatory Support in Two Infants with Williams’ Syndrome

Case Reports in Surgery

IF0

2014-01-01

OAAI

Constantinos A. Contrafouris; Andrew C. Chatzis; Meletios A. Kanakis; Prodromos A. Azariadis; Fotios A. Mitropoulos