Context-free error analysis by evaluation of algebraic power series

ABSTRACT

Optimal error analysis with respect to a context-free language may be viewed as the evaluation of an algebraic power series. By generalization of the nodal span context-free recognition algorithm, any algebraic power series is computable in O(n3) steps. The closure of algebraic power series under sequential transduction yields a generous class of reasonable error measures for which optimal analysis is O(n3). Included is minimizing the number of symbol insertions, deletions and/or replacements needed for correction, a special case which has been studied separately.

REFERENCES

• 1: Shamir, Eliahu, "A Representation Theorem for Algebraic and Context-Free Power Series in Noncommuting Variables," Information and Control (11), 1967, 239-254.
• 2: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 3: Teitelbaum, Ray, "Diagnosis of Syntax Errors," February 1972, unpublished note.
• 4: Lyon, Gordon, "Least-errors Recognition of Mutated Context Free Sentences in Time n3 log n," Proc. of the Sixth Annual Princeton Conf. on Info. Sci. and Sys., March 1972.
• 5: Aho, A. V. and T. G. Peterson, "A Minimum Distance Error Correcting Parser for Context Free Languages," SIAM J. on Computing, Dec. 1972.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Algebraic language theory

General Terms:
Algorithms, Theory