Learning Deterministic One-Counter Automata in Polynomial Time
Prince Mathew, Vincent Penelle, A. V. Sreejith · 2025
We give an active learning algorithm for deterministic one-counter automata (DOCA) 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 DOCA, even for the subclasses of deterministic real-time one-counter automata (DROCA) and visibly one-counter automata (VOCA), in the worst case, run in exponential time with respect to the size of the DOCA under learning. Furthermore, previous learning algorithms are "grey-box" algorithms relying on an additional query type - counter value query - where the teacher returns the counter value reached on reading a given word. In contrast, our algorithm is a "black-box" algorithm.It is known that the minimisation of VOCA is NP-hard. However, OL∗can be used for approximate minimisation of DOCA. In this case, the output size is at most polynomial in the size of a minimal DOCA.