Speaker: |
Kshitij Gajjar |

Organiser: |
Deepesh Data |

Date: |
Friday, 14 Jun 2013, 14:30 to 16:00 |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

Parikh used properties of semi-linear sets and derivation trees and presented some interesting combinatorial arguments to arrive at his result. Although Goldstine came up with a simplified proof 11 years later, Parikh's theorem is still considered remarkable since the exact conditions controlling the structure of the derivation trees that he defined are nontrivial.

In this talk, we will define these terms and use them to prove Parikh's theorem, and time permitting, discuss some of its applications.