Quantitative fair simulation games Journal Article


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A; Otop, Jan; Velner, Yaron
Article Title: Quantitative fair simulation games
Affiliation IST Austria
Abstract: Simulation is an attractive alternative to language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. 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. 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 in general, whereas the (quantitative) simulation reduces to quantitative games, which admit pseudo-polynomial time algorithms. In 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, yet they still admit pseudo-polynomial time algorithms.
Keywords: simulation; Weighted automata; Quantitative simulation; fair simulation; mean-payoff and discounted-sum games
Journal Title: Information and Computation
Volume: 254
Issue 2
ISSN: 0890-5401
Publisher: Elsevier  
Date Published: 2017-06-01
Start Page: 143
End Page: 166
DOI: 10.1016/j.ic.2016.10.006
Notes: This research was funded in part by the European Research Council (ERC) under grant agreements 267989 (QUAREM), 279307 (Graph Games), by the Austrian Science Fund (FWF) projects S11402-N23 (RiSE), S11407-N23 (RiSE), P23499-N23, and Microsoft faculty fellows award. A Technical Report of this paper is available at: https://repository.ist.ac.at/id/eprint/315
Open access: yes (repository)
IST Austria Authors
  1. Thomas A. Henzinger
    398 Henzinger
  2. Jan Otop
    15 Otop
Related IST Austria Work