I specifically mean language families that admit arbitrarily long strings -- not conjunctions over n bits or decision lists or any other "simple" language contained in {0,1}^n.

I am asking about "automata-theoretic" regular languages as opposed to "logic-theoretic" ones: something like the piecewise testable languages, start-height-zero languages, locally testable languages, that sort of thing. The relevant complexity parameter n is the size of the minimal accepting DFA. So, succinctly put: is there an interesting family of n-state DFAs that is known to be efficiently PAC learnable?


There is a recent result on the polynomial pac-learnability of semilinear sets at LICS 2010: Parikh Images of Regular Languages: Complexity and Applications. I guess this is not what you are looking for.

You should also have a look to the paper of Clark and Thollard: PAC-learnability of Probabilistic Deterministic Finite State Automata

  • 2
    $\begingroup$ Right, I am familiar with Clark and Thollard's paper -- but they make distribution assumptions so it's not true PAC... $\endgroup$ – Aryeh Oct 14 '10 at 7:59

This paper gives a good hint about PAC-learning result for piecewise languages: Learning Linearly Separable Languages

The work of Clark & Thollard was refined by Castro & Gavalda in a way that can fit what you are looking for : Towards feasible PAC-learning probabilistic deterministic finite automata

And this work is a good answer of the initial question: On the Learnability of Shuffle Ideals. One of the authors is likely to be the same person who formerly asked the question here, but I found this page by working on that problem and have just found this paper: it might help other to have this reference.

  • 3
    $\begingroup$ My guess is that @Aryeh is aware of at least two of these papers :) $\endgroup$ – Lev Reyzin Mar 19 '13 at 2:29
  • $\begingroup$ Indeed, I vaguely recall co-authoring #1 and #3... None of these give positive PAC results of the type I asked about. In #1, we require a margin, which is a distribution-dependent quantity. In #3, we give strong negative results. $\endgroup$ – Aryeh Mar 23 '13 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.