BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/514
DTSTAMP:20230914T125927Z
SUMMARY:On the Computational Complexity of Data Flow Analysis Over Finite B
ounded Meet-semilattices
DESCRIPTION:Speaker: Gaurav Sood\n\nAbstract: \nAbstract: In order to perf
orm global code optimizations\, the compiler needs to gather information a
bout a program. It may want to know whether a value computed will be used
later during the execution of the program (Live Variables Analysis) or whe
ther during the execution\, the result of an expression computation can be
reused at several places (Available Expressions Analysis). Data flow anal
ysis is an abstraction of these and several other similar analyses. This i
nformation can be gathered by computing the Meet Over all Paths (MOP) solu
tion for Data Flow Analysis. However\, if the underlying semilattice is in
finite\, computing the MOP solution is undecidable. So as a safe approxima
tion\, we settle with the Maximum Fixed Point (MFP) solution which is poly
nomial time computable for semilattices of finite height.\n\nIn this talk\
, we consider Data Flow Analysis over monotone data flow frameworks with a
finite bounded meet-semilattice. We show that the problem of computing th
e MFP solution is P-complete. This shows that the problem can not have eff
icient parallel algorithms unless P = NC. We will also show that the probl
em of computing the MOP solution is NL-complete (and hence efficiently par
allelizable) when the semilattice is finite. These results appear in contr
ast with the fact that computing the MOP solution is significantly harder
than the MFP solution in general.\n
URL:https://www.tcs.tifr.res.in/web/events/514
DTSTART;TZID=Asia/Kolkata:20140624T153000
DTEND;TZID=Asia/Kolkata:20140624T170000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR