{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T21:40:02Z","timestamp":1706650802058},"reference-count":16,"publisher":"Duke University Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[1995,4,1]]},"DOI":"10.1305\/ndjfl\/1040248462","type":"journal-article","created":{"date-parts":[[2003,2,25]],"date-time":"2003-02-25T21:30:46Z","timestamp":1046208646000},"source":"Crossref","is-referenced-by-count":0,"title":["NP-Completeness of a Combinator Optimization Problem"],"prefix":"10.1215","volume":"36","author":[{"given":"M. S.","family":"Joy","sequence":"first","affiliation":[]},{"given":"V. J.","family":"Rayward-Smith","sequence":"additional","affiliation":[]}],"member":"73","reference":[{"key":"1","unstructured":"Barendregt, H. P., <i>The Lambda Calculus, its Syntax and Semantics<\/i>, North-Holland, Amsterdam, 1981. Zbl 0467.03010 MR 83b:03016"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Batini, C., and A. Pettorossi, <i>Some Properties of Subbases in Weak Combinatory Logic<\/i>, Report 75\u201304, Istituto di Automatica, Roma, 1975.","DOI":"10.1007\/BFb0029533"},{"key":"3","doi-asserted-by":"crossref","unstructured":"Clarke, T. J. W., P. J. S. Gladstone, C. D. MacLean and A. C. Norman, \u201cSKIM\u2013-The S,K,I Reduction Machine\u201d in <i>Conference Record of the 1980 LISP Conference<\/i>, Stanford University, 1980.","DOI":"10.1145\/800087.802798"},{"key":"4","unstructured":"Curry, H. B., W. Craig and R. C. Feys, <i>Combinatory Logic<\/i>, vol. 1, North-Holland, Amsterdam, 1958. Zbl 0081.24104 MR 20:817"},{"key":"5","unstructured":"Curry, H. B., J. R. Hindley and J. P. Seldin, <i>Combinatory Logic<\/i>, vol. 2, North-Holland, Amsterdam, 1972. Zbl 0242.02029"},{"key":"6","unstructured":"Garey, M. R., and D. S. Johnson, <i>Computers and Intractability: A Guide to the Theory of NP-Completeness<\/i>, W. H. Freeman, San Francisco, 1979. Zbl 0411.68039 MR 80g:68056"},{"key":"7","unstructured":"Glaser, H., C. Hankin and D. Till, <i>Principles of Functional Programming<\/i>, Prentice-Hall, Englewood Cliffs, 1984. Zbl 0649.68002 MR 88i:68007"},{"key":"8","unstructured":"Hindley, J. R., and J. P. Seldin, <i>Introduction to Combinators and $\\lambda$-Calculus,<\/i> Cambridge University Press, Cambridge, 1986. Zbl 0614.03014 MR 88j:03009"},{"key":"9","unstructured":"Joy, M. S., <i>On the Efficient Implementation of Combinators as an Object Code for Functional Programs<\/i>, PhD Thesis, University of East Anglia, Norwich, 1985."},{"key":"10","doi-asserted-by":"crossref","unstructured":"Joy, M. S., V. J. Rayward-Smith and F. W. Burton, \u201cEfficient combinator code,\u201d <i>Computer Languages<\/i>, vol. 10 (1985), pp. 221\u2013224.","DOI":"10.1016\/0096-0551(85)90017-7"},{"key":"11","unstructured":"Kennaway, J. R., \u201cThe complexity of a translation of $\\lambda $-calculus to combinators,\u201d Internal Report CS\/82\/023\/E, University of East Anglia, Norwich, 1982."},{"key":"12","unstructured":"Klop, J. W., <i>Combinatory Reduction Systems<\/i>, Mathematisch Centrum, Amsterdam, 1980. Zbl 0466.03006 MR 83e:03026"},{"key":"13","unstructured":"Stoye, W. R., \u201cThe implementation of functional languages using custom hardware,\u201d Technical Report 81, University of Cambridge Computer Laboratory, Cambridge, 1985."},{"key":"14","unstructured":"Turner, D. A., \u201cAnother algorithm for bracket abstraction,\u201d <i>The Journal of Symbolic Logic<\/i>, vol. 44, (1979), pp. 67\u201370. Zbl 0408.03013 MR 80f:03021"},{"key":"15","doi-asserted-by":"crossref","unstructured":"Turner, D. A., \u201cA new implementation technique for applicative languages,\u201d <i>Software\u2013-Practice and Experience<\/i>, vol. 9 (1979), pp. 31\u201349. Zbl 0386.68009","DOI":"10.1002\/spe.4380090105"},{"key":"16","unstructured":"Turner, D. A., \u201cCombinator reduction machines,\u201d in <i>Proceedings of the International Workshop on High Level Computer Architecture<\/i>, Los Angeles, 1984."}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1305\/ndjfl\/1040248462","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T21:12:30Z","timestamp":1706649150000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-36\/issue-2\/NP-Completeness-of-a-Combinator-Optimization-Problem\/10.1305\/ndjfl\/1040248462.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,4,1]]},"references-count":16,"journal-issue":{"issue":"2","published-online":{"date-parts":[[1995,4,1]]}},"URL":"https:\/\/doi.org\/10.1305\/ndjfl\/1040248462","relation":{},"ISSN":["0029-4527"],"issn-type":[{"value":"0029-4527","type":"print"}],"subject":[],"published":{"date-parts":[[1995,4,1]]}}}