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