Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems

K. Chatterjee, V. Prabhu, Information and Computation 228–229 (2013) 83–119.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English
Author
Department
Abstract
We study synthesis of controllers for real-time systems, where the objective is to stay in a given safe set. The problem is solved by obtaining winning strategies in the setting of concurrent two player timed automaton games with safety objectives. To prevent a player from winning by blocking time, we restrict each player to strategies that ensure that the player cannot be responsible for causing a Zeno run. We construct winning strategies for the controller which require access only to (1) the system clocks (thus, controllers which require their own internal infinitely precise clocks are not necessary), and (2) a logarithmic (in the number of clocks) number of memory bits (i.e. a linear number of memory states). Precisely, we show that for safety objectives, a memory of size (3 + lg (| C | + 1)) bits suffices for winning controller strategies, where C is the set of clocks of the timed automaton game, significantly improving the previous known exponential memory states bound. We also settle the open question of whether winning region-based strategies require memory for safety objectives by showing with an example the necessity of memory for such strategies to win for safety objectives. Finally, we show that the decision problem of determining if there exists a receptive player-1 winning strategy for safety objectives is EXPTIME-complete over timed automaton games.
Publishing Year
Date Published
2013-04-24
Journal Title
Information and Computation
Volume
228-229
Page
83-119
IST-REx-ID

Cite this

Chatterjee K, Prabhu V. Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems. Information and Computation. 2013;228-229:83-119. doi:10.1016/j.ic.2013.04.003
Chatterjee, K., & Prabhu, V. (2013). Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems. Information and Computation, 228229, 83–119. https://doi.org/10.1016/j.ic.2013.04.003
Chatterjee, Krishnendu, and Vinayak Prabhu. “Synthesis of Memory-Efficient, Clock-Memory Free, and Non-Zeno Safety Controllers for Timed Systems.” Information and Computation 228–229 (2013): 83–119. https://doi.org/10.1016/j.ic.2013.04.003.
K. Chatterjee and V. Prabhu, “Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems,” Information and Computation, vol. 228–229, pp. 83–119, 2013.
Chatterjee K, Prabhu V. 2013. Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems. Information and Computation. 228–229, 83–119.
Chatterjee, Krishnendu, and Vinayak Prabhu. “Synthesis of Memory-Efficient, Clock-Memory Free, and Non-Zeno Safety Controllers for Timed Systems.” Information and Computation, vol. 228–229, Elsevier, 2013, pp. 83–119, doi:10.1016/j.ic.2013.04.003.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar