Interface Simulation Distances Journal Article

Author(s): Cerný, Pavol; Chmelík, Martin; Henzinger, Thomas A; Radhakrishna, Arjun
Article 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 distance for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intuitively, 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, that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces, and how to synthesize an interface from incompatible requirements. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies.
Keywords: Quantitative Analysis; games; Alternating simulation
Journal Title: Theoretical Computer Science
Volume: 560
Issue 3
ISSN: 0304-3975
Publisher: Elsevier  
Date Published: 2014-12-04
Start Page: 348
End Page: 363
Sponsor: This research was partially supported by the European Research Council (ERC) Advanced Investigator Grant (267989: QUAREM), the Austrian Science Fund (FWF) projects S11402-N23 and S11407-N23 (RiSE), the Austrian Science Fund (FWF) Grant No. P 23499-N23, ER
DOI: 10.1016/j.tcs.2014.08.019
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