Seven trees - λx. x K S K ＠はてな

NICTA に来てから tree transducer 漬けの毎日． こちらに来るまで，Macro tree transducer (MTT) とか Attributed tree transducer (ATT) とかそれより上のクラスばっかり相手にしていて， Top-down tree transducer (TDTT) は自明な世界だと思ってましたが， Partial や Nondeterministic を許すとなかなか奥が深いです． と，余談はさておき，表題の件です． 元ネタを知っていたので狡いですが， ヒントは，二分木 (Tree) が の不動点で表現できることと， の複素数解 が を満たすということですね． あまり，ヒントになってないか…． OCaml で実装してみましたが，双方向とも 5 種類のパターンによる分岐で定義できます．

[kgbu]

二分木がT=1+T*Tの不動点で表現できるってところが面白い。なんか、水分子の振動モードを連想してしまった。でも、さっぱりわからないのは同じ（汗