Normal-order reduction grammars*. (17th January 2017)

• Record Type: Journal Article
• Authors: BENDKOWSKI, MACIEJ
• Is Part Of: Journal of functional programming. Volume 27(2017)
• Publication Date: 2017-01-17
• Subjects: Functional programming (Computer science) -- Periodicals
• DOI: 10.1017/S0956796816000332
• Languages: English
• ISSNs: 0956-7968

Abstract

Abstract: We present an algorithm which, for given n, generates an unambiguous regular tree grammar defining the set of combinatory logic terms, over the set {S, K} of primitive combinators, requiring exactly n normal-order reduction steps to normalize. As a consequence of Curry and Feys's standardization theorem, our reduction grammars form a complete syntactic characterization of normalizing combinatory logic terms. Using them, we provide a recursive method of constructing ordinary generating functions counting the number of SK -combinators reducing in n normal-order reduction steps. Finally, we investigate the size of generated grammars giving a primitive recursive upper bound.