A Parallel Minimum Distance Error-Correcting Context-Free Parser

Giovanni Pighizzini

Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy

Abstract

In this paper we present the first parallel minimum distance error--correcting parser for context--free languages. The error correction is performed considering three kinds of syntax errors: the mutation of a symbol in another incorrect symbol, the insertion of an extraneous symbol and the deletion of a symbol. Our algorithm has the same parallel complexity of other well--known non--correcting context--free parsers such as developed by Ruzzo (1980) and Gibbons and Rytter (1988). Further, with respect to these algorithms it has the advantage of working with every context--free grammar and not just with grammars in Chomsky Normal Form. The algorithm is developed using dynamic programming techniques.

Download
Compressed postscript
Compressed dvi