Learning Deterministic One-Counter Automata in Polynomial Time

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<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∗</sup> 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<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∗</sup> 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.