BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20240331T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20241027T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20240507T100000
DTEND;TZID=Europe/Paris:20240507T170000
DTSTAMP:20260504T033056
CREATED:20240513T081850Z
LAST-MODIFIED:20240513T081850Z
UID:11511-1715076000-1715101200@www.greyc.fr
SUMMARY:Séminaire Algorithmique « Synthesis for fragments of first-order logic on data words »\, Julien Grange (LACL\, Univ. Paris-Est Créteil)
DESCRIPTION:We carry on the study initiated by Bérard et al.[1] of the reactive synthesis problem for distributed systems with an unbounded number of participants interacting with an uncontrollable environment. Executions of those systems are modeled by data words (i.e. finite or infinite words were positions are labeled by an unbounded alphabet)\, and specifications are given as first-order formulas. \nFirst\, we delineate the border between decidability and undecidability for the fragments introduced by Bérard et al.[1]. We then introduce prefix first-order logic\, a logic that implements a limited kind of order\, and show that this logic has a decidable synthesis problem on data words. \n[1] Bérard Béatrice\, et al. “Parameterized Synthesis for Fragments of First-Order Logic Over Data Words.” FoSSaCS. 2020.
URL:https://www.greyc.fr/event/seminaire-algorithmique-synthesis-for-fragments-of-first-order-logic-on-data-words-julien-grange-lacl-univ-paris-est-creteil/
LOCATION:Salle à déterminer
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20240514T100000
DTEND;TZID=Europe/Paris:20240514T110000
DTSTAMP:20260504T033056
CREATED:20240513T082027Z
LAST-MODIFIED:20241003T140141Z
UID:11513-1715680800-1715684400@www.greyc.fr
SUMMARY:Séminaire Algorithmique « History-deterministic and explorable automata »\, Denis Kuperberg (LIP\, ENS Lyon)
DESCRIPTION:History-deterministic automata are intermediary between deterministic and nondeterministic ones\, and have been the object of thorough study in the last decade. They offer a way to get a better grasp of the power of nondeterminism\, by allowing only some aspects of it: nondeterministic choices are allowed to depend on the past of the computation but not on the future. I will present the state of the art on the understanding of these history-deterministic automata\, as well as open problems related to complexity questions. If time permits\, I will finish by presenting a recent generalization of history-determinism called explorable automata\, where more nondeterminism is allowed\, and some intriguing decidability questions remain open.
URL:https://www.greyc.fr/event/seminaire-algorithmique-synthesis-for-fragments-of-first-order-logic-on-data-words-denis-kuperberg-lip-ens-lyon/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20240521T100000
DTEND;TZID=Europe/Paris:20240521T110000
DTSTAMP:20260504T033056
CREATED:20240513T082150Z
LAST-MODIFIED:20240524T150934Z
UID:11515-1716285600-1716289200@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Computability of extender sets in multidimensional subshifts »\, Léo Paviet Salomon (GREYC\, Caen)
DESCRIPTION:A classical result from the theory of formal languages\, the Myhill-Nerode theorem\, gives a necessary and sufficient condition in terms of congruence classes for a language to be regular. In this talk\, we try to adapt this result to the case of subshifts\, in which we consider potentially multidimensional infinite configurations rather than finite words. In particular\, we study the behavior of /extender entropy/\, a property introduced by R. Pavlov and T. French which is analogous to congruence classes in formal languages\, and obtain some computability characterizations on the possible extender entropies of various classes of subshifts.
URL:https://www.greyc.fr/event/seminaire-algorithmique-leo-paviet-salomon-greyc-caen/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
END:VCALENDAR