Table of Links
2 Pairing functions
To construct a bijection between trees and integers, we use a construction that has its roots in Cantor [12]’s proof that the rationals can be put into one-to-one correspondence with the integers. Cantor used a pairing function [13] to match up N × N with N itself:
Other pairing functions are more convenient for some applications. A popular alternative, illustrated in Figure 1 is the Rosenberg-Strong pairing function [17],
Then, for example, n = 147 can be broken down as,
It may not also be obvious how to use this approach to generate from an arbitrary CFG where the productions allowed at each step vary depending on the CFG’s nonterminal types. In particular, there may be multiple ways of expanding each nonterminal, which differs depending on which non-terminal is used. A simple scheme such as giving each CFG rule an integer code and then using a pairing function like R to recursively pair them together will not, in general, produce a bijection because there may be integer codes that do not map onto full trees (for instance, pairings of two terminal rules in the CFG).
The issue is that in generating from a CFG, we have to encode a choice of which rule to expand next, of which there are only finitely many options. In fact, the number of choices will in general depend on the nonterminal. Our approach to address this is to use two different pairing functions: a modular “pairing function” to encode which nonterminal to use and the Rosenberg-Strong pairing function to encode integers for the child of any node. Thus, if a given nonterminal has k expansions, define a pairing function that pairs {0, 1, 2, . . . , k − 1} × N with N. A simple mod operation, shown in Figure 1, will work:
Author:
(1) Steven T. Piantadosi.
This paper is
[1] A function f such that f(x, y) > max(x, y).