BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:ff02c2e1-ad15-4514-93c7-6a64cca36a92
X-WR-CALNAME:[MTV] Hugo Gimbert - 'Distributed Asynchronous Games With Caus
 al Memory are Undecidable'
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20231029T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20211031T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20221030T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20210328T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20220327T020000
RDATE:20230326T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ff02c2e1-ad15-4514-93c7-6a64cca36a92
DTSTAMP:20260522T194757Z
CLASS:PUBLIC
DESCRIPTION:The distributed version of the Ramadge and Wonham control probl
 em asks for the existence of a correct controller of a plant modeled as an
  asynchronous transition system. The controllable plant is distributed on 
 several finite-state processes which interact asynchronously using shared 
 actions. The controller is distributed as well\, and decomposes as one loc
 al controller on every process. Each local controller can choose to block 
 some of the actions\, called controllable actions\, but it cannot block th
 e uncontrollable actions from the environment. A controller is correct if 
 it guarantees that every possible execution of the plant satisfies some sp
 ecification. The controller synthesis problem is the decision problem whic
 h\, given a plant as input\, asks whether the system admits a correct cont
 roller. In case such a controller exists\, the algorithm should compute on
 e as well. The difficulty of the controller synthesis depends on several f
 actors\, including the architecture of the information flow between proces
 ses (pipeline\, ring\, ...)\, the information available to the controllers
 \, and the specification. The choices of the local controllers can be base
 d on several sources of information. A minima\, a local controller monitor
 s the sequence of states and actions of the local process. This informatio
 n is called the *local view* of the controller. Pnueli and Rosner proved t
 hat the distributed controller synthesis problem is undecidable when local
  controllers are restricted to use their local view for taking decisions\,
  even for very simple architectures. Gastin\, Lerman and Zeitoun have prop
 osed in 2004 a variant of the distributed controller synthesis problem whe
 re local controllers are allowed to base their decisions on their *causal 
 past*. When a shared action is played by several processes then all the co
 ntrollers of these processes are allowed to exchange as much information a
 s they want\, and in particular together they can compute their mutual vie
 w of the global execution: their causal past. In this setting\, Gastin et 
 al. established the decidability of the synthesis for series-parallel arch
 itectures\, and left open the decidability in the general case. In this ta
 lk\, we provide a negative answer to their open question: the distributed 
 controller synthesis problem with causal memory is undecidable. We also re
 view several architectures which where proved decidable or for which the d
 ecidability is still open.
DTSTART;TZID=Europe/Paris:20220310T130000
DTEND;TZID=Europe/Paris:20220310T140000
LOCATION:LaBRI - 076 - https://bordeaux-inp-fr.zoom.us/j/89508306159
SEQUENCE:0
SUMMARY:[MTV] Hugo Gimbert - 'Distributed Asynchronous Games With Causal Me
 mory are Undecidable'
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
