[prev] [prev-tail] [tail] [up]
The hierarchy of grammars in Section 1.2 is due to Chomsky (1959). In the classification
Chomsky (1959) used an equivalent class of grammars, called context-sensitive
grammars, instead of the Type 1 grammars. Type 1 grammars are due to Kuroda
(1964). Harrison (1978) provides an extensive treatment for grammars and formal
languages.
Nondeterminism was introduced in Rabin and Scott (1959) and applied to programs in
Floyd (1967).
The study of undecidability originated in Turing (1936) and Church (1936). Hilbert's
tenth problem is due to Hilbert (1901), and its undecidability to Matijasevic (1970). LOOP
programs and the undecidability of the equivalence problem for them are due to Ritchie
(1963) and Meyer and Ritchie (1967).
[prev] [prev-tail] [front] [up]