Coregular Tree Grammar - formallang.memo

"Un Théorème de Duplication pour les Forêts Algébriques" (1976)

Context-Free Tree Grammarのサブセット。Top-Context-Free とも呼ばれる。呼ばれるというか、この論文と[Hofbauer&Huber&Kucherov 1994,Some Results on Top-Context-Free Tree Languages]でしか見たことがないクラスだけど面白かったのでメモる。

• André Arnold & Max Dauchet
• Journal of Computer and System Sciences, vol. 13, pp. 223-244
• http://dx.doi.org/10.1016/S0022-0000(76)80032-3

定義など

CFTGのサブセットとして正規木言語を見ると、「非終端記号がパラメタをとらない」、つまり「ルールの右辺では非終端記号が常にleafとしてのみ登場する」クラスと考えることができる。Coregularは、逆に「ルールの右辺では非終端記号が常にrootとしてのみ登場する」クラス。

文字列だと左線形も右線形も同じだが木構造だと違うことになる。uncomparable。

OI CFTGは「非決定的に生成した木をコピーする」のが苦手だが、そのOIが唯一できるコピーの形はCoregular Grammarでできるタイプのコピーのみである、ということが示されている。（F'={a(t,t) | t in F} がOI-CFTL if and only if F'とFがcoregular）