TY - GEN
T1 - LEARNING ONE-COUNTER LANGUAGES IN POLYNOMIAL TIME.
AU - Berman, Piotr
AU - Roos, Robert
PY - 1987
Y1 - 1987
N2 - It is demonstrated that the class of languages accepted by deterministic one-counter machines, or DOCAs (a natural subset of the context-free languages), is learnable in polynomial time. The learning protocol is based on D. Angluin's concept (1986) of a minimally adequate teacher who can answer membership queries about a concept and provide counterexamples to incorrect hypothesized concepts. It is also demonstrated that the problem of testing DOCAs for equivalence may be solved in polynomial time.
AB - It is demonstrated that the class of languages accepted by deterministic one-counter machines, or DOCAs (a natural subset of the context-free languages), is learnable in polynomial time. The learning protocol is based on D. Angluin's concept (1986) of a minimally adequate teacher who can answer membership queries about a concept and provide counterexamples to incorrect hypothesized concepts. It is also demonstrated that the problem of testing DOCAs for equivalence may be solved in polynomial time.
UR - http://www.scopus.com/inward/record.url?scp=0023538326&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0023538326&partnerID=8YFLogxK
U2 - 10.1109/sfcs.1987.36
DO - 10.1109/sfcs.1987.36
M3 - Conference contribution
AN - SCOPUS:0023538326
SN - 0818608072
SN - 9780818608070
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 61
EP - 67
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - IEEE
ER -