Solving games without determinization

T.A. Henzinger, N. Piterman, in:, Springer, 2006, pp. 395–410.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
Series Title
LNCS
Abstract
The synthesis of reactive systems requires the solution of two-player games on graphs with ω-regular objectives. When the objective is specified by a linear temporal logic formula or nondeterministic Büchi automaton, then previous algorithms for solving the game require the construction of an equivalent deterministic automaton. However, determinization for automata on infinite words is extremely complicated, and current implementations fail to produce deterministic automata even for relatively small inputs. We show how to construct, from a given nondeterministic Büchi automaton, an equivalent nondeterministic parity automaton that is good for solving games with objective . The main insight is that a nondeterministic automaton is good for solving games if it fairly simulates the equivalent deterministic automaton. In this way, we omit the determinization step in game solving and reactive synthesis. The fact that our automata are nondeterministic makes them surprisingly simple, amenable to symbolic implementation, and allows an incremental search for winning strategies.
Publishing Year
Date Published
2006-09-20
Acknowledgement
This research was supported in part by the Swiss National Science Foundation.
Volume
4207
Page
395 - 410
Conference
CSL: Computer Science Logic
IST-REx-ID

Cite this

Henzinger TA, Piterman N. Solving games without determinization. In: Vol 4207. Springer; 2006:395-410. doi:10.1007/11874683_26
Henzinger, T. A., & Piterman, N. (2006). Solving games without determinization (Vol. 4207, pp. 395–410). Presented at the CSL: Computer Science Logic, Springer. https://doi.org/10.1007/11874683_26
Henzinger, Thomas A, and Nir Piterman. “Solving Games without Determinization,” 4207:395–410. Springer, 2006. https://doi.org/10.1007/11874683_26.
T. A. Henzinger and N. Piterman, “Solving games without determinization,” presented at the CSL: Computer Science Logic, 2006, vol. 4207, pp. 395–410.
Henzinger TA, Piterman N. 2006. Solving games without determinization. CSL: Computer Science Logic, LNCS, vol. 4207. 395–410.
Henzinger, Thomas A., and Nir Piterman. Solving Games without Determinization. Vol. 4207, Springer, 2006, pp. 395–410, doi:10.1007/11874683_26.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar