A New Algorithm for Pattern Matching and Unification

A new algorithm for pattern matching and unification in the form of natural language is proposed in this paper. This algorithm is put forwarded based on the method of enumeration which includes six sequential steps: two patterns´ prefix (postfix) are both constant; one pattern´s prefix (postfix) is constant and the other pattern´s prefix (postfix) is variable; two patterns´ prefix (postfix) are both variable. Comparing with other related algorithms, the main improvement of this algorithm is that it process patterns in the form of natural language instead of formal patterns. This algorithm´s correctness is strictly proved and its time complexity is linear. The experiment proved that this algorithm can be used to judge whether two patterns are match and to unify two patterns to be one pattern if they are match. This algorithm can be widely used in reasoning which is an important aspect of AI (artificial intelligence) and computational linguistics.