DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
Rechercher
(titres de publication, de périodique et noms de colloque inclus)
2006-06-01 - Article/Dans un journal avec peer-review - Anglais - 7 page(s)

Bouyer Patricia, Brihaye Thomas , Markey Nicolas, "Improved undecidability results on weighted timed automata" in Information Processing Letters, 98, Issue 5, 188-194

  • Edition : Elsevier Science
  • Codes CREF : Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Mathématiques effectives (S820)
Texte intégral :

Abstract(s) :

(Anglais) In this paper, we strengthen two recent undecidability results about weighted timed automata, an extension of timed automata with cost variables. More precisely, we propose new encodings of a Minsky machine that only require three clocks and one stopwatch cost, while previous reductions required five clocks and one stopwatch cost. Timed Systems (FORMATS'05), in: Lecture Notes in Comput. Sci., vol. 3821, Springer, Berlin, 2005, pp. 49-64] about weighted timed automata, an extension of timed automata with cost variables. More precisely, we propose new encodings of a Minsky machine that only require three clocks and one stopwatch cost, while they required five clocks and one stopwatch cost in [Th. Brihaye, V. Bruyere, J.-F. Raskin, On model-checking timed automata with stopwatch observers, 2005, submitted for publication; Th. Brihaye, V. Bruyere, J.-F. Raskin, On optimal timed strategies, in: Proc. 3rd Internat. Conference Formal Modeling and Analysis of Timed Systems (FORMATS'05), in: Lecture Notes in Comput. Sci., vol. 3821, Springer, Berlin, 2005, pp. 49-64].

Identifiants :
  • DOI : 10.1016/j.ipl.2006.01.012