SUPER-PATTERN MATCHING

Some recognition problems are either too complex or too ambiguous to b e expressed as a simple pattern matching problem using a sequence or r egular expression pattern. In these cases, a richer environment is nee ded to describe the ''patterns'' and recognition techniques used to pe rform the recognition. Some researchers have turned to artificial-inte lligence techniques and multistep matching approaches for the problems of gene recognition [5], [7], [18], protein structure recognition [13 ], and on-line character recognition [6]. This paper presents a class of problems which involve finding matches to ''patterns of patterns,'' or super-patterns, given solutions to the lower-level patterns. The e xpressiveness of this problem class rivals that of traditional artific ial-intelligence characterizations, and yet polynomial-time algorithms are described for each problem in the class.