Patent ID: 6684201
Filing Date: 2004-01-27
Classification: G06F,G06N

Abstract:
A computer-implemented method comprising:defining a set of reduced regular expressions for particular patterns in strings, wherein the set of reduced regular expressions are defined over a finite alphabet &Sgr; as follows: (1) âˆ€a&egr;&Sgr;: â€œaâ€  is a reduced regular expression and denotes a set {a}; â€œa+â€  is a reduced regular expression and denotes a positive closure of the set {a}; â€œa*â€  is a reduced regular expression and denotes a Kleene closure of the set {a}; â€œËœaâ€  is a reduced regular expression and denotes a set &Sgr;-a; â€œËœa+â€  is a reduced regular expression and denotes the positive closure of the set &Sgr;-a; â€œËœa*â€  is a reduced regular expression and denotes the Kleene closure of the set &Sgr;-a; (2) â€œ.â€  is a reduced regular expression denoting a set &Sgr;; (3) â€œ.+â€  is a reduced regular expression denoting the positive closure of the set &Sgr;; (4) â€œ.*â€  is a reduced regular expression denoting the Kleene closure of the set &Sgr;; and (5) if r and s are reduced regular expressions denoting languages R and S, respectively, then â€œrsâ€  is a reduced regular expression denoting a set RS; and learning, from a training set, a knowledge base that uses the reduced regular expressions to resolve ambiguity based upon the strings in which the ambiguity occurs.