We give an active learning algorithm for deterministic one-counter automata (DOCAs) where the learner can ask the teacher membership and minimal equivalence queries. The algorithm called OL* learns a DOCA in time polynomial in the size of the smallest DOCA, recognising the target language. All existing algorithms for learning DOCAs, even for the subclasses of deterministic real-time one-counter automata (DROCAs) and visibly one-counter automata (VOCAs), in the worst case, run in time exponential in the size of the DOCA under learning. Furthermore, previous learning algorithms are ''grey-box'' algorithms relying on an additional query type - counter value queries - where the teacher must return the counter value for a given word. Our algorithm is a ''black-box'' algorithm, that runs in polynomial time and can learn DOCAs without any restriction. It is known that the minimisation of VOCAs is NP-hard. However, OL* can be used for approximate minimisation of DOCAs. In this case, the output size is at most polynomial in the size of a minimal DOCA.
I am pursuing my PhD in Theoretical Computer Science under the guidance of Dr. Sreejith A V in the School of Mathematics and Computer Science at Indian Institute of Technology, Goa. Our current research is centered on developing better algorithms for the active learning of one-counter automata. Recently, we proved that learning deterministic one-counter automata (DOCAs) can be done in polynomial time. This is the first polynomial time algorithm for learning DOCAs. Previously, we demonstrated that deterministic real-time one-counter automata (DROCAs) can be efficiently learned using a polynomial number of queries, significantly improving upon earlier algorithms that required an exponential number of queries.
Earlier research also established that problems, including equivalence, regularity, and covering for weighted one-counter automata (over fields) with counter determinacy, can be solved in polynomial time. This finding mark a promising step toward addressing the open problem of equivalence of weighted one-counter automata.