Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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)

[img]
Preview
PDF
WRAP_cs-rr-88.pdf - Requires a PDF viewer.

Download (13Mb) | Preview

Request Changes to record.

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:
DateEvent
January 1987Completion
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.&nbsp;Joy and V.J.&nbsp;Rayward-Smith, &ldquo;NP-Completeness of a Combinator Optimisation Problem&rdquo;, <i>Notre Dame Journal of Formal Logic</i> <b>36</b>(2), pp.&nbsp;319-335 (1995)
Funder: Science and Engineering Research Council (Great Britain) (SERC)
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us