Export Reviews, Discussions, Author Feedback and Meta-Reviews

This paper studies the problem of learning shffle ideals in the PAC-learning model under some simple distributions such as product distribution, or distributions generated by Markov chains. A shuffle ideal is a particularly simple type of regular language. Given alphabet \Sigma, and a string u (u_1, …, u_L) the prime shuffle ideal generated by u is the set of strings obtained by inserting any strings s_0, …, s_L in u to get s_0 u_1 s_1 … u_L s_L. The shuffle ideal is a more general class of regular languages where instead of a string u we consider strings in a product set U U_1 \times … \times U_L where U_i \subseteq \Sigma and take the union of the prime shuffle ideals generated by strings in U. The problem of learning regular languages has many applications.