Katarzyna Grygiel. In search of a bijection between β-normal 3-ind. planar λ-terms and β(0,1)-trees
Channel: Computational Logic and Applications
Date: 2020-10-12

15th Workshop
Computational Logic and Applications (https://cla.tcs.uj.edu.pl/)
12-13 October 2020

Speaker: Katarzyna Grygiel and Guan-Ru Yu 
Title: In search of a bijection between β-normal 3-indecomposable planar lambda terms and β(0,1)-trees
Abstract:
During his CLA 2019 talk, Noam Zeilberger posed the following conjecture: β-normal internally 3-edge-connected planar lambda terms are counted by the OEIS sequence A000257. This very sequence is already known to enumerate other structures, among others β(0,1)-trees, i.e., rooted plane trees whose nodes are labeled with non-negative integers in the following way:

*   leaves have label 0;
*   the label of the root is one more than the sum of its children’s labels;
*   the label of any other node exceeds the sum of its children’s labels by at most one.

In our talk we aim at presenting our approaches to find a constructive bijection between these two families of objects. So far, we have managed to find out some building blocks that, when smartly combined together, hopefully could lead us to establish a full recursive procedure for the translation in question. We strongly believe that our ideas can be further expanded and we count on the interaction with the audience.