A natural counting of lambda terms

June 08, 2015 · The Ethereal · 🏛 Conference on Current Trends in Theory and Practice of Informatics

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, Marek Zaionc arXiv ID 1506.02367 Category cs.LO: Logic in CS Cross-listed cs.DM, cs.PL, math.CO, math.LO Citations 22 Venue Conference on Current Trends in Theory and Practice of Informatics Last Checked 2 months ago
Abstract
We study the sequences of numbers corresponding to lambda terms of given sizes, where the size is this of lambda terms with de Bruijn indices in a very natural model where all the operators have size 1. For plain lambda terms, the sequence corresponds to two families of binary trees for which we exhibit bijections. We study also the distribution of normal forms, head normal forms and strongly normalizing terms. In particular we show that strongly normalizing terms are of density 0 among plain terms.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Logic in CS