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. (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

[img]
Preview
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

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 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:
DateEvent
1995Published
1990Updated
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:
  • http://projecteuclid.org/euclid.ndjfl/10...

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

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