The Library
NP-completeness of a combinator optimisation problem
Tools
Tools
Tools
Joy, Mike and Rayward-Smith, V. J. (1995) NP-completeness of a combinator optimisation problem. Notre Dame Journal of Formal Logic, Volume 36 (Number 2). pp. 319-335. doi:10.1305/ndjfl/1040248462
|
PDF
WRAP_Joy_raywardsmith_ndjfl.pdf - Accepted Version - Requires a PDF viewer. Download (330Kb) | Preview |
Official URL: http://dx.doi.org/10.1305/ndjfl/1040248462
Abstract
We consider a deterministic rewrite system for combinatory logic over combinators S, K, I, B, C, S’, B’ and C’. Terms will be represented by graphs so that reduction of a duplicator will cause the duplicated to be "shared" rather than copied. To each normalising term we assign a weighting which is the number of reduction steps necessary to reduce the expression to normal form. A lambda expression may be represented by several distinct expressions in combinatory logic, and two combinatory logic expressions are considered equivalent if they represent the same lambda expression (up to b-h-equivalence). The problem of minimising the number of reduction steps over equivalent combinator expressions (i.e. the problem of finding the "fastest running" combinator representation for a specific lambda expression) is proved to be NP-complete by reduction from the "Hitting Set" problem.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Combinatory logic, Lambda calculus | ||||||
| Journal or Publication Title: | Notre Dame Journal of Formal Logic | ||||||
| Publisher: | University of Notre Dame | ||||||
| ISSN: | 0029-4527 | ||||||
| Official Date: | 1995 | ||||||
| Dates: |
|
||||||
| Volume: | Volume 36 | ||||||
| Number: | Number 2 | ||||||
| Number of Pages: | 27 | ||||||
| Page Range: | pp. 319-335 | ||||||
| DOI: | 10.1305/ndjfl/1040248462 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
