From the enumeration of leftist trees [1] to the basics of parsing context-free grammars, Rainer Kemp (1949--2004) had a major role in shaping the grounding of the analysis of algorithms. His research in the theory of formal languages, namely, syntax analysis with a basis in combinatorial enumeration and asymptotic methods, is presented in a systematic and enriching way.

Kemp started his research career in his early twenties. Along with Philippe Flajolet and Helmut Prodinger, he was the founder of the analysis of algorithms community (AofA). The work of 30 years of research is summarized in this note, which refers to Kemp’s 53 publications, as well as some by other researchers. The paper shows the impact of Kemp’s results on computer science, and exposes his relevant work. For instance, Kemp’s approach to solving the open problem of the enumeration of leftist trees, provided by Knuth in his book [2], led to the concept of simply generated trees.

The paper is divided into 11 categories, with mathematical emphasis on registers, arithmetic expressions, leftist trees, stack size and height, formal languages and enumeration, additive weight of trees, binary search trees, and parsing. The representation of Kemp’s work with Speckenmeyer on the “Boolean formula in conjunctive normal form” [3], and the comparison to the original work of de Bruijn, Knuth, and Rice [4] on determining the stack height of a binary search tree make the paper more relevant.

Finally, the research on Kemp’s work represents a hot reference for any researcher in theoretical computer science, applied mathematics, operations research, or computational complexity theory, in relation to areas such as artificial intelligence, optimization, algorithms theory, computer architecture and memory registers, and stack and data structure.