An Automatically Compilable Recognition Network For Structured Patterns

Abstract

A new method for efficient recoanilion of aeneral relational structures is described and compared with existing methods. Patterns to be recognized are defined by templates consisting of a set of predicate calculus relations. Productions are representable by associating actions with templates. A network for recognizing occurrences of any of the template patterns in data may be automatically compiled. The compiled network is economical in the sense that conjunctive products (subsets) of relations common to several templates are represented in and computed by the network only once. The recognition network operates in a bottom-up fashion, in which all possibilities for pattern matches are evaluated simultaneously. The distribution of the recognition process throughout the network means that H can readily be decomposed into par aile I processes for use on a multiprocessor machine. The method is expected to be especially useful in errorful domains (!!.:&:, vision, speech) where par.llel treatment of alternative hypotheses is desired. The network is illustrated with an example from the current syntax and semantics module in the Hearsay II speech understandina system.