The Dual DFA Learning Problem: Hardness Results for Programming by Demonstration and Learning First-Order Representations (Extended Abstract)
Abstract
) William W. Cohen AT&T Laboratories, 600 Mountain Avenue Murray Hill, NJ 07974 [email protected] 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 ...
Cite
Text
Cohen. "The Dual DFA Learning Problem: Hardness Results for Programming by Demonstration and Learning First-Order Representations (Extended Abstract)." Annual Conference on Computational Learning Theory, 1996. doi:10.1145/238061.238066Markdown
[Cohen. "The Dual DFA Learning Problem: Hardness Results for Programming by Demonstration and Learning First-Order Representations (Extended Abstract)." Annual Conference on Computational Learning Theory, 1996.](https://mlanthology.org/colt/1996/cohen1996colt-dual/) doi:10.1145/238061.238066BibTeX
@inproceedings{cohen1996colt-dual,
title = {{The Dual DFA Learning Problem: Hardness Results for Programming by Demonstration and Learning First-Order Representations (Extended Abstract)}},
author = {Cohen, William W.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1996},
pages = {29-40},
doi = {10.1145/238061.238066},
url = {https://mlanthology.org/colt/1996/cohen1996colt-dual/}
}