TY - JOUR
AU - Mayer Goldberg
PY - 1995/06/19
Y2 - 2019/09/15
TI - Solving Equations in the lambda-Calculus using Syntactic Encapsulation
JF - BRICS Report Series
JA - BRICS
VL - 2
IS - 49
SE - Articles
DO - 10.7146/brics.v2i49.19950
UR - https://tidsskrift.dk/brics/article/view/19950
AB - Syntactic encapsulation is a relation between an expression and one ofits sub-expressions, that constraints how the given sub-expression canbe used throughout the reduction of the expression. In this paper, wepresent a class of systems of equations, in which the right-hand side ofeach equation is syntactically encapsulated in the left-hand side. Thisclass is general enough to allow equations to contain self-application,and to allow unknowns to appear on both sides of the equation. Yetsuch a system is simple enough to be solvable, and for a solution(though of course not its normal form) to be obtainable in constanttime.Keywords: lambda-calculus, programming calculi.
ER -