TY - GEN

T1 - REDUCTIONS AMONG PREDICTION PROBLEMS

T2 - ON THE DIFFICULTY OF PREDICTING AUTOMATA.

AU - Pitt, Leonard

AU - Warmuth, Manfred K.

PY - 1988

Y1 - 1988

N2 - Given examples of words accepted and rejected by an unknown automaton, the question of whether there is an algorithm that in a feasible amount of time will learn to predict which words will be accepted by the automaton is examined. A notion of prediction-preserving reducibility is developed, and it is shown that if DFAs are predictable, then so are all languages in logspace. In particular, the predictability of DFAs implies the predictability of all Boolean formulas. Similar results hold for NFAs and PDAs (or CFGs). Relationships between the complexity of the membership problem for a class of automata and the complexity of the prediction problem are obtained. Examples are give of prediction problems in which predictability implies the predictability of all langages in P. Assuming the existence of one-way functions, it follows that these problems are not predictable, even in an extremely weak sense.

AB - Given examples of words accepted and rejected by an unknown automaton, the question of whether there is an algorithm that in a feasible amount of time will learn to predict which words will be accepted by the automaton is examined. A notion of prediction-preserving reducibility is developed, and it is shown that if DFAs are predictable, then so are all languages in logspace. In particular, the predictability of DFAs implies the predictability of all Boolean formulas. Similar results hold for NFAs and PDAs (or CFGs). Relationships between the complexity of the membership problem for a class of automata and the complexity of the prediction problem are obtained. Examples are give of prediction problems in which predictability implies the predictability of all langages in P. Assuming the existence of one-way functions, it follows that these problems are not predictable, even in an extremely weak sense.

UR - http://www.scopus.com/inward/record.url?scp=0023672752&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023672752&partnerID=8YFLogxK

U2 - 10.1109/sct.1988.5263

DO - 10.1109/sct.1988.5263

M3 - Conference contribution

AN - SCOPUS:0023672752

SN - 0818607947

SN - 9780818607943

SP - 60

EP - 69

BT - Unknown Host Publication Title

PB - IEEE

ER -