Computer Science Seminar
Speaker: Sreejith A. V., IIT Goa
Date: Tuesday, 4 February 2025
Time: 3.45 - 4.45 PM
Venue: Seminar Hall
Active learning of one counter automata
Sreejith A. V.
IIT Goa.
04-02-25

---

Abstract

Deterministic one-counter automata (DOCA) extends 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 construct a machine in the mind of the teacher by querying the co-operative teacher with membership and equivalence queries. Angluin's classical L* algorithm showed that in this framework a DFA can be learnt in polynomial time by the learner.

We are interested in active learning of DOCAs. All existing algorithms for learning DOCAs run in time exponential in the minimal DOCA recognizing the language. In the first part of the talk, we give a P^NP algorithm that learns the minimal DOCA. This algorithm outperforms state of the art learning algorithms. In the second part, we present the first polynomial time algorithm (which we call OL*).