A typical syntactic pattern recognition (PR) problem involves comparing a noisy string with every element of a dictionary, H. The problem of classification can be greatly simplified if the dictionary is partitioned into a set of subdictionaries. In this case, the classification can be hierarchical - the noisy string is first compared to a representative element of each subdictionary and the closest match within the subdictionary is subsequently located. Indeed, the entire problem of subdividing a set of strings into subsets where each subset contains "similar" 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 solution to string taxonomy. The solution utilizes the Object Migrating Automaton (OMA) the power of which in clustering objects and images [33], [35] has been reported. The power of the scheme for string taxonomy has been demonstrated using random strings and garbled versions of string representations of fragments of macromolecules.

Additional Metadata
Keywords Dictionary partitioning, String clustering, String taxonomy, Syntactic pattern recognition
Persistent URL dx.doi.org/10.1109/3477.558849
Journal IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Oommen, J, & De St. Croix, E.V. (Edward V.). (1997). String taxonomy using learning automata. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 27(2), 354–365. doi:10.1109/3477.558849