9

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?

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Aryeh
  • 10,494
  • 1
  • 27
  • 51
  • 1
    have you looked at the related questions: http://cstheory.stackexchange.com/questions/1401/pac-learning-boolean-conjunctions and http://cstheory.stackexchange.com/questions/153/computational-query-complexity-of-sq-learning, as well as this answer – Suresh Venkat Oct 13 '10 at 15:02
  • 1
    this question might also be relevant: http://cstheory.stackexchange.com/questions/1854 – Lev Reyzin Oct 13 '10 at 19:13

2 Answers2

4

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

Sylvain Peyronnet
  • 3,063
  • 1
  • 18
  • 29
  • 2
    Right, I am familiar with Clark and Thollard's paper -- but they make distribution assumptions so it's not true PAC... – Aryeh Oct 14 '10 at 07:59
1

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.

user14249
  • 11
  • 2
  • 3
    My guess is that @Aryeh is aware of at least two of these papers :) – Lev Reyzin Mar 19 '13 at 02:29
  • 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. – Aryeh Mar 23 '13 at 21:37