BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1540
DTSTAMP:20250403T093508Z
SUMMARY:Learning Real-Time One-Counter Automata Using Polynomially Many Que
 ries
DESCRIPTION:Speaker: Prince Mathew (IIT Goa)\n\nAbstract: \nIn this talk\, 
 we introduce a novel method for active learning of deterministic real-time
  one-counter automata (DROCA). The existing techniques for learning DROCA 
 rely on observing the behaviour of the DROCA up to exponentially large cou
 nter-values. Our algorithm eliminates this need and requires only a polyno
 mial number of queries. Additionally\, our method differs from existing te
 chniques as we learn a minimal counter-synchronous DROCA\, resulting in mu
 ch smaller counter-examples on equivalence queries. Learning a minimal cou
 nter-synchronous automaton cannot be done in polynomial time unless P = NP
 \, even in the case of visibly one-counter automata. We use a SAT solver t
 o overcome this difficulty. The solver is used to compute a minimal separa
 ting DFA from a given set of positive and negative samples. We implemented
  the proposed learning algorithm and tested it on randomly generated DROCA
 . Our evaluations show that the proposed method outperforms the existing t
 echniques on the test set.\nShort Bio:\nPrince Mathew is pursuing his PhD 
 in Theoretical Computer Science under the guidance of Dr. Sreejith A.V. in
  the School of Mathematics and Computer Science at IIT Goa.\n
URL:https://www.tcs.tifr.res.in/web/events/1540
DTSTART;TZID=Asia/Kolkata:20250404T160000
DTEND;TZID=Asia/Kolkata:20250404T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR