Technical Reports

The ICICS/CS Reading Room

UBC CS TR-77-04 Summary

A New Notation for Derivations, June 1977 J. L Baker

Ordered directed graphs (generalizing ordered trees) are defined and used in a new formal definition of grammatical derivation. The latter is shown equivalent to the currently accepted definition. The new scheme is illustrated by detailed proofs of two familiar results: the equivalence of the notions ``context-sensitive'' and ``length-nondecreasing'' as applied to grammars, and an important lemma in the theory of deterministic context-free parsing.

If you have any questions or comments regarding this page please send mail to