Learning Deterministic One-Counter Automata in Polynomial Time

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 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 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.