---
_id: '2916'
abstract:
- lang: eng
  text: 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.
arxiv: 1
author:
- first_name: Pavol
  full_name: Cerny, Pavol
  id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
  last_name: Cerny
- first_name: Martin
  full_name: Chmelik, Martin
  id: 3624234E-F248-11E8-B48F-1D18A9856A87
  last_name: Chmelik
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Arjun
  full_name: Radhakrishna, Arjun
  id: 3B51CAC4-F248-11E8-B48F-1D18A9856A87
  last_name: Radhakrishna
citation:
  ama: 'Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. Interface Simulation Distances.
    In: <i>Electronic Proceedings in Theoretical Computer Science</i>. Vol 96. EPTCS;
    2012:29-42. doi:<a href="https://doi.org/10.4204/EPTCS.96.3">10.4204/EPTCS.96.3</a>'
  apa: 'Cerny, P., Chmelik, M., Henzinger, T. A., &#38; Radhakrishna, A. (2012). Interface
    Simulation Distances. In <i>Electronic Proceedings in Theoretical Computer Science</i>
    (Vol. 96, pp. 29–42). Napoli, Italy: EPTCS. <a href="https://doi.org/10.4204/EPTCS.96.3">https://doi.org/10.4204/EPTCS.96.3</a>'
  chicago: Cerny, Pavol, Martin Chmelik, Thomas A Henzinger, and Arjun Radhakrishna.
    “Interface Simulation Distances.” In <i>Electronic Proceedings in Theoretical
    Computer Science</i>, 96:29–42. EPTCS, 2012. <a href="https://doi.org/10.4204/EPTCS.96.3">https://doi.org/10.4204/EPTCS.96.3</a>.
  ieee: P. Cerny, M. Chmelik, T. A. Henzinger, and A. Radhakrishna, “Interface Simulation
    Distances,” in <i>Electronic Proceedings in Theoretical Computer Science</i>,
    Napoli, Italy, 2012, vol. 96, pp. 29–42.
  ista: 'Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. 2012. Interface Simulation
    Distances. Electronic Proceedings in Theoretical Computer Science. GandALF: Games,
    Automata, Logic, and Formal Verification vol. 96, 29–42.'
  mla: Cerny, Pavol, et al. “Interface Simulation Distances.” <i>Electronic Proceedings
    in Theoretical Computer Science</i>, vol. 96, EPTCS, 2012, pp. 29–42, doi:<a href="https://doi.org/10.4204/EPTCS.96.3">10.4204/EPTCS.96.3</a>.
  short: P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, in:, Electronic Proceedings
    in Theoretical Computer Science, EPTCS, 2012, pp. 29–42.
conference:
  end_date: 2012-09-08
  location: Napoli, Italy
  name: 'GandALF: Games, Automata, Logic, and Formal Verification'
  start_date: 2012-09-06
date_created: 2018-12-11T12:00:19Z
date_published: 2012-10-07T00:00:00Z
date_updated: 2025-09-29T13:14:24Z
day: '07'
department:
- _id: ToHe
- _id: KrCh
doi: 10.4204/EPTCS.96.3
ec_funded: 1
external_id:
  arxiv:
  - '1210.2450'
intvolume: '        96'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1210.2450
month: '10'
oa: 1
oa_version: Submitted Version
page: 29 - 42
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '267989'
  name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
  name: Microsoft Research Faculty Fellowship
publication: Electronic Proceedings in Theoretical Computer Science
publication_status: published
publisher: EPTCS
publist_id: '3827'
quality_controlled: '1'
related_material:
  record:
  - id: '1733'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: Interface Simulation Distances
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 96
year: '2012'
...