北京大学学报（自然科学版）
北京大學學報（自然科學版）
북경대학학보（자연과학판）
ACTA SCIENTIARUM NATURALIUM UNIVERSITATIS PEKINENSIS
1999年
5期
589-601
,共13页
信念格%多值非循环有限自动机%蕴涵%特征和%最小不相容特征描述逻辑
信唸格%多值非循環有限自動機%蘊涵%特徵和%最小不相容特徵描述邏輯
신념격%다치비순배유한자동궤%온함%특정화%최소불상용특정묘술라집
belief lattice%multiple-valued acyclic finite automaton%subsumption%feature sum%mini-mally inconsistent feature description logic
提出了信念格上的多值非循环有限自动机并给出了特征和的算法,分别与Rounds-Kasper和Dawar-Shanker的非循环有限自动机相比较,这一理论扩展了自然语言语义运算的能力.定义了最小不相容特征描述逻辑和它的语义,并为该逻辑提供了一个充分且完备的证明系统.最后,证明了最小不相容特征描述逻辑的可满足性问题是NP-完全的.
提齣瞭信唸格上的多值非循環有限自動機併給齣瞭特徵和的算法,分彆與Rounds-Kasper和Dawar-Shanker的非循環有限自動機相比較,這一理論擴展瞭自然語言語義運算的能力.定義瞭最小不相容特徵描述邏輯和它的語義,併為該邏輯提供瞭一箇充分且完備的證明繫統.最後,證明瞭最小不相容特徵描述邏輯的可滿足性問題是NP-完全的.
제출료신념격상적다치비순배유한자동궤병급출료특정화적산법,분별여Rounds-Kasper화Dawar-Shanker적비순배유한자동궤상비교,저일이론확전료자연어언어의운산적능력.정의료최소불상용특정묘술라집화타적어의,병위해라집제공료일개충분차완비적증명계통.최후,증명료최소불상용특정묘술라집적가만족성문제시NP-완전적.
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 RoundsKasper Logic is defined. Later, several persons proposed various logics that include negation in RoundsKasper-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.
