Sub-λ-calculi, Classified | Zendy

François-Régis Sinot | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Sub-λ-calculi, Classified

Author(s) -

François-Régis Sinot

Publication year - 2008

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2008.03.038

Subject(s) - calculus (dental) , mathematics , algebraic number , class (philosophy) , algebra over a field , discrete mathematics , computer science , pure mathematics , artificial intelligence , medicine , mathematical analysis , dentistry

When sharing is studied in the λ-calculus, some sub-calculi often pop up, for instance λI or the linear λ-calculus. In this paper, we generalise these to a large class of sub-calculi, parametrised by an arbitrary predicate on the number of occurrences of bound variables. Such a definition only makes sense when the sub-calculi are stable by β-reduction. Surprisingly, we are able to give a complete description and classification of such stable sub-calculi, in a rather algebraic way; and surprisingly again, we discover some unexpected such subcalculi. This could lead to a better understanding of the structure of the λ-calculus

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research