On the learnability of shuffle ideals

Dana Angluin, James Aspnes, Sarah Eisenstat, and Aryeh Kontorovich. On the learnability of shuffle ideals. Journal of Machine Learning Research, 14(Jun):1513–1531, June 2013. An earlier version appeared in Twenty-Third International Converence on Algorithmic Learning Theory, October 2012, pp. 111–123.


PAC learning unrestricted regular languages is long known to be a very difficult problem. The class of shuffle ideals is a very restricted subclass of regular languages, where the shuffle ideal generated by a string u is the collection of all strings containing u as a subsequence. This fundamental language family is of theoretical interest in its own right and provides the building blocks for other important language families. Despite its apparent simplicity, the class of shuffle ideals appears quite difficult to learn. In particular, just as for unrestricted regular languages, the class is not properly PAC learnable in polynomial time if RP ≠ NP, and PAC learning the class improperly in polynomial time would imply polynomial time algorithms for certain fundamental problems in cryptography. In the positive direction, we give an efficient algorithm for properly learning shuffle ideas in the statistical query (and therefor also PAC) model under the uniform distribution.


  author  = {Dana Angluin and James Aspnes and Sarah Eisenstat and Aryeh Kontorovich},
  title   = {On the Learnability of Shuffle Ideals},
  journal = {Journal of Machine Learning Research},
  month = jun,
  year    = {2013},
  volume  = {14},
  number = {Jun},
  pages   = {1513--1531},
  url     = {http://jmlr.org/papers/v14/angluin13a.html}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page