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

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

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

这个文章讲有一种分层的production rule系统,可以转化为一般的LP系统,从而有陈述性语义(declarative semantics)——而不仅是操作语义(operational semantics)。

另参 P.M. Dung, P. Mancarella, “Production Systems with Negation as Failure,” IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 2, pp. 336-352, Mar./Apr. 2002, doi:10.1109/69.991720

==层化LP==

如果LP中有“非”(not),那不能保证推理结果的唯一性,例如

P :- not Q.
Q : -not P.

那{},{P,Q}都是一个model。所以,到底P是真还是假,不确定。

是不是就不可以有非呢?层化是说,可以有非操作,但是谓词(或者命题)要分个三六九等, 高等级的谓词可以依赖于低等级的谓词的非,反之不可以。例如

P :- not Q.
Q :- not R.

这个就没有问题。如果我们把not的依赖画个关系,那这个图要求无环。这样的LP,称为层化stratified logic program 。对产生式程序(production program),也有对应的层化。就是本文研究的对象。

层化LP有well-founded semantics (WFS, Gelder 1988)。对locally stratified LP,有perfect model semantics (Przymusinska, 1986)。暂不深谈。

==目的==

为什么要研究这种层化的产生式程序?因为它有陈述性语义。好处如下

  • 产生式系统的推理通常要经过一个复杂的匹配过程(参RIF-PRD的语义);陈述性语义相对简单,无论是数据库还是LP(参考answer set的构造)。
  • 当我们执行产生式规则时,无法检验结果的正确性(correctness, or soundness)。打个比方说,如果我们把生孩子的过程看成一个产生式程序,那怀孕生产,都是其中的过程,最后生下一个孩子,或男或女,但是我们既不能事先预测,也不能检测这个性别是不是表达“对”了(相对受精卵)。反之,如果我们把受精卵的DNA作为语义,那首先,我们可以预测,这个孩子能不能生出来(类比于逻辑的termination),而且生出来以后,如果XY染色体出来的小宝宝没“把”,那肯定是基因表达(推理过程)出错了。
  • 操作语义本身不能保证执行的可终止性(termination)和结果的唯一性(deterministic)。
  • 操作语义很难用来做证明程序的等价性(equivalence),冗余性(redundancy),包含性(embedding),一致性(consistency)等。我认为这一点最重要!

霍恩逻辑有好几种语义:不定点(fixpoint)语义,模型论(model-theoretic)语义,操作(operational)语义相互都是等价的。

数据库有证明论(proof-theoretic)语义和模型论语义,也是等价的。

那么我们能不能对 产生式程序 定义 模型论语义(也即陈述性语义)——及对应的不动点语义?一般不能,但对层化的产生式程序,可以。

层化的产生式程序有标准的最小模型(minimal model)语义。把层化的产生式程序翻译成层化的LP,原有层化LP的研究就都可以借鉴过来了。

【未完,待续】

Advertisements
分类:笔记, 逻辑, 思路

发表评论

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