By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Previous Article
Analysis and Synthesis of Sorting Algorithms
The problem of analyzing and synthesizing sorting algorithms is studied. That is, given a sorting algorithm we want to investigate how it works in a step-by-step manner and consequently to assert that...
Next Article
Compatibility and Complexity of Refinements of the Resolution Principle
This paper studies a number of logically complete search strategies (refinements) for improving the performance of automatic theorem-proving programs based on the resolution principle. These strategie...

You are not logged in to this journal. Log in

A Minimum Distance Error-Correcting Parser for Context-Free Languages

SIAM J. Comput. Volume 1, Issue 4, pp. 305-312 (1972)

Issue Date: 1972
Buy This PDF   (US$25)
Download PDF (898 kB) View Cart
We assume three types of syntax errors can debase the sentences of a language generated by a context-free grammar: the replacement of a symbol by an incorrect symbol, the insertion of an extraneous symbol, or the deletion of a symbol. We present an algorithm that will parse any input string to completion finding the fewest possible number of errors. On a random access computer the algorithm requires time proportional to the cube of the length of the input. ©1972 Society for Industrial and Applied Mathematics
History: Received 1972-06-06
Permalink: http://dx.doi.org/10.1137/0201022

KEYWORDS and AMS

PUBLICATION DATA

ISSN:
0097-5397 (print)   1095-7111 (online)
Publisher:
AIP is a member of CrossRef SIAM

REFERENCES (10)
For access to fully linked references, you need to log in. For access to fully linked references, you need to Log in.

CITING ARTICLES
For access to citing articles, you need to log in.
For access to citing articles, you need to Log in.