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:20240109T100000
DTEND;TZID=Europe/Paris:20240109T110000
DTSTAMP:20260422T194944
CREATED:20231215T134121Z
LAST-MODIFIED:20231215T134121Z
UID:11364-1704794400-1704798000@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « State complexity: Inverting a language reduces the complexity of the root operation »\, Alexandre Durand (LITIS\, Univ. Rouen)
DESCRIPTION:Automata (DFA) are state machines that accept or reject words. The set of words recognized by an automaton is its its language. Regular languages coincide with languages that can be recognized by automata. Here\, we’re going to focus on a measure\, namely state complexity. For rational languages\, this is defined as the size of the smallest (deterministic) automaton that recognizes the language. On operations\, it is defined as the action of an operation on the minimal automata of rational languages. The root and reverse operations are well-known. Their state complexity are nn – n(n-1)/2 and 2n respectively. One might expect an explosion in the number of states when composing them. \nThe aim of this seminar will be to lay the foundations for the understanding of the problem\, and then to show that not only does root-reverse composition does not produce a combinatorial explosion but in fact produces an automaton smaller than the root automaton in the worst cases.
URL:https://www.greyc.fr/event/seminaire-algorithmique-state-complexity-inverting-a-language-reduces-the-complexity-of-the-root-operation-alexandre-durand-litis-univ-rouen/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20240116T104500
DTEND;TZID=Europe/Paris:20240116T114500
DTSTAMP:20260422T194944
CREATED:20230922T072250Z
LAST-MODIFIED:20240116T093733Z
UID:11262-1705401900-1705405500@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Learning Linear Temporal Logic »\, Nathanaël Fijalkow (CNRS\, LaBRI\, Univ. Bordeaux)
DESCRIPTION:We consider the problem of learning a logical formula from a set of positive and negative examples. The logic we target is Linear Temporal Logic (LTL)\, a prominent formalism in program verification and analysis\, software engineering\, and robot motion planning. \nWe’ll discuss on the one hand theoretical results\, in particular NP-completeness\, and on the other hand a practical approach\, arguing that the problem is a perfect match for GPUs (Graphical Processing Units). No knowledge of LTL or GPU will be required to follow the talk.
URL:https://www.greyc.fr/event/seminaire-algorithmique-nathanael-fijalkow-cnrs-labri-univ-bordeaux/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20240123T100000
DTEND;TZID=Europe/Paris:20240123T110000
DTSTAMP:20260422T194944
CREATED:20231215T143227Z
LAST-MODIFIED:20240108T095104Z
UID:11368-1706004000-1706007600@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Untangling Graphs on Surfaces »\, Loïc Dubois (LIGM\, Univ. G.Eiffel)
DESCRIPTION:Consider a graph drawn on a surface (for example\, the plane minus a finite set of obstacle points)\, possibly with crossings. We provide a polynomial time algorithm to decide whether such a drawing can be untangled\, namely\, if one can slide the vertices and edges of the graph on the surface (avoiding the obstacles) to remove all crossings; in other words\, whether the drawing is homotopic to an embedding. While the problem boils down to planarity testing when the surface is the sphere or the disk (or equivalently the plane without any obstacle)\, the other cases have never been studied before\, except when the input graph is a cycle\, in an abundant literature in topology and more recently by Despré and Lazarus [SoCG 2017\, J. ACM 2019].
URL:https://www.greyc.fr/event/seminaire-algorithmique-loic-dubois-ligm-univ-g-eiffel/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20240130T100000
DTEND;TZID=Europe/Paris:20240130T110000
DTSTAMP:20260422T194944
CREATED:20231215T143338Z
LAST-MODIFIED:20231215T143338Z
UID:11370-1706608800-1706612400@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Géraud Sénizergues (LaBRI\, Univ. Bordeaux)
DESCRIPTION:
URL:https://www.greyc.fr/event/seminaire-algorithmique-geraud-senizergues-labri-univ-bordeaux/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
END:VCALENDAR