An analysis of the cost of validating semantic composability

Abstract

Validation of semantic composability is a non-trivial problem and a key step in component-based modelling and simulation. Recent work in semantic composability validation promises to reduce verification, validation, and accreditation efforts. However, the underlying cost of current validation approaches can undermine the promised benefits, and the trade-off between validation accuracy and validation cost is not well understood. In this paper we present, to the best of our knowledge, the first quantitative study on the cost of validating semantic composability. Our study covers four representative validation approaches, including two DEVS-based methods, Petty and Weisel formal validation, and deny-validity, and for simplicity, we use computation time as a measure of validation cost. For a queueing model with 1000 components, there is significant trade-off between validation accuracy and cost, with the time-based deny-validity costing seven times that of timeless Petty and Weisel formalism.

Keywords:

• validation
• cost
• composability

Notes

1 We ensured that models with invalid syntax were eliminated using an approach based on compositional grammars expressed in EBNF (Teo and Szabo, 2008).

2 In particular, provided that the transformation from the meta-model to integers is sound, the algorithm to determine mathematical composability could employ a Radix sort algorithm (Knuth, 1997) to first sort the integer values, followed by an inclusion check, resulting in O(kn) steps, where n is the number of elements in the interval, and k is the average element length.

3 However, the validation of component coordination using model checking remains capped to reduce state space explosion.