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:20230326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20231029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230404T100000
DTEND;TZID=Europe/Paris:20230404T170000
DTSTAMP:20260503T215019
CREATED:20230303T093038Z
LAST-MODIFIED:20230322T164302Z
UID:11121-1680602400-1680627600@www.greyc.fr
SUMMARY:Séminaire Algo : Edwin Hamel (Univ. libre Bruxelles\, Belgique) « Two-player boundedness counter games »
DESCRIPTION:We consider two-player zero-sum games with winning objectives beyond regular languages\, expressed as a parity condition in conjunction with a Boolean combination of boundedness conditions on a finite set of counters which can be incremented\, reset to 0\, but not tested. A boundedness condition requires that a given counter is bounded along the play. Such games are decidable\, though with non-optimal complexity\, by an encoding into the logic WMSO with the unbounded and path quantifiers\, which is known to be decidable over infinite trees. Our objective is to give tight or tighter complexity results for particular classes of counter games with boundedness conditions\, and study their strategy complexity. In particular\, counter games with conjunction of boundedness conditions are easily seen to be equivalent to Streett games\, so\, they are CoNP-complete. Moreover\, finite-memory strategies suffice for Eve and memoryless strategies suffice for Adam. For counter games with a disjunction of boundedness conditions\, we prove that they are in solvable in NP\cap CoNP\, and in PTime if the parity condition is fixed. In that case memoryless strategies suffice for Eve while infinite memory strategies might be necessary for Adam. Finally\, we consider an extension of those games with a max operation. In that case\, the complexity increases: for conjunctions of boundedness conditions\, counter games are EXPTIME-complete.
URL:https://www.greyc.fr/event/seminaire-algo-edwin-hamel-univ-libre-bruxelles-belgique/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230405T110000
DTEND;TZID=Europe/Paris:20230405T120000
DTSTAMP:20260503T215019
CREATED:20230322T164506Z
LAST-MODIFIED:20230322T164506Z
UID:11149-1680692400-1680696000@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Gabriel Le Bouder (LIP6\, Sorbonne Univ.) « Memory-Optimization for Self-Stabilizing Distributed Algorithms »
DESCRIPTION:Self-stabilization is a suitable paradigm for distributed systems\, particularly prone to transient faults. Errors such as memory or messages corruption\, break of a communication link\, can put the system in an inconsistent state. A protocol is self-stabilizing if\, whatever the initial state of the system\, it guarantees that it will return a normal behavior in finite time. Several constraints concern algorithms designed for distributed systems. Asynchrony is one emblematic example. With the development of networks of connected\, autonomous devices\, it also becomes crucial to design algorithms with a low energy consumption\, and not requiring much in terms of resources. \nOne way to address these problems is to aim at reducing the size of the messages exchanged between the nodes of the network. This thesis focuses on the memory optimization of the communication for self-stabilizing distributed algorithms. We will present a negative results\, proving the impossibility to solve some problems under a certain limit on the size of the exchanged messages\, and a particularly efficient algorithms in terms of memory for one fundamental problem in distributed systems: the token circulation.
URL:https://www.greyc.fr/event/seminaire-algorithmique-gabriel-le-bouder-lip6-sorbonne-univ-memory-optimization-for-self-stabilizing-distributed-algorithms/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230411T100000
DTEND;TZID=Europe/Paris:20230411T110000
DTSTAMP:20260503T215019
CREATED:20221216T135437Z
LAST-MODIFIED:20230407T114716Z
UID:11033-1681207200-1681210800@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Julien Clément (GREYC\, Caen) « Combinatorics of reduced ordered binary decision diagrams. Application to random uniform sampling »
DESCRIPTION:Any Boolean function corresponds to a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a directed acyclic graph where common subtrees are factored and shared\, keeping only one copy of each unique  subtree. This yields the celebrated and widely used structure called reduced ordered binary decision diagram (ROBDD). In the random uniform model over the set of Boolean functions with a fixed number of variables the size of a typical ROBDD is of near maximal (exponential) size. This makes random sampling of small ROBDDs (the ones usable in practice) a difficult task even for a few variables. In this talk we want to compute the distribution of ROBDDs (for a fixed number of variables) with respect to the size. As a by-product we get a random uniform and exhaustive sampler for ROBDDs for a given number of variables and size with polynomial time complexity. \nJoint work with Antoine Genitrini (LIP6\, Paris).
URL:https://www.greyc.fr/event/seminaire-algorithmique-julien-clement-greyc-caen/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
END:VCALENDAR