Abstract | ||
---|---|---|
Verification of parameterized systems for an arbitrary number of instances is generally undecidable. Existing approaches resort to non-trivial restrictions on the system or lack automation. In practice, applications can often provide a suitable bound on the parameter size. We propose a new technique toward the bounded formulation of parameterized reasoning: how to efficiently verify properties of a family of systems over a large finite parameter range. We show how to accomplish this with a single verification run on a model that aggregates the individual instances. Such a run takes significantly less time than if the systems were considered one by one. Our method is applicable to a completely inhomogeneous family of systems, where properties may not even be preserved across instances. In this case the method exposes the parameter values for which the verification fails. If symmetry is present in the systems, it is inherited by the aggregate representation, allowing for verification over a reduced model. Our technique is fully automatic and requires no approximation. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/11901433_6 | ICFEM |
Keywords | Field | DocType |
inhomogeneous family,parameter value,large finite parameter range,model checking,parameter size,parameterized system,single verification,aggregate representation,parameterized reasoning,reduced model,new technique | Kripke structure,Parameterized complexity,Model checking,Computer science,Algorithm,Automation,Temporal logic,Formal methods,Bounded function,Undecidable problem | Conference |
Volume | ISSN | ISBN |
4260 | 0302-9743 | 3-540-47460-9 |
Citations | PageRank | References |
7 | 0.58 | 23 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
e allen emerson | 1 | 7683 | 1183.13 |
Richard J. Trefler | 2 | 222 | 14.59 |
Thomas Wahl | 3 | 103 | 10.21 |