BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/375
DTSTAMP:20230914T125922Z
SUMMARY:Parikh's Theorem
DESCRIPTION:Speaker: Kshitij  Gajjar\n\nAbstract: \nWe know that every regu
 lar language is context-free but a context-free language need not be regul
 ar. In 1966\, Rohit Parikh showed that if th order of the symbols in a con
 text-free language is ignored\, it is impossible to distinguish it from a 
 regular set\, thus implying that context-free languages can have a richer 
 structure than those obtained rom regular sets.\n\nParikh used properties 
 of semi-linear sets and derivation trees and presented some interesting co
 mbinatorial arguments to arrive at his result. Although Goldstine came up 
 with a simplified proof 11 years later\, Parikh's theorem is still conside
 red remarkable since the exact conditions controlling the structure of the
  derivation trees that he defined are nontrivial.\n\nIn this talk\, we wil
 l define these terms and use them to prove Parikh's theorem\, and time per
 mitting\, discuss some of its applications.\n
URL:https://www.tcs.tifr.res.in/web/events/375
DTSTART;TZID=Asia/Kolkata:20130614T143000
DTEND;TZID=Asia/Kolkata:20130614T160000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR