BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/95
DTSTAMP:20230914T125910Z
SUMMARY:Some Extentsions to the Theory of Regularity in Formal Languages
DESCRIPTION:Speaker: Ajesh Babu\nSchool of Technology and Computer Science\
nTata Institute of Fundamental Research\nHomi Bhabha Road\n\nAbstract: \nI
n formal languguage theory\, regularity is a robust notion having many equ
ivalent representations: regular expressions\, ï¬nite state automata\,
MSO etc. These have made important impact on programming and veriï¬ca
tion tools. In this talk we delve into some the alternate formulations and
extensions of regularity:\n\n1) We will look at a new representation for
the $epsilon$-free fragment of regular languages by replacing the conventi
onal concatenation operator by the chop operator\, giving rise to the noti
on of chop expressions. We study the eï¬€ective conversions between ch
op expressions\, regular expression and ï¬nite state automata and pin
down the complexities of various decision procedures for chop expressions
and its extensions. Following Salomaaâ€™s complete axiomatization of
regular expressions\, we provide a complete axiom system for equality chop
expressions.\n\n2) We shall survey the ï¬eld of automata over inï¬
nite alphabet. This area of research aims at extending regular language
theory over ï¬nite alphabet to a corresponding theory over inï¬nit
e alphabet. We also provide an eï¬ƒcient decision procedure for emptine
ss of nested data\nword CMAs.\n\n3) We shall also discuss a logspace rando
mized 1-pass algorithm for the membership checking of deterministic linear
context-free languages.\n
URL:https://www.tcs.tifr.res.in/web/events/95
DTSTART;VALUE=DATE:20100625
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR