Dana Angluin, James Aspnes, and Aryeh Kontorovich. On the learnability of shuffle ideals. Twenty-Third International Converence on Algorithmic Learning Theory, October 2012, pp. 111–123. Submitted to Journal of Machine Learning Research.
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.
@inproceedings{AngluinAK2012,
author = {Dana Angluin and James Aspnes and Aryeh Kontorovich},
title = {On the learnability of shuffle ideals},
month = oct,
year = 2012,
booktitle = {Algorithmic Learning Theory, 23rd International Conference,
ALT 2012, Lyon, France, October 29-31, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
volume = 7568,
pages = {111--123}
}