IO-OI- Hierarchy - formallang.memo

"The IO- and OI- Hierarchies" (1982)

Macro Grammarのさらなる一般化。文脈自由言語の非終端記号が"文字列"をパラメタとしてとれるように拡張したマクロ文法を、高階化する。マクロ文法の非終端記号は関数(string→string)みたいなものなので、さらに、関数を引数に取る関数（(string→string)→string）みたいなものを許す。

• Werner Damm
• Theoretical Computer Science, vol. 20, pp. 95--207
• http://dx.doi.org/10.1016/0304-3975(82)90009-3

n階の関数まで使う文法を Level-n Grammar という（0が文脈自由文法、1がマクロ文法、…でいいと思う。もしかしたらひとつずれてるかも）。マクロ文法と同じく、パラメタの評価戦略によって
IO : Inside-Out, いわゆる call-by-value
OI : Outside-In, いわゆる call-by-name
生成される言語が変わることがわかっている。お互いにuncomparable、つまり、Level-n OI Grammarでは決して書けない IO Macro Grammar があるし、逆も。

• 任意の n について Level-n IO の定義する言語も Level-n OI の定義する言語も Recursive (この論文)
• 任意の n について Level-n IO Grammar の定義する言語は文脈依存言語 [Maneth 2002, The Complexity of Compositions of Deterministic Tree Transducers]
• 任意の n について Level-n OI Grammar の定義する言語は文脈依存言語 [Maneth&Inaba 2008, The Complexity of Tree Transducer Output Languages]
  • ぜったい他ですでに証明されていると思うのだが…

---