BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:269e67e7-0107-4ab5-8a01-4248caafb2e9
X-WR-CALNAME:[MTV] Pierre VANDENHOVE - Memory Requirements of Omega-Regular
  Objectives: the Regular Case
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20241027T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20221030T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20231029T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20220327T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20230326T020000
RDATE:20240331T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:269e67e7-0107-4ab5-8a01-4248caafb2e9
DTSTAMP:20260418T201134Z
CLASS:PUBLIC
DESCRIPTION:We study zero-sum games played on graphs and present contributi
 ons toward the following question: given an objective\, how much memory is
  required to play optimally? This question has been well-studied since the
  1980s\, with complete answers for large classes of omega-regular objectiv
 es. Nevertheless\, there is still no precise general answer for arbitrary 
 omega-regular objectives\, despite their significance in various fields. T
 oward this goal\, we study a simple subclass of the omega-regular objectiv
 es that we call the regular objectives. In such games\, the goal of one of
  the two players is that\, eventually\, the sequence of colors along the p
 lay belongs to some regular language of finite words. We obtain different 
 characterizations of the memory requirements for such objectives for both 
 players\, from which we derive complexity-theoretic statements: deciding w
 hether there exist small memory structures sufficient to play optimally is
  NP-complete for both players. Some of our characterization results apply 
 to a more general class of objectives: topologically closed and topologica
 lly open sets.\nThese results are based on joint work with Patricia Bouyer
 \, Nathanaël Fijalkow\, and Mickael Randour.
DTSTART;TZID=Europe/Paris:20230302T130000
DTEND;TZID=Europe/Paris:20230302T140000
LOCATION:salle 178\, zoom: https://bordeaux-inp-fr.zoom.us/j/89508306159
SEQUENCE:0
SUMMARY:[MTV] Pierre VANDENHOVE - Memory Requirements of Omega-Regular Obje
 ctives: the Regular Case
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
