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

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

今天重温这篇经典文章

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

Przymusinski是UC Riverside的教授。他的文章大部分就一个作者,有时有个co-author Przymusinska,我瞎猜是他太太。

==背景==

Perfect model 是LP的minimal model,等价于iterated least fixed points (迭代最小不动点) of natural operators。但是这个语义,只能用在局域层化的LP上(stratified LP)。前面我有笔记说什么是层化(大义是高层次的词汇只能依赖于低或同层次的词汇)。

Perfect model semantics 参

Teodor C. Przymusinski: On the Declarative and Procedural Semantics of Logic Programs. J. Autom. Reasoning 5(2): 167-205 (1989)

本文的主要贡献是说well-founded semantics(WFS,作为perfect model semantics的一个扩展)可以用在所有的LP上,不仅是层化LP。而且,所有的LP都有一个动态层化(dynamic stratification)的办法。

well-founded semantics是一个三值语义,每个fact可以是True, False or Unknown。

为什么要看这个?主要是看能不能用在RIF的语义上。比如RIF-BLD没有否定。如果进入自然层化,或许就可以了。到底成不成,看完才知道。

==三值模型==

三值模型是WFS的特点。我们这里先只考虑命题LP而不是一阶LP,所有的atom都是ground(不含变量)。

把所有的atom分成三个集合:T(真),F(假),U(未知)。对一个一致(consistant)的模型,三个集合互斥。

真值有个次序, t>u>f. 组合如下

¬t=f, ¬f= t ¬u=u

t ∨ f = t, t ∨ t = t, t ∨ u = t,  f ∨ u = u,  u ∨ u = u,  f ∨ f = f,

t ∧ f = f, t ∧ t = t, t ∧ u = u,  f ∧ u = f,  u ∧ u = u,  f ∧ f = f,

f->u = t, f->t = t, u->t =t (其他略)

对每个规则 A<- L1,…Lm

要求val(A) >= val(L1^…^Lm) 也就是大于val(Li)最小的一个

一个模型I1=<T1,F1>扩展(extends)另一个I2=<T2,F2>,如果T2是T1的子集,F2是F1的子集。模型的交和并是他们相应T集/F集的交和并。

I2<= I1 if T1是T2的子集,F2是F1的子集。也就是,I2有更少的T和更多的F。一个模型是最小的,如果没有其他模型比它更小(好像是废话)。最小模型(minimal model)含有最少的T和最多的F。

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