{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:57:20Z","timestamp":1776891440853,"version":"3.51.2"},"reference-count":21,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2017,1,17]],"date-time":"2017-01-17T00:00:00Z","timestamp":1484611200000},"content-version":"unspecified","delay-in-days":16,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2017]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We present an algorithm which, for given\n                    <jats:italic>n<\/jats:italic>\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                    <jats:italic>n<\/jats:italic>\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\n                    <jats:italic>SK<\/jats:italic>\n                    -combinators reducing in\n                    <jats:italic>n<\/jats:italic>\n                    normal-order reduction steps. Finally, we investigate the size of generated grammars giving a primitive recursive upper bound.\n                  <\/jats:p>","DOI":"10.1017\/s0956796816000332","type":"journal-article","created":{"date-parts":[[2017,1,17]],"date-time":"2017-01-17T04:15:59Z","timestamp":1484626559000},"source":"Crossref","is-referenced-by-count":2,"title":["Normal-order reduction grammars"],"prefix":"10.46298","volume":"27","author":[{"given":"MACIEJ","family":"BENDKOWSKI","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2017,1,17]]},"reference":[{"key":"S0956796816000332_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49192-8_15"},{"key":"S0956796816000332_ref9","doi-asserted-by":"publisher","DOI":"10.2307\/2370619"},{"key":"S0956796816000332_ref21","unstructured":"Wolfram Research, Inc. (2015) Mathematica Version 10.3. Champaign, Illinois."},{"key":"S0956796816000332_ref20","doi-asserted-by":"publisher","DOI":"10.1145\/15042.15053"},{"key":"S0956796816000332_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796815000271"},{"key":"S0956796816000332_ref17","volume-title":"Proceedings of the 6th International Workshop on Automation of Software Test, AST 2011","author":"Pa\u0142ka","year":"2011"},{"key":"S0956796816000332_ref15","first-page":"594","volume-title":"J. Funct. Program","volume":"23","author":"Grygiel","year":"2013"},{"key":"S0956796816000332_ref14","first-page":"40:1","volume-title":"Proceedings of 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016","author":"Gittenberger","year":"2016"},{"key":"S0956796816000332_ref8","unstructured":"Comon H. , Dauchet M. , Gilleron R. , L\u00f6ding C. , Jacquemard F. , Lugiez D. , Tison S. & Tommasi M. (2007) Tree Automata Techniques and Applications. Available at: http:\/\/www.grappa.univ-lille3.fr\/tata.release October, 12th 2007."},{"key":"S0956796816000332_ref10","volume-title":"Combinatory Logic","author":"Curry","year":"1958"},{"key":"S0956796816000332_ref2","volume-title":"The Lambda Calculus, Its Syntax and Semantics","author":"Barendregt","year":"1984"},{"key":"S0956796816000332_ref4","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/978-3-319-17142-5_7","volume-title":"Theory and Applications of Models of Computation","author":"Bendkowski","year":"2015"},{"key":"S0956796816000332_ref19","first-page":"31","article-title":"A new implementation technique for applicative languages","volume":"9","author":"Turner","year":"1979","journal-title":"Softw.: Pract. Exp."},{"key":"S0956796816000332_ref6","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(4:3)2013"},{"key":"S0956796816000332_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006315"},{"key":"S0956796816000332_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448013"},{"key":"S0956796816000332_ref7","unstructured":"Bodini O. , Gardy D. , Gittenberger B. & Go\u0142ebiewski Z. (2015) On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height. arXiv:1510.01167."},{"key":"S0956796816000332_ref11","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(1:2)2013"},{"key":"S0956796816000332_ref1","volume-title":"Handbook of Mathematical Functions, with Formulas, Graphs, and Mathematical Tables","author":"Abramowitz","year":"1972"},{"key":"S0956796816000332_ref3","unstructured":"Bendkowski M. (2016) Normal-Order Reduction Grammars\u2013Haskell Implementation. Available at: https:\/\/github.com\/maciej-bendkowski\/normal-order-reduction-grammars, Last accessed 03.01.2017."},{"key":"S0956796816000332_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796816000332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:19:53Z","timestamp":1776889193000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796816000332\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"references-count":21,"alternative-id":["S0956796816000332"],"URL":"https:\/\/doi.org\/10.1017\/s0956796816000332","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"article-number":"e6"}}