BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:4a124894-8040-4c56-b0c3-3a67d0102fe7
X-WR-CALNAME:[M2F] Julie Parreaux (U. Warsaw) - Weighted Timed Games: Decid
 ability\, Randomness and Robustness
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20251026T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:4a124894-8040-4c56-b0c3-3a67d0102fe7
DTSTAMP:20260922T192936Z
CLASS:PUBLIC
DESCRIPTION:Weighted timed games are two-player zero-sum games played in a 
 timed automaton\nequipped with integer weights. We consider optimal reacha
 bility objectives\, in\nwhich one of the players\, whom we call Min\, want
 s to reach a target location\nwhile minimising the cumulated weight. While
  knowing if Min has a\n(deterministic) strategy to guarantee a value lower
  than a given threshold is\nknown to be undecidable (with two or more cloc
 ks)\, several conditions\, one of\nthem being the divergence or one-clock 
 WTGs with only non-negative weights\,\nhave been given to recover decidabi
 lity. We\, first\, extend this list by\nconsidering arbitrary weights by s
 howing that the value function can be\ncomputed in exponential time (if we
 ights are encoded in unary).\n\nNext\, in such weighted timed games (like 
 in untimed weighted games in the\npresence of negative weights)\, Min may 
 need finite memory to play (close to)\noptimally. This is thus tempting to
  try to emulate this finite memory with\nother strategic capabilities. In 
 particular\, we allow the players to use\nstochastic decisions\, both in t
 he choice of transitions and timing delays. We\ngive\, for the first time\
 , a definition of the expected value in weighted timed\ngames\, overcoming
  several theoretical challenges. We then show that\, in\ndivergent weighte
 d timed games\, the stochastic value is indeed equal to the\nclassical (de
 terministic) value\, thus proving that Min can guarantee the same\nvalue w
 hile only using stochastic choices and no memory.\n\nFinally\, even stocha
 stic strategies\, almost optimal strategies are not\nimplementable since t
 hey use infinite precision of clocks in the choice of the\ndelay or in the
  knowledge about the configurations. Robustness is a known\nprocess to enc
 ode the imprecision of delays in strategies: robustness allows to\nMax pla
 yer (the opponent of Min) to lightly modify the delay chosen by Min. In\nt
 he literature\, two robust semantics exist: conservative semantic checks a
 \nguard after the perturbation\, and excessive semantic checks a guard bef
 ore.\nAs for deterministic strategies\, it was known that if Min has a (ro
 bust)\nstrategy to guarantee a value lower than a given threshold is known
  to be\nundecidable. By adapting the process of value iteration introduced
  by Alur\, we\ncompute the (robust) value in acyclic WTG under conservativ
 e and excessive\nsemantics.
DTSTART;TZID=Europe/Paris:20240319T140000
DTEND;TZID=Europe/Paris:20240319T150000
LOCATION:Amphitheatre du LaBRI
SEQUENCE:0
SUMMARY:[M2F] Julie Parreaux (U. Warsaw) - Weighted Timed Games: Decidabili
 ty\, Randomness and Robustness
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR