Edwin Henry Spanier (1921-1996)

This paper presents a major and difficult decidability result in grammar form theory. It is proved that, given two arbitrary context-free grammar forms, it is decidable whether or not the family of one is contained in the other. This leads immediately to the decidability of the equality of two context-free grammar forms." This result is based on an earlier paper, "A prime decomposition theorem for grammatical families ", in which the same authors obtained a prime decomposition for formal language families, closely analogous in form to the decomposition of whole numbers into prime factors. Spanier's publications, as were his lectures, are characterized by unusual lucidity and precision and an even rarer quality of naturalness and simplicity. No matter how complex the subject, at the end the reader feels the theorems are the right ones, the hypotheses natural, and the methods as simple as possible. Ed Spanier will be remembered as a gifted researcher, an inspiring teacher, an able administrator, and as a modest, friendly, wise, and helpful colleague