Interface Simulation Distances Conference Paper


Author(s): Cerný, Pavol; Chmelík, Martin; Henzinger, Thomas A; Radhakrishna, Arjun
Title: Interface Simulation Distances
Affiliation IST Austria
Abstract: The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a quantitative measure for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intu- itively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, and that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies.
Conference Title: GandALF: Games, Automata, Logic, and Formal Verification
Conference Dates: September 6-8, 2012
Conference Location: Italy, Naples
ISBN: 2075-2180
Publisher: EPTCS  
Date Published: 2012-10-07
Start Page: 29
End Page: 42
URL:
DOI: 10.4204/EPTCS.96.3
Open access: yes (repository)
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
  2. Pavol Černý
    25 Cerný
  3. Martin Chmelik
    23 Chmelik
Related IST Austria Work