BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1430
DTSTAMP:20240722T043818Z
SUMMARY:Type-Checking for Pattern-Based Tree Transformations
DESCRIPTION:Speaker: M. Praveen (Chennai Mathematical Institute)\n\nAbstrac
 t: \nWe introduce and study pattern-based tree transformations. Consider (
 +(.(x\, y)\, .(x\, z))\, .(x\, +(y\, z)))\, a pair of a source pattern and
  a target pattern. This source pattern matches any expression e of the for
 m +(.(e1 \, e2 )\, .(e1 \, e3 ))\, by substituting e1 for x\, e2 for y and
  e3 for z. Note that the set of such matching expressions is not a regular
  tree language\, since the same expression must appear in two locations wh
 ere x appears in the source pattern. This pair transforms the expression e
  into the expression .(e1 \, +(e2 \, e3 )) (obtained by applying the same 
 substitution to the target pattern). Our model finitely represents a (poss
 ibly infinite) set of such (source pattern\, target pattern) pairs. The ex
 pressive power of this model comes at the cost of undecidability of checki
 ng equivalence. The type-checking problem checks whether applying a given 
 transformation to trees having a given regular property (type) preserves t
 he property. We show that this problem is decidable for pattern-based tree
  transformations. Our decision procedure is by a reduction to the emptines
 s problem of alternating tree automata.This is joint work with C. Aiswarya
  and Sahil Mhaskar from Chennai Mathematical Institute.\nShort Bio:\nPrave
 en is an associate professor at Chennai Mathematical Institute. He finishe
 d PhD at the Institute of Mathematical Institute\, Chennai. He was a postd
 oc at LSV\, ENS Cachan and LaBRI\, University of Bordeaux before he joined
  CMI in 2014. His research interests and logic and automata theory for for
 mal verification.\n
URL:https://www.tcs.tifr.res.in/web/events/1430
DTSTART;TZID=Asia/Kolkata:20240730T160000
DTEND;TZID=Asia/Kolkata:20240730T170000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR