Acta Scientiarum Naturalium Universitatis Pekinensis

Previous Articles     Next Articles

Multiple-valued Feature Structure Description

YU Jiangsheng, CHENG Minde   

  1. School of Mathematical Sciences, Peking University, Beijing, 100871
  • Received:1998-07-13 Online:1999-09-20 Published:1999-09-20


于江生, 程民德   

  1. 北京大学数学科学学院,北京,100871

Abstract: Feature structures are used in represention of linguistic knowledge. Rounds and Kasper proposed the acyclic finite automaton to describe the feature structures (f-structures) on which Rounds-Kasper Logic is defined. Later, several persons proposed various logics that include negation in Rounds-Kasper-like framework. In this article, a description of multiple-valued feature structures based on belief lattice is established, which extends the ability of semantic operations. Then, Minimally Inconsistent Feature Description Logic and its semantics are defined. We also showed some properties of them. Finally, we presented a sound and complete proof system for our logic and a theorem of NP-completeness.

Key words: belief lattice, multiple-valued acyclic finite automaton, subsumption, feature sum, minimally inconsistent feature description logic

摘要: 提出了信念格上的多值非循环有限自动机并给出了特征和的算法,分别与Rounds-Kasper和Dawar-Shanker的非循环有限自动机相比较,这一理论扩展了自然语言语义运算的能力。定义了最小不相容特征描述逻辑和它的语义,并为该逻辑提供了一个充分且完备的证明系统。最后,证明了最小不相容特征描述逻辑的可满足性问题是NP-完全的。

关键词: 信念格, 多值非循环有限自动机, 蕴涵, 特征和, 最小不相容特征描述逻辑

CLC Number: