RPO, Second-order Contexts, and Lambda-calculus

Details RPO, Second-order Contexts, and Lambda-calculus RPO, Second-order Contexts, and Lambda-calculus

2009-06-15

arxiv.org/abs/0906.2727v2

LMCS 5 (3:6) 2009

Computer Science

Programming Languages

35 pages, published in Logical Methods in Computer Science

Scientific paper

10.2168/LMCS-5(3:6)2009

First, we extend Leifer-Milner RPO theory, by giving general conditions to obtain IPO labelled transition systems (and bisimilarities) with a reduced set of transitions, and possibly finitely branching. Moreover, we study the weak variant of Leifer-Milner theory, by giving general conditions under which the weak bisimilarity is a congruence. Then, we apply such extended RPO technique to the lambda-calculus, endowed with lazy and call by value reduction strategies. We show that, contrary to process calculi, one can deal directly with the lambda-calculus syntax and apply Leifer-Milner technique to a category of contexts, provided that we work in the framework of weak bisimilarities. However, even in the case of the transition system with minimal contexts, the resulting bisimilarity is infinitely branching, due to the fact that, in standard context categories, parametric rules such as the beta-rule can be represented only by infinitely many ground rules. To overcome this problem, we introduce the general notion of second-order context category. We show that, by carrying out the RPO construction in this setting, the lazy observational equivalence can be captured as a weak bisimilarity equivalence on a finitely branching transition system. This result is achieved by considering an encoding of lambda-calculus in Combinatory Logic.

Affiliated with

Also associated with

No associations

Rating

RPO, Second-order Contexts, and Lambda-calculus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with RPO, Second-order Contexts, and Lambda-calculus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and RPO, Second-order Contexts, and Lambda-calculus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-316576