BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:cc4bcd44-6408-4daf-a541-054b54b87a27
X-WR-CALNAME:GT MTV - Jérôme Leroux - The Semilinear Home-Space Problem is 
 Ackermann-Complete for Petri Nets
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20250330T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20221030T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20231029T030000
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:cc4bcd44-6408-4daf-a541-054b54b87a27
DTSTAMP:20260420T180447Z
CLASS:PUBLIC
DESCRIPTION:A set of configurations H is a home-space for a set of configur
 ations X of a Petri net if every configuration reachable from (any configu
 ration in) X can reach (some configuration in) H. The semilinear home-spac
 e problem for Petri nets asks\, given a Petri net and semilinear sets of c
 onfigurations X\, H\, if H is a home-space for X. In 1989\, David de Fruto
 s Escrig and Colette Johnen proved that the problem is decidable when X is
  a singleton and H is a finite union of linear sets with the same periods.
  In this presentation\, we show that the general (semilinear) problem is d
 ecidable. This result is obtained by proving a duality between the reachab
 ility problem and the non-home-space problem. In particular\, we prove tha
 t for any Petri net and any linear set of configurations L we can effectiv
 ely compute a semilinear set C of configurations\, called a non-reachabili
 ty core for L\, such that for every set X the set L is not a home-space fo
 r X if\, and only if\, C is reachable from X. We show that the established
  relation to the reachability problem yields the Ackermann-completeness of
  the (semilinear) home-space problem. For this we also show that\, given a
  Petri net with an initial marking\, the set of minimal reachable markings
  can be constructed in Ackermannian time.\nThis is a joint work with Petr 
 Jančar (Dept of Comp. Sci.\, Faculty of Science\, Palacký Univ. Olomouc\,
  Czechia).
DTSTART;TZID=Europe/Paris:20230914T130000
DTEND;TZID=Europe/Paris:20230914T140000
LOCATION:salle 178\, zoom: https://bordeaux-inp-fr.zoom.us/j/89508306159
SEQUENCE:0
SUMMARY:GT MTV - Jérôme Leroux - The Semilinear Home-Space Problem is Acker
 mann-Complete for Petri Nets
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
