Verification of Sequential and Concurrent Programs by Krzysztof R. Apt

By Krzysztof R. Apt

Computer courses are an essential a part of the various structures we depend upon in our day-by-day lives, and the right kind functioning and security of those structures is of paramount significance. the advance of tools that verify software correctness is accordingly a key problem for machine scientists.

This largely expected 3rd variation of Verification of Sequential and Concurrent Programs presents a scientific exploration of 1 of the most typical methods to application verification, often called the "assertional" process. Following the winning formulation of earlier variants, this technique is utilized to deterministic and nondeterministic sequential courses of various complexity, including either parallel and dispensed concurrent courses. The elevated content material of this thorough re-creation additionally contains insurance of the verification of object-oriented courses. for every classification of courses, the authors introduce an operational semantics and evidence structures for the verification of partial and overall correctness, justified officially in corresponding soundness theorems. Case reviews provided in the course of the ebook show using the facts structures to officially be sure strategies to classical difficulties, resembling sorting, manipulation of lists, producer/consumer and mutual exclusion.

Topics and Features:

  • Includes an intensive introductory part, familiarizing the reader with the elemental suggestions and notation utilized in the ebook, in addition to the book’s structure
  • Explains Hoare’s method of application verification for while courses, supplying a correctness facts of a application for partitioning an array (NEW)
  • Concludes every one bankruptcy with routines and bibliographic feedback for extra reading
  • Discusses recursive courses that stretch deterministic courses through parameterless strategies and systems with the call-by-value parameter mechanism, and offers a correctness facts of the quicksort software (NEW)
  • Explores nondeterministic and allotted courses, proposing a verification approach to allotted courses in line with a change into nondeterministic ones
  • Presents object-oriented courses, with a spotlight at the major features of items (NEW)
  • Investigates parallel courses with shared variables and with synchronization
  • Studies the problem of equity within the framework of nondeterministic courses, utilizing an procedure in accordance with the strategy of specific schedulers
  • Includes a Foreword via Professor Amir Pnueli

This glossy replace of a vintage, reader-friendly textbook is ideal for an introductory direction on software verification for complicated undergraduate or graduate scholars, and should even be used as an creation to operational semantics. Outlines for attainable classes are steered within the Preface to the publication. This e-book is exclusive in addressing assertional verification of all crucial periods of significant courses: while courses, recursive courses, object-oriented courses, nondeterministic courses, parallel courses, and allotted programs.

Show description

Read Online or Download Verification of Sequential and Concurrent Programs PDF

Similar algorithms and data structures books

Introduction To Algorithms. Solutions. Instructors.Manual

The up-to-date new version of the vintage advent to Algorithms is meant essentially to be used in undergraduate or graduate classes in algorithms or information constructions. just like the first variation, this article is additionally used for self-study by way of technical pros because it discusses engineering concerns in set of rules layout in addition to the mathematical points.

Algorithms of informatics, vol.2.. applications (2007)(ISBN 9638759623)

Ivanyi A. (ed. ) Algorithms of informatics, vol. 2. . functions (2007)(ISBN 9638759623)

Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications

Real-time structures play a vital function in our society, aiding numerous vital program parts, resembling nuclear and chemical plant regulate, flight regulate structures, site visitors regulate in airports, harbors, and educate stations, telecommunication structures, business automation, robotics, protective army platforms, area missions, and so forth.

Additional info for Verification of Sequential and Concurrent Programs

Example text

21 29 32 38 39 41 42 47 50 51 N THIS CHAPTER we explain the basic concepts and notations used throughout this book. We recommend to the reader to move now to Chapter 3 and consult the individual sections of this chapter whenever needed. This chapter is organized as follows. 1, we list the standard mathematical notation for sets, tuples, relations, functions, sequences, strings, proofs, induction and grammars. 2 is needed to understand the syntax of the programs studied in this book.

By definition, R0 = {(a, a) | a ∈ A}. Since R∗ is reflexive, R0 ⊆ R∗ follows. • Induction step. Using the proof format explained earlier, we argue as follows: Rn+1 = {definition of Rn+1 } Rn ◦ R ⊆ {induction hypothesis, definition of ◦} R∗ ◦ R ⊆ {definition of R∗ } R∗ ◦ R∗ ⊆ {transitivity of R∗ } R . ∗ Thus Rn+1 ⊆ R∗ . ⊓ ⊔ The induction principle for natural numbers is based on the fact that the natural numbers can be constructed by beginning with the number 0 and repeatedly adding 1. By allowing more general construction methods, one obtains the principle of structural induction, enabling the use of more than one case at the induction basis and at the induction step.

Bibliographic Remarks . . . . . . . . . . . . . . . . 21 29 32 38 39 41 42 47 50 51 N THIS CHAPTER we explain the basic concepts and notations used throughout this book. We recommend to the reader to move now to Chapter 3 and consult the individual sections of this chapter whenever needed. This chapter is organized as follows. 1, we list the standard mathematical notation for sets, tuples, relations, functions, sequences, strings, proofs, induction and grammars.

Download PDF sample

Rated 4.85 of 5 – based on 19 votes