---
_id: '5428'
abstract:
- lang: eng
  text: "Simulation is an attractive alternative for language inclusion for automata
    as it is an under-approximation of language inclusion, but usually has much lower
    complexity. For non-deterministic automata, while language inclusion is PSPACE-complete,
    simulation can be computed in polynomial time. Simulation has also been extended
    in two orthogonal directions, namely, (1) fair simulation, for simulation over
    specified set of infinite runs; and (2) quantitative simulation, for simulation
    between weighted automata. Again, while fair trace inclusion is PSPACE-complete,
    fair simulation can be computed in polynomial time. For weighted automata, the
    (quantitative) language inclusion problem is undecidable for mean-payoff automata
    and the decidability is open for discounted-sum automata, whereas the (quantitative)
    simulation reduce to mean-payoff games and discounted-sum games, which admit pseudo-polynomial
    time algorithms.\r\n\r\nIn this work, we study (quantitative) simulation for weighted
    automata with Büchi acceptance conditions, i.e., we generalize fair simulation
    from non-weighted automata to weighted automata. We show that imposing Büchi acceptance
    conditions on weighted automata changes many fundamental properties of the simulation
    games. For example, whereas for mean-payoff and discounted-sum games, the players
    do not need memory to play optimally; we show in contrast that for simulation
    games with Büchi acceptance conditions, (i) for mean-payoff objectives, optimal
    strategies for both players require infinite memory in general, and (ii) for discounted-sum
    objectives, optimal strategies need not exist for both players. While the simulation
    games with Büchi acceptance conditions are more complicated (e.g., due to infinite-memory
    requirements for mean-payoff objectives) as compared to their counterpart without
    Büchi acceptance conditions, we still present pseudo-polynomial time algorithms
    to solve simulation games with Büchi acceptance conditions for both weighted mean-payoff
    and weighted discounted-sum automata."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- 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: Jan
  full_name: Otop, Jan
  id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
  last_name: Otop
- first_name: Yaron
  full_name: Velner, Yaron
  last_name: Velner
citation:
  ama: Chatterjee K, Henzinger TA, Otop J, Velner Y. <i>Quantitative Fair Simulation
    Games</i>. IST Austria; 2014. doi:<a href="https://doi.org/10.15479/AT:IST-2014-315-v1-1">10.15479/AT:IST-2014-315-v1-1</a>
  apa: Chatterjee, K., Henzinger, T. A., Otop, J., &#38; Velner, Y. (2014). <i>Quantitative
    fair simulation games</i>. IST Austria. <a href="https://doi.org/10.15479/AT:IST-2014-315-v1-1">https://doi.org/10.15479/AT:IST-2014-315-v1-1</a>
  chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Yaron Velner.
    <i>Quantitative Fair Simulation Games</i>. IST Austria, 2014. <a href="https://doi.org/10.15479/AT:IST-2014-315-v1-1">https://doi.org/10.15479/AT:IST-2014-315-v1-1</a>.
  ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and Y. Velner, <i>Quantitative fair
    simulation games</i>. IST Austria, 2014.
  ista: Chatterjee K, Henzinger TA, Otop J, Velner Y. 2014. Quantitative fair simulation
    games, IST Austria, 26p.
  mla: Chatterjee, Krishnendu, et al. <i>Quantitative Fair Simulation Games</i>. IST
    Austria, 2014, doi:<a href="https://doi.org/10.15479/AT:IST-2014-315-v1-1">10.15479/AT:IST-2014-315-v1-1</a>.
  short: K. Chatterjee, T.A. Henzinger, J. Otop, Y. Velner, Quantitative Fair Simulation
    Games, IST Austria, 2014.
date_created: 2018-12-12T11:39:16Z
date_published: 2014-12-05T00:00:00Z
date_updated: 2026-06-18T08:47:00Z
day: '05'
ddc:
- '004'
department:
- _id: ToHe
- _id: KrCh
doi: 10.15479/AT:IST-2014-315-v1-1
file:
- access_level: open_access
  checksum: b1d573bc04365625ff9974880c0aa807
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:53:59Z
  date_updated: 2020-07-14T12:46:52Z
  file_id: '5521'
  file_name: IST-2014-315-v1+1_report.pdf
  file_size: 531046
  relation: main_file
file_date_updated: 2020-07-14T12:46:52Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '26'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '315'
related_material:
  record:
  - id: '1066'
    relation: later_version
    status: public
status: public
title: Quantitative fair simulation games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...