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

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

层化产生式系统(1)

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

==语法==

基本的产生式系统,就是这个形式  assert R(x)[或 retract S(x)] <-P(x), not Q(x).

安全性(safety):所有的变量都要在body的正字项(literal, 有人翻译成“文字”,我觉得不妥)里出现。这有两个作用,在匹配时,负字项negative literal可以保证匹配(NAF),对retract操作,只会作用在已有的实例上。

对层化的LP rule,有这个形式 A<- L1, L2,… Lm

一个程序P,可以分成不相交的几组(层)。对第i层中的rule,如果在body的正字项中含有一个谓词,那这个谓词所依赖的谓词作为头部,都在i或更低的层中。比如如果有 A<- B,B<-C ,那{B<-C}的层次不高于{A<-B}(可能相等)。

在body的负字项中含有一个谓词,那它所依赖的谓词都在绝对低于i的层中。比如如果有 A<- not B,B<-C,那{B<-C}的层次绝对低于{A<-B}。

对层化的PS(production system),PS0包含那些facts。其他rule,分成a型(assert)和r型(retract)。a型,按层化的LP同样要求。对r型,要求头部所依赖的谓词都在绝对更低层中。例

R1) assert P<- A, not B .
R2) retract A <- C .
R3) retract B <- C .

那R1>R2, R1 >R3。原则是有依赖关系时,先retract能retract的东西。这叫身子能扔的先扔掉(retract body literal first)。

另外,如果 retract P <-A 在i层中,那 assert P<-B 或 retract P<-B 在i或更低层中。原则就是retract级别比assert高。因为执行的时候是从低层次往高层次执行,所以P会被先assert再retract。这叫你得先有了头才能没有头(assert head before retract head)

如果没有retract操作,那这个层化PS和层化LP就没什么两样了。

==语义==

一个层化的PS有不动点操作TPS。首先,EDB0(沿用RIF的说法,我们称为状态)是所有的初始事实,记为assert P(x)之类。后续的状态由这个初始状态变化而来。

一个状态S|=P, 如果 assert P在S里,而retract P不在。反之,S|=¬P。

assert P不在S里,而retract P在S里是不可能的。

TPS操作定义了状态的转移,是单调增的。也就是,如果一个rule的body部分被S满足,而head部分为assert P或者retract P,那TPS(S)包含了assert P或者retract P。这和RIF-PRD不同,哪里一个状态会被动作增加,或者减少元素,不是单调的。

TPS操作逐层进行,从低往高。每层到了不动点,停,进入下一层。

【待续】

Advertisements
分类:笔记, 逻辑
  1. 还没有评论。
  1. 2011/04/26 @ 17:37

发表评论

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 博主赞过: