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)|
|Through your library||Configure|
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
Recent downloads (6 months)0
How can I increase my downloads?