Search

• < Previous
• 1
• Next >

---

Relational Graph Models at Work

Flavien Breuvart ; Giulio Manzonetto ; Domenico Ruoppolo.

We study the relational graph models that constitute a natural subclass of relational models of lambda-calculus. We prove that among the lambda-theories induced by such models there exists a minimal one, and that the corresponding relational graph model is very natural and easy to construct. We then&nbsp;[&hellip;]

---

Degrees of extensionality in the theory of B\"ohm trees and Sall\'e's conjecture

Benedetto Intrigila ; Giulio Manzonetto ; Andrew Polonsky.

The main observational equivalences of the untyped lambda-calculus have been characterized in terms of extensional equalities between B\"ohm trees. It is well known that the lambda-theory H*, arising by taking as observables the head normal forms, equates two lambda-terms whenever their B\"ohm trees&nbsp;[&hellip;]

---

Addressing Machines as models of lambda-calculus

Giuseppe Della Penna ; Benedetto Intrigila ; Giulio Manzonetto.

Turing machines and register machines have been used for decades in theoretical computer science as abstract models of computation. Also the $\lambda$-calculus has played a central role in this domain as it allows to focus on the notion of functional computation, based on the substitution mechanism,&nbsp;[&hellip;]

---

Revisiting Call-by-value B\"ohm trees in light of their Taylor expansion

Emma Kerinec ; Giulio Manzonetto ; Michele Pagani.

The call-by-value lambda calculus can be endowed with permutation rules, arising from linear logic proof-nets, having the advantage of unblocking some redexes that otherwise get stuck during the reduction. We show that such an extension allows to define a satisfying notion of B\"ohm(-like) tree and&nbsp;[&hellip;]

---

Full Abstraction for the Resource Lambda Calculus with Tests, through Taylor Expansion

Thomas Ehrhard ; Antonio Bucciarelli ; Alberto Carraro ; Giulio Manzonetto.

We study the semantics of a resource-sensitive extension of the lambda calculus in a canonical reflexive object of a category of sets and relations, a relational version of Scott's original model of the pure lambda calculus. This calculus is related to Boudol's resource calculus and is derived from&nbsp;[&hellip;]

---