---
_id: '4496'
abstract:
- lang: eng
  text: 'The simulation preorder for labeled transition systems is defined locally
    as a game that relates states with their immediate successor states. Liveness
    assumptions about transition systems are typically modeled using fairness constraints.
    Existing notions of simulation for fair transition systems, however, are not local,
    and as a result, many appealing properties of the simulation preorder are lost.
    We extend the local definition of simulation to account for fairness: system S
    fairly simulates system I iff in the simulation game, there is a strategy that
    matches with each fair computation of I a fair computation of S. Our definition
    enjoys a fully abstract semantics and has a logical characterization: S fairly
    simulates I iff every fair computation tree embedded in the unrolling of I can
    be embedded also in the unrolling of S or, equivalently, iff every Fair-AFMC formula
    satisfied by I is satisfied also by S (AFMC is the universal fragment of the alternation-free
    -calculus). The locality of the definition leads us to a polynomial-time algorithm
    for checking fair simulation for finite-state systems with weak and strong fairness
    constraints. Finally, fair simulation implies fair trace-containment, and is therefore
    useful as an efficientlycomputable local criterion for proving linear-time abstraction
    hierarchies.'
acknowledgement: This research was supported in part by the ONR YIP award N00014-95-1-0520,
  by the NSF CAREER award CCR-9501708, by the NSF grant CCR-9504469, by the AFOSR
  contract F49620-93-1-0056, by the ARO MURI grant DAAH-04-96-1-0341, by the ARPA
  grant NAG2-892, and by the SRC contract 95-DC-324.036.
alternative_title:
- LNCS
article_processing_charge: No
author:
- 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: Orna
  full_name: Kupferman, Orna
  last_name: Kupferman
- first_name: Sriram
  full_name: Rajamani, Sriram
  last_name: Rajamani
citation:
  ama: 'Henzinger TA, Kupferman O, Rajamani S. Fair simulation. In: <i>Proceedings
    of the 8th International Conference on Concurrency Theory</i>. Vol 1243. Springer;
    1997:273-287. doi:<a href="https://doi.org/10.1007/3-540-63141-0_19">10.1007/3-540-63141-0_19</a>'
  apa: 'Henzinger, T. A., Kupferman, O., &#38; Rajamani, S. (1997). Fair simulation.
    In <i>Proceedings of the 8th International Conference on Concurrency Theory</i>
    (Vol. 1243, pp. 273–287). Warsaw, Poland: Springer. <a href="https://doi.org/10.1007/3-540-63141-0_19">https://doi.org/10.1007/3-540-63141-0_19</a>'
  chicago: Henzinger, Thomas A, Orna Kupferman, and Sriram Rajamani. “Fair Simulation.”
    In <i>Proceedings of the 8th International Conference on Concurrency Theory</i>,
    1243:273–87. Springer, 1997. <a href="https://doi.org/10.1007/3-540-63141-0_19">https://doi.org/10.1007/3-540-63141-0_19</a>.
  ieee: T. A. Henzinger, O. Kupferman, and S. Rajamani, “Fair simulation,” in <i>Proceedings
    of the 8th International Conference on Concurrency Theory</i>, Warsaw, Poland,
    1997, vol. 1243, pp. 273–287.
  ista: 'Henzinger TA, Kupferman O, Rajamani S. 1997. Fair simulation. Proceedings
    of the 8th International Conference on Concurrency Theory. CONCUR: Concurrency
    Theory, LNCS, vol. 1243, 273–287.'
  mla: Henzinger, Thomas A., et al. “Fair Simulation.” <i>Proceedings of the 8th International
    Conference on Concurrency Theory</i>, vol. 1243, Springer, 1997, pp. 273–87, doi:<a
    href="https://doi.org/10.1007/3-540-63141-0_19">10.1007/3-540-63141-0_19</a>.
  short: T.A. Henzinger, O. Kupferman, S. Rajamani, in:, Proceedings of the 8th International
    Conference on Concurrency Theory, Springer, 1997, pp. 273–287.
conference:
  end_date: 1997-07-04
  location: Warsaw, Poland
  name: 'CONCUR: Concurrency Theory'
  start_date: 1997-07-01
date_created: 2018-12-11T12:09:09Z
date_published: 1997-01-01T00:00:00Z
date_updated: 2022-08-17T09:09:13Z
day: '01'
doi: 10.1007/3-540-63141-0_19
extern: '1'
intvolume: '      1243'
language:
- iso: eng
month: '01'
oa_version: None
page: 273 - 287
publication: Proceedings of the 8th International Conference on Concurrency Theory
publication_identifier:
  isbn:
  - '9783540631415'
publication_status: published
publisher: Springer
publist_id: '234'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fair simulation
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1243
year: '1997'
...