David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Notre Dame Journal of Formal Logic 36 (2):319-335 (1995)
We consider a deterministic rewrite system for combinatory logic over combinators , and . 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 normalizing 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 --equivalence). The problem of minimizing 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
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Katalin Bimbó (2005). Admissibility of Cut in LC with Fixed Point Combinator. Studia Logica 81 (3):399 - 423.
Philippe Mongin (2000). Does Optimization Imply Rationality? Synthese 124 (1-2):73 - 111.
Frédéric Laville (2000). Should We Abandon Optimization Theory? The Need for Bounded Rationality. Journal of Economic Methodology 7 (3):395-426.
Sahotra Sarkar (2005). Maynard Smith, Optimization, and Evolution. Biology and Philosophy 20 (5):951-966.
Lou Goble (2004). Combinator Logics. Studia Logica 76 (1):17 - 66.
Daniel J. Gilman (1993). Optimization and Simplicity: Marr's Theory of Vision and Biological Explanation. Synthese 107 (3):293-323.
Stéphane Demri (1997). A Completeness Proof for a Logic with an Alternative Necessity Operator. Studia Logica 58 (1):99-112.
Jairo José Da Silva (2000). Husserl's Two Notions of Completeness: Husserl and Hilbert on Completeness and Imaginary Elements in Mathematics. Synthese 125 (3):417 - 438.
Christian Arnsperger (2000). Methodological Altruism as an Alternative Foundation for Individual Optimization. Ethical Theory and Moral Practice 3 (2):115-136.
Paul Weirich (2010). Optimization and Improvement. [REVIEW] Philosophical Studies 148 (3):467 - 475.
Björn Hagströmer, Richard G. Anderson, Jane M. Binner, Thomas Elger & Birger Nilsson, Mean-Variance Vs. Full-Scale Optimization: Broad Evidence for the UK.
Katalin Bimbó (2003). The Church-Rosser Property in Dual Combinatory Logic. Journal of Symbolic Logic 68 (1):132-152.
Sherry May (1976). Probability Kinematics: A Constrained Optimization Problem. [REVIEW] Journal of Philosophical Logic 5 (3):395 - 398.
Robert E. McGinn (1997). Optimization, Option Disclosure, and Problem Redefinition. Professional Ethics 6 (1/2):5-25.
Sorry, there are not enough data points to plot this chart.
Added to index2010-08-24
Total downloads1 ( #459,101 of 1,101,814 )
Recent downloads (6 months)1 ( #306,516 of 1,101,814 )
How can I increase my downloads?