Search

Discusses weighted deductive parsing and the problem of finding the derivation with the lowest weight. Discussion on weighted deductive parsing; Analysis of Knuth's algorithm to finding lowest-weighted derivations; Description of the algorithm by Viterbi.

We recall the notion of regular closure of classes of languages. We present two important results. The first result is that all languages which are in the regular closure of the class of deterministic (context-free) languages can be recognized in linear time. This is a nontrivial result, since this closure contains many inherently ambiguous languages. The second result is that the class of deterministic languages is contained in the closure of the class of deterministic languages with the prefix property or, stated in an equivalent way, all LR(k) languages are in the regular closure of the class of LR(0) languages. Key words: context-free languages; regular languages [ABSTRACT FROM AUTHOR]

Presents information on a study which improved the run-time efficiency of error repair algorithm by pruning configurations. Overview of error repair techniques; Phases of repair algorithm; Defectiveness of pruning; Discussion.