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:20260512T104500
DTEND;TZID=Europe/Paris:20260512T114500
DTSTAMP:20260526T193608
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
END:VCALENDAR