Polynomial-Time Algorithms for Learning Typed Pattern Languages

This article proposes polynomial-time algorithms for learning typed pattern languages—formal languages that are generated by patterns consisting of terminal symbols and typed variables. A string is generated by a typed pattern by substituting all variables with strings of terminal symbols that belong to the corresponding types.

The algorithms presented consitute non-trivial generalizations of Lange and Wiehagen’s efficient algorithm for learning patterns in which variables are not typed. This is achieved by defining

type witnesses

to impose structural conditions on the types used in the patterns. It is shown that Lange and Wiehagen’s algorithm implicitly uses a special case of type witnesses. Moreover, the type witnesses for a typed pattern form characteristic sets whose size is linear in the length of the pattern; our algorithm, when processing any set of positive data containing such a characteristic set, will always generate a typed pattern equivalent to the target pattern. Thus our algorithms are of relevance to the area of grammatical inference, in which such characteristic sets are typically studied.