| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4950707 | Information and Computation | 2017 | 24 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Krishnendu Chatterjee, Thomas A. Henzinger, Jan Otop, Yaron Velner,