Polynomial learnability of formal languages
Naoki Abe, Scott Weinstein · Scholarly Commons (University of Pennsylvania) · 1989
In this thesis, we investigate learnability of various subclasses of formal languages within the paradigm of pac-learnability. We present a nearly complete characterization of a host of polynomial learnability questions for subsets of $N\\sp m$ called 'semilinear sets', up to various hardness assumptions. In formal language terms, semilinear sets are exactly the class of 'letter counts' of regular languages. We show that a certain natural class of representations for unrestricted semilinear sets of dimension up to 2 ($m \\leq 2$) is polynomially learnable. We accompany this positive result by various hardness results. We also relate various learnability questions about classes of semilinear and related subsets of $N\\sp m$, by using a notion of reducibility among learning problems called 'prediction preserving reducibility' due to Pitt and Warmuth. On the positive side, we show that the entire class of permutation invariant deterministic finite state automata (PIDFA) is polynomially learnable, by reducing it to the learning problem for a restricted subclass of similinear sets for which we can directly exhibit a learning algorithm. On the negative side, we reduce the learning problem for DNF to various learning problems for classes of semilinear and related subsets of $N\\sp m$. We then apply similar proof techniques to show learnability and non-learnability results about some subclasses of formal grammars of more direct linguistic relevance.