Ranking/Unranking of Lambda Terms with Compressed de Bruijn Indices

DOI10.1007/978-3-319-20615-8_8zbMath1417.68028OpenAlexW850177946MaRDI QIDQ3453110

Paul Tarau

Publication date: 20 November 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-20615-8_8

zbMATH Keywords

lambda calculuscombinatorics of lambda termsde Bruijn indicesbijective Gödel numberings of lambda termslambda-term compressionranking and unranking of lambda terms

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Logic programming (68N17)

Related Items

Tests and proofs for custom data generators ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ Deriving Efficient Sequential and Parallel Generators for Closed Simply-Typed Lambda Terms and Normal Forms

Uses Software

• Automath
• OEIS

Cites Work

• The lambda calculus. Its syntax and semantics. Rev. ed.
• On arithmetical first-order theories allowing encoding and decoding of lists
• Asymptotically almost all \lambda-terms are strongly normalizing
• Compact serialization of Prolog terms (with catalan skeletons, cantor tupling and Gödel numberings)
• Counting and generating lambda terms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item