Error-Correcting Parsers for Formal Languages
- 1 July 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-27 (7) , 605-616
- https://doi.org/10.1109/tc.1978.1675160
Abstract
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.Keywords
This publication has 9 references indexed in Scilit:
- A Method for the Correction of Garbled Words Based on the Levenshtein MetricIEEE Transactions on Computers, 1976
- Maximum-likelihood syntactic decodingIEEE Transactions on Information Theory, 1975
- Stochastic Syntactic Decoding for Pattern ClassificationIEEE Transactions on Computers, 1975
- Automatic correction of syntax-errors in programming languagesActa Informatica, 1975
- Errors in Regular LanguagesIEEE Transactions on Computers, 1974
- Sequential syntactical decodingInternational Journal of Parallel Programming, 1974
- A Minimum Distance Error-Correcting Parser for Context-Free LanguagesSIAM Journal on Computing, 1972
- Error detection in formal languagesJournal of Computer and System Sciences, 1970
- Classes of languages and linear-bounded automataInformation and Control, 1964