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:20260422T211829
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
END:VCALENDAR