Learning One-Counter Languages in Polynomial .Time (Extended Abstract)
Piotr Berman, Robert S. Roos · Foundations of Computer Science · 1987
We demonstrate that the class of languages accepted by deterministic one-counter machines, or DOCAs (a natural subset of the context-free languages), is learnable in poly nomial time. Our learning protocol is based upon Angluin's concept of a minimally adequate teacher who can answer membership queries about a concept and pro vide counterexamples to incorrect hypothesized concepts. We also demonstrate that the problem of testing DOCAs for equivalence may be solved in polynomial time, answer ing a question posed by Valiant and Paterson.