BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1732
DTSTAMP:20260610T052840Z
SUMMARY:Set automata and limits of decidability of two-variable logic on da
 ta words
DESCRIPTION:Speaker: Rishal S P (Sarva Labs Inc.)\n\nAbstract: \nA data wor
 d is a finite word in which each position carries a label from a finite al
 phabet and a data value from an infinite domain. It is well-known that sat
 isfiability of two-variable first-order logic with the data value equalit
 y test on data words is decidable while three variables leads to undecidab
 ility. In this talk\, we present a decidable extension of the two-variable
  logic by adding guarded regular binary predicates of the form L(x\,y) tha
 t is satisfied by positions x and y if they carry the same data value and 
 the factor strictly between x and y is in the regular language L. We chara
 cterise the class of monoids recognising the regular predicates for which 
 the resulting extension of the two-variable logic is decidable. Our proof 
 is automata-theoretic – we translate formulas to a new automaton formal
 ism called ordered quasi-normal set automaton that has a decidable emptine
 ss problem by reduction to ordered multicounter automata. We obtain decida
 bility for the logic with guarded regular predicates recognised by a monoi
 d if and only if the monoid is idempotent and its two-sided ideals are lin
 early ordered. \nBio: Rishal S P is a researcher at Sarva Labs. He is int
 erested in theoretical computer science\, especially in automata theory\, 
 logic\, and verification. He completed his undergraduate studies in mathem
 atics at Shiv Nadar University\, Delhi-NCR in 2024 and has been an intern 
 at IIT Goa under Amaldev Manuel where he was working on automata and logic
 s on data words. \n
URL:https://www.tcs.tifr.res.in/web/events/1732
DTSTART;TZID=Asia/Kolkata:20260612T113000
DTEND;TZID=Asia/Kolkata:20260612T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR