Efficient Learning of One-Variable Pattern Languages from Positive Data

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. Descriptive patterns are a key concept for inductive inference of pattern languages. A pattern ß is descriptive for a given sample if the sample is contained in the language L(ß) generated by ß and no other pattern having this property generates a proper subset of the language L(ß). The best previously known algorithm for computing descriptive one-variable patterns requires time O(n 4 log n), where n is the size of the sample. We present a simpler and more efficient algorithm solving the same problem in time O(n 2 log n). In addition, we give a parallel version of this algorithm that requires time O(log n) and O(n 3 = log n) processors on an EREW-PRAM. Previously, no parallel algorithm was known for this problem. Using a modified version of the seque..