トップ «前の日記(2008-06-07) 最新 次の日記(2008-06-09)» 月表示 編集

日々の流転


2008-06-08 [長年日記]

λ.A constructive proof of equivalence of formalism od DCG's with the formalism of type 0 phrase-structure grammars” by Marica D. Prešić and Slavisa B. Prešić

We present a proof that definite clause grammars (DCG's) are equivalent in their generative power to type 0 phrase-structure grammars. The proof is constructive and it actually describes an algorithm for transferring from a language description by type 0 grammar to DCG characterization. The proof has been inspired by the proof given in [MA93] but our approach is considerably simpler and the constructed DCG grammar is much more efficient. The paper also suggests how computer implementation of the algorithm can be developed.

以前にTwitterで「DCGの言語クラスはtype-0」と書いたときに持ち出した論文を読んだ*1。 記法がよく分からないのだけど、引数の項で記号列を持って、書き換え規則を全て引数の項を書き換える形の規則にするということか。 そうすると、確かに0型文法をDCGで表現すること自体は自明だが、そのままだとProlog等の深さ優先でのSLD導出じゃちゃんと列挙出来ないのでは?*2

*1 あのときはまだ読んでなかったのだった(^^;

*2 0型言語は帰納的ではないけど、帰納的可算ではあるので列挙は出来て欲しい。

λ. 風神録Normalを魔理沙(B)で初クリア

[準備「神風を喚ぶ星の儀式」] 世間はすっかり新作だと思うけど、そういえばまだ風神録あんまりやってなかったなぁと思い、まだNormalをクリアしてなかった魔理沙(貫通装備)でNormalをクリアしてみた。 久しぶりなこともあって、いつも以上にボロボロ。

th10_04.rpy

東方風神録 リプレイファイル情報
Version 1.00a
Name hiro    
Date 08/06/08 23:22
Chara MarisaB
Rank Normal 
Stage All Clear
Score 29768812
Slow Rate 0.18
Tags: 東方