Title: Active learning of deterministic one-counter automata

Speaker: Sreejith A V    (bio) (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.

When: Tuesday, 20 May 2025 at 1900 hrs (IST)  

Meeting Details: Zoom link, 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)