The Library
NP-Completeness of a combinator optimisation problem
Tools
Tools
Tools
Joy, Mike and Rayward-Smith, V. J. (1987) NP-Completeness of a combinator optimisation problem. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-88.pdf - Requires a PDF viewer. Download (13Mb) | Preview |
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 expression 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 beta-eta-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: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Combinatory logic | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Place of Publication: | Coventry, UK | ||||
| Official Date: | January 1987 | ||||
| Dates: |
|
||||
| Number: | Number 88 | ||||
| Number of Pages: | 27 | ||||
| DOI: | CS-RR-088 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | M.S. Joy and V.J. Rayward-Smith, “NP-Completeness of a Combinator Optimisation Problem”, <i>Notre Dame Journal of Formal Logic</i> <b>36</b>(2), pp. 319-335 (1995) | ||||
| Funder: | Science and Engineering Research Council (Great Britain) (SERC) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
