首页 > 笔记, 逻辑 > 笔记:LP的自然层化和不动点语义(3)动态层化

笔记:LP的自然层化和不动点语义(3)动态层化

Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 (download)(citation)

==动态层化 Dynamic Stratification==

层化就是要把一个program里所有的规则rule分分类,有高级的,有低级的,做推理的时候,先低级的工作,然后一层一层往上推。也可以定义为这些rule的head的层。这就叫逻辑程序的不平等,有逻辑的地方就有阶级和阶级斗争。

上面我们说了,我们有一个操作<TI,FI>,不断的迭代的调用,每次会往我们的模型里加一些新的事实fact。这样fact在模型里就有一个先来后到。这个进来的次序,就是这个fact的层。如果把我们合工大看成一个模型,那我就是94层的,比我晚一年的就是95层的。如果94的留级,到了95又进校了,那还算94层的。还要记住,这个模型是是没有毕业一说的(单调增),进去就别想出来!

动态层化对于局域层化的LP,等价于一般的层化(standard stratification)

动态层化是唯一的(unique)。yeah!动态层化是普通层化中最“紧”(tightest)的(U最多)。

不过话说回来,似乎这样的层化,我们要把程序跑一遍。普通层化不用,看看命题的依赖关系就可以了。

一个饱和(saturate)的LP,其模型U为空,也就是其良基模型是二值(2-valued)的。

文章下面证明良基模型可以用迭代最小模型定义,和我的目的不相关。略

==总结==

那动态层化有什么意义呢?其实这个思路很简单,就是把程序跑一遍,把所有能得到的真或者假值都得出来(剩下的算未知),每次得到的新知识,算做一层。

为什么它有唯一性而普通层化没有?因为它有更强的条件——它忽略了在普通层化中在依赖图上可能存在,而在实际运行中其实无关的关系。普通层化的原则是基于语法分析的,而动态层化是基于模型的变化,故是一种语义的分析。

此不动点语义,或可用于RIF-PRD。

【完】

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