Speaker: |
Gaurav Sood |

Organiser: |
Arkadev Chattopadhyay |

Date: |
Tuesday, 24 Jun 2014, 15:30 to 17:00 |

Venue: |
D-405 (D-Block Seminar Room) |

(Scan to add to calendar)

In 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 the MFP solution is P-complete. This shows that the problem can not have efficient parallel algorithms unless P = NC. We will also show that the problem of computing the MOP solution is NL-complete (and hence efficiently parallelizable) when the semilattice is finite. These results appear in contrast with the fact that computing the MOP solution is significantly harder than the MFP solution in general.