BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1372
DTSTAMP:20240102T061417Z
SUMMARY:The transformation of regular expressions into finite automata: old
and new results
DESCRIPTION:Speaker: Jacques Sakarovitch (IRIF\, CNRS/Paris Cité Universit
y)\n\nAbstract: \nNot many results in Computer Science are recognised to b
e as basic and fundamental as Kleene Theorem. It states the equality of
two sets of objects that we call now languages. A slight change of focus
on this result shows how it is essentially the combination of two familie
s of algorithms: algorithms that transform a finite automaton into a regul
ar expression on one hand and algorithms that build a finite automaton fro
m a regular expression on the other.In this talk\, I shall consider the al
gorithms of the latter family\, a much laboured subject of both theoretica
l and practical interests. I shall present three different constructions\,
classically attributed to Thompson\, Glushkov\, and Brzozowski-Antimirov
respectively\, and their relationships.We shall then see how the extension
of Kleene Theorem beyond languages: to subsets of arbitrary monoids first
and second to subsets with multiplicity\, leads to a modification of the
construction for the first one and to a radical transformation of the proo
f for the third.All recent results were obtained in joint works wi
th Sylvain Lombardy.\n
URL:https://www.tcs.tifr.res.in/web/events/1372
DTSTART;TZID=Asia/Kolkata:20240111T160000
DTEND;TZID=Asia/Kolkata:20240111T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR