[FM-India]IARCS Verification Seminar Series -- Talk by Sreejith A V on May 20 at 1900 hrs IST

Dear all, The next talk in the IARCS Verification Seminar Series will be given by Sreejith A V, a faculty member in the Department of Computer Science at IIT Goa. The talk is scheduled on Tuesday, May 20, at 1900 hrs IST (add to Google calendar <https://calendar.google.com/calendar/event?action=TEMPLATE&tmeid=NHRwODlxNjJqZDU2NjFraWplOG8yb3BjZWcgdnNzLmlhcmNzQG0&tmsrc=vss.iarcs%40gmail.com> ). The details of the talk can be found on our webpage ( https://fmindia.cmi.ac.in/vss/), and also appended to the body of this email. The Verification Seminar Series, an initiative by the Indian Association for Research in Computing Science (IARCS), is a monthly, online talk-series, broadly in the area of Formal Methods and Programming Languages, with applications in Verification and Synthesis. The aim of this talk-series is to provide a platform for Formal Methods researchers to interact regularly. In addition, we hope that it will make it easier for researchers to explore newer problems/areas and collaborate on them, and for younger researchers to start working in these areas. All are welcome to join. Best regards, Akash, Deepak, Madhukar, Srivathsan ============================================================= Title: Active learning of deterministic one-counter automata Meeting Link: https://us02web.zoom.us/j/89164094870?pwd=eUFNRWp0bHYxRVpwVVNoVUdHU0djQT09 (Meeting ID: 891 6409 4870, Passcode: 082194) Abstract: Deterministic one-counter automata (DOCA) extend finite automata with a counter that can be incremented, decremented or reset to zero. The transition of a DOCA depends on the current state, the letter, and whether the current counter value is zero. In an active learning framework, a Learner intends to learn a language by querying the Teacher with membership and equivalence queries. Angluin's classical L* algorithm showed that in this framework, a DFA can be learnt in polynomial time. In this talk, we are interested in the active learning of DOCA. All existing algorithms for learning DOCA run in time exponential in the size of the minimal DOCA recognising the language. We present OL*, the first active learning algorithm that learns a DOCA in polynomial time. This is a joint work with Prince Mathew and Vincent Penelle. arXiv: https://arxiv.org/abs/2503.04525 (to appear in LICS'25) Bio: Sreejith A V is a faculty member in the Department of Computer Science at IIT Goa. His research interests lie in theoretical computer science, especially formal methods. In the past, he has also held research positions in University of Tubingen, TIFR - Mumbai, LIAFA - Paris, CMI - Chennai, and University of Warsaw - Poland.