Stochastic Error-Correcting Syntax Analysis for Recognition of Noisy Patterns

1 December 1977

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-26 (12) , 1268-1276
https://doi.org/10.1109/tc.1977.1674788

Abstract

In this paper, a probabilistic model for error-correcting parsing with substitution, insertion, and deletion errors is introduced. The formulation of maximum-likelihood error-correcting parser (MLECP) by incorporating the noise model into stochastic grammars is also presented. The use of stochastic error-correcting parsers for recognition of noisy and/or distorted patterns results in a process of high accuracy, but with low efficiency. In order to make the syntax analysis more practically feasible, it is proposed to use a sequential classification method for noisy strings processing. Computation results based on the classification experiments of noisy patterns for both nonsequential and sequential error-correcting parsers are presented.

Keywords

This publication has 12 references indexed in Scilit:

Language Correction Using Probabilistic Grammars
IEEE Transactions on Computers, 1976
Practical syntactic error recovery
Communications of the ACM, 1975
Sequential classification of strings generated by SCFG's
International Journal of Parallel Programming, 1975
Decoding for channels with insertions, deletions, and substitutions with applications to speech recognition
IEEE Transactions on Information Theory, 1975
Syntactic Recognition of Imperfectly Specified Patterns
IEEE Transactions on Computers, 1975
Stochastic languages for picture analysis
Computer Graphics and Image Processing, 1973
A Stochastic Syntax Analysis Procedure and Its Application to Pattern Classification
IEEE Transactions on Computers, 1972
An efficient context-free parsing algorithm
Communications of the ACM, 1970
PL360, a Programming Language for the 360 Computers
Journal of the ACM, 1968
An error-correcting parse algorithm
Communications of the ACM, 1963