In Baier, C. & Hermanns, H., editors, *Proceedings of the 17th International Conference on Concurrency Theory (CONCUR)*, of *Lecture Notes in Computer Science*, pages 450–464, 2006. Springer Berlin Heidelberg.

abstract bibtex

abstract bibtex

We consider the control problem for timed automata against specifications given as MTL formulas. The logic MTL is a linear-time timed temporal logic which extends LTL with timing constraints on modalities, and recently, its model-checking has been proved decidable in several cases. We investigate these decidable fragments of MTL (full MTL when interpreted over finite timed words, and Safety-MTL when interpreted over infinite timed words), and prove two kinds of results. (1) We first prove that, contrary to model-checking, the control problem is undecidable. Roughly, the computation of a lossy channel system could be encoded as a model-checking problem, and we prove here that a perfect channel system can be encoded as a control problem. (2) We then prove that if we fix the resources of the controller (by resources we mean clocks and constants that the controller can use), the control problem becomes decidable. This decidability result relies on properties of well (and better) quasi-orderings.

@inproceedings{bouyer_controller_2006, series = {Lecture {Notes} in {Computer} {Science}}, title = {Controller {Synthesis} for {MTL} {Specifications}}, isbn = {978-3-540-37377-3}, abstract = {We consider the control problem for timed automata against specifications given as MTL formulas. The logic MTL is a linear-time timed temporal logic which extends LTL with timing constraints on modalities, and recently, its model-checking has been proved decidable in several cases. We investigate these decidable fragments of MTL (full MTL when interpreted over finite timed words, and Safety-MTL when interpreted over infinite timed words), and prove two kinds of results. (1) We first prove that, contrary to model-checking, the control problem is undecidable. Roughly, the computation of a lossy channel system could be encoded as a model-checking problem, and we prove here that a perfect channel system can be encoded as a control problem. (2) We then prove that if we fix the resources of the controller (by resources we mean clocks and constants that the controller can use), the control problem becomes decidable. This decidability result relies on properties of well (and better) quasi-orderings.}, language = {en}, booktitle = {Proceedings of the 17th {International} {Conference} on {Concurrency} {Theory} ({CONCUR})}, publisher = {Springer Berlin Heidelberg}, author = {Bouyer, Patricia and Bozzelli, Laura and Chevalier, Fabrice}, editor = {Baier, Christel and Hermanns, Holger}, year = {2006}, keywords = {Control Problem, Controller Synthesis, Temporal Logic, Undesired Behaviour, Winning Strategy}, pages = {450--464} }

Downloads: 0