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:20260329T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20261025T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20260505T104500
DTEND;TZID=Europe/Paris:20260505T114500
DTSTAMP:20260615T161058
CREATED:20260526T120349Z
LAST-MODIFIED:20260526T120349Z
UID:12123-1777977900-1777981500@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « From Elastic Degenerate Strings to Full-Text Indexing: Suffix Sorting\, BWT\, and FM-Index Construction and Search »\, Francesco Pio Marino (Univ. Catane\, Italie)
DESCRIPTION:Elastic degenerate strings provide a flexible framework for representing sequences with structured variability\, generalizing classical string models while preserving algorithmic tractability. In this talk\, we present a comprehensive framework for indexing such objects\, culminating in the construction of an FM-index that supports efficient pattern matching. \nWe begin by revisiting the notion of elastic degeneracy and its algorithmic implications. We then describe how classical building blocks—suffix sorting\, the Burrows–Wheeler Transform (BWT)\, and wavelet trees—can be extended to this richer setting. In particular\, we outline a linear-time suffix sorting approach based on an adaptation of the DC3 algorithm\, followed by the construction of the BWT and the associated wavelet tree representation. \nFinally\, we show how these components combine into a full FM-index and describe how the classical backward search procedure can be adapted to this setting\, enabling efficient pattern matching over elastic degenerate strings. The resulting framework bridges combinatorial pattern matching and compressed indexing\, opening the way to scalable querying in settings where uncertainty and variability are intrinsic.
URL:https://www.greyc.fr/event/seminaire-algorithmique-from-elastic-degenerate-strings-to-full-text-indexing-suffix-sorting-bwt-and-fm-index-construction-and-search-francesco-pio-marino-univ-catane-italie/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20260512T104500
DTEND;TZID=Europe/Paris:20260512T114500
DTSTAMP:20260615T161058
CREATED:20260526T120536Z
LAST-MODIFIED:20260526T120536Z
UID:12125-1778582700-1778586300@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Un automate pour les caractériser tous »\, Théo Grente (GREYC)
DESCRIPTION:Au début des années 2000\, Okhotin a introduit deux familles de grammaires formelles\, les grammaires conjonctives et les grammaires booléennes\, qu’il présente comme “le véritable cas général des grammaires sans contexte”. Ces grammaires enrichissent les grammaires algébriques par l’ajout d’une opération de conjonction pour les grammaires conjonctives et de la négation en plus de la conjonction pour les grammaires booléennes. Ces deux nouvelles grammaires (et leurs restrictions linéaires) viennent ainsi étoffer la zoologie des classes de langages formels sans contexte. L’un des critères permettant de mesurer l’importance d’une classe de langages est qu’elle dispose d’une définition équivalente par une famille d’automates. On peut ainsi citer la caractérisation des langages réguliers par les automates finis\, celle des algébriques par les automates à pile ou encore la caractérisation de la restriction linéaire des grammaires conjonctives par les automates treillis. Ces caractérisations nous permettent de mieux comprendre le pouvoir d’expression des grammaires mais ne facilitent pas forcément leur comparaison. \nDans cet exposé\, je présenterai une famille d’automates\, appelés automates SCYK\, permettant d’obtenir une caractérisation uniforme des classes de langages citées. Cette famille d’automates est inspirée de l’algorithme classique pour la reconnaissance de langages algébriques découvert indépendamment par Sakai\, Cocke\, Younger et Kasami (d’où son nom). Dans leur version la plus générale\, ces automates caractérisent exactement les langages booléens puis\, en leur ajoutant différentes restrictions\, ceux-ci nous permettent de caractériser naturellement les langages conjonctifs\, algébriques (avec leurs restrictions linéaires) ainsi que les langages réguliers.
URL:https://www.greyc.fr/event/seminaire-algorithmique-un-automate-pour-les-caracteriser-tous-theo-grente-greyc/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20260519T104500
DTEND;TZID=Europe/Paris:20260519T114500
DTSTAMP:20260615T161058
CREATED:20260526T112223Z
LAST-MODIFIED:20260526T112223Z
UID:12114-1779187500-1779191100@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Effective Asymptotics of Combinatorial Systems »\, Carine Pivoteau (LIGM\, Univ. Paris-Est Marne la Vallée)
DESCRIPTION:In their book “Analytic Combinatorics”\, Flajolet and Sedgewick describe a general approach that starts from a combinatorial description\, translates this description into equations satisfied by generating functions\, views these generating functions as analytic functions and exploits their singular behavior to deduce asymptotic properties of the combinatorial objects when their size becomes large. \nWith Bruno Salvy\, we developed computational tools that automate large parts of this approach and in this talk I will outline the main steps.
URL:https://www.greyc.fr/event/seminaire-algorithmique-effective-asymptotics-of-combinatorial-systems-carine-pivoteau-ligm-univ-paris-est-marne-la-vallee/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20260526T104500
DTEND;TZID=Europe/Paris:20260526T114500
DTSTAMP:20260615T161058
CREATED:20260526T112049Z
LAST-MODIFIED:20260526T112049Z
UID:12112-1779792300-1779795900@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Weihrauch et la topologie »\, Emmanuel Rauzy (LACL\, Univ. Paris-Est Créteil)
DESCRIPTION:Le but de cet exposé est d’introduire les deux fondements de l’analyse calculable : la théorie des espaces représentés et ses liens avec la topologie\, et la réduction de Weihrauch. \nJ’insisterai en particulier sur le fait que la réduction de Weihrauch est définie grâce à une notion de multifonction continue que l’on ne peut définir que dans la catégorie des espaces représentés. Enfin\, je présenterai de nouveaux outils\, développés avec Vasco Brattka\, pour déterminer facilement la topologie finale d’une représentation.
URL:https://www.greyc.fr/event/seminaire-algorithmique-weihrauch-et-la-topologie-emmanuel-rauzy-lacl-univ-paris-est-creteil/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
END:VCALENDAR