9
$\begingroup$

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?

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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
    Commented Oct 14, 2010 at 7:59
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ My guess is that @Aryeh is aware of at least two of these papers :) $\endgroup$
    – Lev Reyzin ♦
    Commented Mar 19, 2013 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
    Commented Mar 23, 2013 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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