首页 > 笔记, 逻辑 > 笔记:层化产生式系统(3)

笔记:层化产生式系统(3)

续 层化产生式系统(1)2

主要基于 Louiqa Raschid: A Semantics for a Class of Stratified Production System Programs. 31-57 (bibtex)(download)(citation)

==从层化PS到层化LP==

这么做的目的,是提供和不动点语义等价的一个陈述性语义——因为LP有陈述性语义。如果能把层化PS翻译成层化LP,那就可以用LP做各种有趣的事情!

assert rule很容易理解。retract rule要转化成denial integrity constraint(否定式完整性约束),形式如下

[Li] <- L1, … Lm , 其中i是1 to m其中的一个

意思是L1, … Lm不能全为真;如果全为真,那可以把其中一个Li干掉,这个世界就清静了。例如

[妖精] <- 妖精, 唐僧, 孙悟空 .

==具体过程==

assert P <- A, ¬B 会转化为 P <- A, ¬B.

retract P <- C, ¬D 会转化为 [P] <- C, ¬ D, P . 【这一步是关键】

下一步,要保证程序的完整性integrity。对上面的rule(也即,P被某些规则assert,某些规则retract),要把IC(integrity constraint)代入非IC,把不完整性扼杀在body里!(IC本身就没有利用价值,不要了。)

P’ <- C, ¬D .
P <- A, B, ¬P’ . 【只有在IC不被满足的时候,才生成P。不然,反正也会被IC消灭掉,生成P也是白搭】

对一阶LP,要对变量做合一(unification)

【4.4里的Example 3简化过了,有点误导】

==证明==

要证明转化本身是语义不变的,就要证明PS状态的不动点就对应LP的minimal model。文章的核心贡献,也复杂无比,略过。

==总结==

这是我的心得,不是作者的。

本文的干货是

1)PS层化的原则:身子能扔的先扔掉(retract body literal first),你得先有了头才能没有头(assert head before retract head)

2)PS->LP的翻译,把retract规则看成IC,再把IC改写到LP里。

【完】

Advertisements
分类:笔记, 逻辑
  1. 还没有评论。
  1. No trackbacks yet.

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: