<p>There is a recent result on the polynomial pac-learnability of semilinear sets at LICS 2010: <a href="http://homepages.inf.ed.ac.uk/s0673998/papers/parikh.pdf" rel="nofollow">Parikh Images of Regular Languages: Complexity and Applications</a>. I guess this is not what you are looking for.</p>

<p>You should also have a look to the paper of Clark and Thollard: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.6808&amp;rep=rep1&amp;type=pdf" rel="nofollow">PAC-learnability of Probabilistic Deterministic Finite State Automata</a></p>

CC BY-SA 2.5
2010-10-14T07:59:45.777Z
Right, I am familiar with Clark and Thollard's paper -- but they make distribution assumptions so it's not true PAC...
Aryeh
CC BY-SA 2.5
2010-10-13T17:39:48.300Z
2010-10-13T17:39:48.300Z
Sylvain Peyronnet
<p>This paper gives a good hint about PAC-learning result for piecewise languages: <a href="http://www.cs.nyu.edu/~mohri/pub/ptl.pdf" rel="nofollow">Learning Linearly Separable Languages</a></p>

<p>The work of Clark &amp; Thollard was refined by Castro &amp; Gavalda in a way that can fit what you are looking for : <a href="http://www.lsi.upc.edu/~gavalda/icgi08proceedings.pdf" rel="nofollow">Towards feasible PAC-learning probabilistic deterministic finite automata</a></p>

<p>And this work is a good answer of the initial question: <a href="http://www.cs.yale.edu/homes/aspnes/papers/alt2012-proceedings.pdf" rel="nofollow">On the Learnability of Shuffle Ideals</a>. 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.</p>

CC BY-SA 3.0
2013-03-19T02:29:44.957Z
My guess is that @Aryeh is aware of at least two of these papers :)
Lev Reyzin
CC BY-SA 3.0
2013-03-23T21:37:59.350Z
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
CC BY-SA 3.0
2013-03-18T22:03:23.277Z
2013-03-18T23:34:06.330Z
2013-03-18T23:34:06.330Z
user14249
<p>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.</p>

<p>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?</p>

CC BY-SA 2.5
2010-10-13T15:02:50.173Z
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](http://cstheory.stackexchange.com/questions/1015/open-problems-on-the-frontiers-of-tcs/1105#1105)
Suresh Venkat
CC BY-SA 2.5
2010-10-13T19:13:59.580Z
this question might also be relevant: http://cstheory.stackexchange.com/questions/1854
Lev Reyzin
<automata-theory><machine-learning><lg.learning>
Are there families of formal languages known to be truly PAC learnable?
Aryeh
# Are there families of formal languages known to be truly PAC learnable?

(Asked by: username_0 on 2010-10-13)

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?

**Tags:** automata-theory, machine-learning, lg.learning
> **Comments:**
> **username_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](http://cstheory.stackexchange.com/questions/1015/open-problems-on-the-frontiers-of-tcs/1105#1105)  
> **username_2**: this question might also be relevant: http://cstheory.stackexchange.com/questions/1854  

---

## 2 answers

### Answer by username_3 on 2010-10-13. Score: 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](http://homepages.inf.ed.ac.uk/s0673998/papers/parikh.pdf). 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.6808&rep=rep1&type=pdf)

> **Comments:**
> **username_0**: Right, I am familiar with Clark and Thollard's paper -- but they make distribution assumptions so it's not true PAC...  

---

### Answer by username_4 on 2013-03-18. Score: 1

This paper gives a good hint about PAC-learning result for piecewise languages: [Learning Linearly Separable Languages](http://www.cs.nyu.edu/~mohri/pub/ptl.pdf)

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](http://www.lsi.upc.edu/~gavalda/icgi08proceedings.pdf)

And this work is a good answer of the initial question: [On the Learnability of Shuffle Ideals](http://www.cs.yale.edu/homes/aspnes/papers/alt2012-proceedings.pdf). 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.

> **Comments:**
> **username_2**: My guess is that @Aryeh is aware of at least two of these papers :)  
> **username_0**: 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.  

---

