In recognition systems, reject options are usually introduced to reduce error rates for general classifiers. For taking this option, there is a trade-off relationship between error rates and reject rates and it is required to optimize the trade-off. Conventional methods have implicit assumptions that the error rates are zero after the rejection; however, real systems have their own error rates even after the rejection. In this paper, we propose a generalized reject model that can introduce error rates after rejection. This model can handle variety of systems with plural classifiers and thresholds. Also, we can optimize the error-reject trade-off by defining and minimizing a cost function of the model. Finally, experimental results show effectiveness of the proposed model by applying it to data entry systems.

In the previous paper on a tree-to-tree editing problem some errors were included. This letter describes the corrected definition of a structure preserving mapping between rooted and ordered trees and a computing method of the tree distance based on the mapping.

Proposes a distance measure between unrooted and unordered trees based on the strongly structure-preserving mapping (SSPM). SSPM can make correspondences between the vertices of similar substructures of given structures more strictly than previously proposed mappings. The time complexity of computing the distance between trees T/sub a/ and T/sub b/ is O(m/sub bsup 3/N/sub a/N/sub b/), where N/sub a/ and N/sub b/ are the number of vertices in trees T/sub a/ and T/sub b/, respectively; m/sub a/ and m/sub b/ are the maximum degrees of a vertex in T/sub a/ and T/sub b/, respectively; and m/sub aspl les/m/sub b/ is assumed. The space complexity of the method is O(N/sub a/N/sub b/).>

A method for stabilizing iterative image reconstruction techniques has been developed for improving the image quality of position emission tomography. A damping matrix is introduced, which suppresses noisy correction on a pixel-by-pixel basis, depending on the statistical precision of the iterative correction. The precision is evaluated by comparing a certain number of correction submatrices, each of which is formed from a subset of the projection data. Simulation studies showed that statistical noise is effectively suppressed, while the image of the source object is reconstructed with high resolution, as long as the signal level is higher than the local noise level. In the application to the MLE (maximum likelihood estimator), the minimum RMS error of the image was reduced to 84% for 500 k total counts, and the RMS error increased more slowly with further iterations as compared with the simple MLE. The method was also applied to the FIR (filtered iterative reconstruction) algorithm, and the images were found to be better than those obtained by the convolution backprojection method.

Two dictionary-based methods for correction of strings with errors are proposed. The first method uses a hierarchical file based on two kinds of class name expression. The second method applies a hashing technique to methods already proposed. The correction rates of the two methods are the same. An experiment using 3782 words of length 6 characters shows that the computing time of the second method is 0.8% of that of the weighted Levenshtein distance method in the case of a substitution recovery.>

This paper describes the computing alogrithms for the tree distance based on the structure preserving mapping. The distance is defined as the minimum sum of the weights of edit operations needed to transform tree Tα to tree Tβ under restriction of the structure preserving mapping. The edit operations allow substituting a vertex of a tree to another, deleting a vertex of a tree and inserting a vertex to a tree. Proposed algorithms determine the distance between Tα and Tβ in time O(NαNβLα) or O(NαNβLβ), and in space O(NαNβ), where Nα, Nβ, Lα and Lβ are the number of vertices of Tα, Tβ, the number of’ leaves of Tα and Tβ, respectively. The time complexity is close to the unapproachable lowest bound O(NαNβ). Improved algorithms are presented. This tree distance can be applied to any problems including pattern recognition, syntactic tree comparison and classification, and tree comparison whose structures are important in structure preserving mapping.

This paper describes a high speed string correction method using a hierarchical file. After reviewing a string correction method based on the Levenshtein distance, a hierarchical file construction method is introduced. A multistage string correction method using this file is proposed. The lower bound of computational complexity is estimated, and it is shown that a multistage method using a special type of a hierarchical file can reduce computational labor greatly. The larger the number of strings considered is, the more efficient the method becomes. The results of computer simulations on 5374 phoneme sequences using two and three stage correction methods are stated. The condition for a multistage string correction method to obtain higher correction rates than an ordinary dictionary method is included.

In our earlier paper1 we proposed an algorithm S for error-correcting parsing of formal languages. It is found recently that two additional CS conditions and a routine for detecting infinite loop are required for the algorithm S.

This paper describes error-correcting parsers for context-free and context-sensitive languages with substitution, insertion and deletion errors. Furthermore, it is shown that the ability of the proposed parsers can be expressed in terms of the weighted Levenshtein metric.

In this paper we propose a new method for correcting garbled words based on Levenshtein distance and weighted Levenshtein distance. We can correct not only substitution errors, but also insertion errors and deletion errors by this method. According to the results of simulation on nearly 1000 high occurrence English words, higher error correcting rates can be achieved by this method than any other method tried to date. Hardware realization of the method is possible, though it is rather complicated.

Block codes are constructed that are capable of simultaneously correctingeor fewer synchronization errors intconsecutive words, for anyt \geq 2e + 1, andsor fewer substitution errors in eachoft - 1or fewer of these words under the condition that there exists at least one ungarbled word among thetconsecutive words. Also, some new extensions of theA_{n}^{c}codes of Calabi and Hartnett are presented under the condition that synchronization and substitution errors do not coexist in thetconsecutive words.