ド・ブラウン記法

ド・ブラウン記法(英:De Bruijn notation)とは、ラムダ計算の表記のための構文の一つである。オランダ人数学者ニコラース・ホーヴァート・ド・ブラウンによって発明された。

 生成文法 
ド・ブラウン記法の項は、vを任意の変数名、MとNを任意のド・ブラウン記法の項とするとき、
 v
 [v] M
 (M) N
の形で表されるもの全てである。

 通常の記法との対応 
Iを通常のラムダ計算の記法からド・ブラウン記法への変換とし、vを任意の変数名、MとNを任意のド・ブラウン記法の項とするとき、
 I(v) = v
 I(λv.M) = [v]I(M)
 I(M N) = (I(N))I(M)
となる。

 参考文献 
 BONELLI E, RIOS A (Univ. Buenos Aires, Buenos Aires, ARG), KESNER D (Univ. Paris-Sud, Orsay, FRA) "A de Bruijn Notation for Higher-Order Rewriting" postscript

Category:ラムダ計算
Category:数学のエポニム