|
Abstract : |
We consider a dual version of the DFA paclearning problem, in which concepts are strings over a fixed alphabet, examples are DFAs, and a string s represents the set of all DFAs that accept it. It is shown that solving this problem is as hard as learning log-depth boolean circuits, even if the example DFAs are are always acyclic, leveled, and of logarithmic level width. Thus under cryptographic assumptions the dual DFA learning problem is hard. This result implies the hardness of several other more natural learning problems, including learning the description logic Classic from subconcepts, and learning arity-two "determinate " functionfree Prolog clauses from ground clauses. The result also implies the hardness of two formal problems that are similar to problems studied in the area of "programming by demonstration ": learning straightline programs over a fixed operator set from input-output pairs, and learning straightline programs from inputoutput pairs traces, and "partial traces". 1, |
