---
_id: '1733'
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 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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Pavol
  full_name: Cerny, Pavol
  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.
    <i>Theoretical Computer Science</i>. 2014;560(3):348-363. doi:<a href="https://doi.org/10.1016/j.tcs.2014.08.019">10.1016/j.tcs.2014.08.019</a>
  apa: Cerny, P., Chmelik, M., Henzinger, T. A., &#38; Radhakrishna, A. (2014). Interface
    simulation distances. <i>Theoretical Computer Science</i>. Elsevier. <a href="https://doi.org/10.1016/j.tcs.2014.08.019">https://doi.org/10.1016/j.tcs.2014.08.019</a>
  chicago: Cerny, Pavol, Martin Chmelik, Thomas A Henzinger, and Arjun Radhakrishna.
    “Interface Simulation Distances.” <i>Theoretical Computer Science</i>. Elsevier,
    2014. <a href="https://doi.org/10.1016/j.tcs.2014.08.019">https://doi.org/10.1016/j.tcs.2014.08.019</a>.
  ieee: P. Cerny, M. Chmelik, T. A. Henzinger, and A. Radhakrishna, “Interface simulation
    distances,” <i>Theoretical Computer Science</i>, vol. 560, no. 3. Elsevier, pp.
    348–363, 2014.
  ista: Cerny P, Chmelik M, Henzinger TA, Radhakrishna A. 2014. Interface simulation
    distances. Theoretical Computer Science. 560(3), 348–363.
  mla: Cerny, Pavol, et al. “Interface Simulation Distances.” <i>Theoretical Computer
    Science</i>, vol. 560, no. 3, Elsevier, 2014, pp. 348–63, doi:<a href="https://doi.org/10.1016/j.tcs.2014.08.019">10.1016/j.tcs.2014.08.019</a>.
  short: P. Cerny, M. Chmelik, T.A. Henzinger, A. Radhakrishna, Theoretical Computer
    Science 560 (2014) 348–363.
corr_author: '1'
date_created: 2018-12-11T11:53:43Z
date_published: 2014-12-04T00:00:00Z
date_updated: 2025-09-29T13:14:25Z
day: '04'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1016/j.tcs.2014.08.019
ec_funded: 1
external_id:
  arxiv:
  - '1210.2450'
  isi:
  - '000347601300009'
intvolume: '       560'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1210.2450
month: '12'
oa: 1
oa_version: Submitted Version
page: 348 - 363
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '267989'
  name: Quantitative Reactive Modeling
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Moderne Concurrency Paradigms
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _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: Theoretical Computer Science
publication_status: published
publisher: Elsevier
publist_id: '5392'
quality_controlled: '1'
related_material:
  record:
  - id: '2916'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Interface simulation distances
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 560
year: '2014'
...