Decidability of Parameterized Verification by Roderick Bloem, Swen Jacobs, Ayrat Khalimov

By Roderick Bloem, Swen Jacobs, Ayrat Khalimov

Whereas the vintage version checking challenge is to determine no matter if a finite approach satisfies a specification, the objective of parameterized version checking is to come to a decision, given finite structures M(n) parameterized by means of n in N, even if, for all n in N, the approach M(n) satisfies a specification. during this e-book we give some thought to the $64000 case of M(n) being a concurrent approach, the place the variety of replicated approaches is determined by the parameter n yet every one strategy is autonomous of n. Examples are cache coherence protocols, networks of finite-state brokers, and structures that remedy mutual exclusion or scheduling difficulties. additional examples are abstractions of structures, the place the techniques of the unique platforms really depend upon the parameter.

We literature during this region has studied a wealth of computational types in accordance with quite a few synchronization and verbal exchange primitives, together with token passing, broadcast, and protected transitions. frequently, various terminology is utilized in the literature, and effects are according to implicit assumptions. during this booklet, we introduce a computational version that unites the vital synchronization and communique primitives of many types, and unveils hidden assumptions from the literature. We survey current decidability and undecidability effects, and provides a scientific view of the fundamental difficulties during this fascinating learn quarter.

Show description

Read Online or Download Decidability of Parameterized Verification PDF

Similar design & architecture books

Operational Amplifiers: Theory and Design

Operational Amplifiers – thought and layout, moment version offers a scientific circuit layout of operational amplifiers. Containing cutting-edge fabric in addition to the necessities, the e-book is written to entice either the circuit dressmaker and the process clothier. it's proven that the topology of all operational amplifiers might be divided into 9 major total configurations.

Computer and Information Security Handbook

The second edition of this accomplished guide of desktop and knowledge security provides the main whole view of laptop protection and privateness on hand. It bargains in-depth assurance of safeguard thought, expertise, and perform as they relate to confirmed applied sciences in addition to contemporary advances.

Languages, Design Methods, and Tools for Electronic System Design: Selected Contributions from FDL 2015

This publication brings jointly a variety of the simplest papers from the eighteenth version of the discussion board on specification and layout Languages convention (FDL), which happened on September 14-16, 2015, in Barcelona, Spain. FDL is a well-established overseas discussion board dedicated to dissemination of analysis effects, useful studies and new principles within the program of specification, layout and verification languages to the layout, modeling and verification of built-in circuits, complicated hardware/software embedded structures, and mixed-technology platforms.

Extra info for Decidability of Parameterized Verification

Sample text

E following problem is parameterized by an infinite-state LTS M with initial states I and a quasi-ordering Ä on the states S of M . • e coverability problem: input: finite set of states T S . output: ‘Yes’ if and only if there exist à 2 I and t 2 "T such that à ! t . e following theorem can be easily obtained from the work by Abdulla et al. [1996] and Finkel and Schnoebelen [2001]. 3 e coverability problem is decidable for WSTSs, if the initial state set I satisfies one of the following conditions.

N/ if and only if for all n 2 N , P ˆ . e first undecidability proof that applies to uniform parameterized systems is by Suzuki [1988], for systems consisting of identical processes arranged in a uni-directional ring with a single multi-valued token. e proof reduces non-halting of Turing machines to this problem. A neater exposition by Emerson and Namjoshi [1995] goes via two-counter machines. Informally, a two-counter machine [Minsky, 1967] has a read-only tape, finite control, and two counters, with operations to increment a counter, decrement a counter, test a counter for zero, and change its internal state.

21. A VASS in which jQj D 1 is called a vector-addition system (VAS), which is a notational variant of Petri nets. Conversely, every VASS can be represented as a VAS (since the state component can be coded in jQj many additional coordinates). 28 3. P ; G; F / is decidable also yield a computable reduction to a finite set of finite-state model checking problems. is is formalized as follows. MCf i n ; ˚B /, where 1. Km ; m /g, where each Ki is a d-ary connectivity-graph, each i is a formula, m is a positive integer, and 2.

Download PDF sample

Rated 4.61 of 5 – based on 47 votes