STRING TAXONOMY USING LEARNING AUTOMATA

A typical syntactic pattern recognition (PR) problem involves comparin g a noisy string with every element of a dictionary, H. The problem of classification can be greatly simplified if the dictionary is partiti oned into a set of subdictionaries. In this case, the classification c an be hierarchical-the noisy string is first compared to a representat ive element of each subdictionary and the closest match within the sub dictionary is subsequently located, Indeed, the entire problem of subd ividing a set of strings into subsets where each subset contains ''sim ilar'' strings has been referred to as the ''String Taxonomy Problem.' ' To our knowledge there is no reported solution to this problem (see footnote 2). In this paper we present a learning-automaton based solut ion to string taxonomy, The solution utilizes the Object Migrating Aut omaton (OMA) the power of which in clustering objects and images [33], [35] has been reported, The power of the scheme for string taxonomy h as been demonstrated using random strings and garbled versions of stri ng representations of fragments of macromolecules.