context-free error analysis by evaluation of algebraic power series
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(n 3 ) steps. The closure of algebraic power series under sequential transduction yields a generous class of reasonable error measures for which optimal analysis is O(n 3 ). Included is minimizing the number of symbol insertions, deletions and/or replacements needed for correction, a special case which has been studied separately.
errors analysis evaluation power optimality language general recognition algorithm class measurement correctness case context