福彩号码查询
学霸学习网 这下你爽了
当前位置:福彩号码查询 >> >>

体彩开奖号码查询:Modalities in knowledge representation

福彩号码查询 www.edasl.tw Modalities in Knowledge Representation
Ullrich Hustadt and Andreas Nonnengart
Max-Planck-Institut fur Informatik, Im Stadtwald, 66123 Saarbrucken, Germany

Standard knowledge representation systems are supposed to be able to represent either common or individual knowledge about the world. In this paper we propose an extension to such knowledge representation systems which, in a uniform manner, allows to express beliefs of multiple agents as well as knowledge, desire, time and in fact any modality which has a rst-order predicate logic possible world semantics. Since the mid-seventies a variety of knowledge representation systems in the tradition of semantic networks and terminological logics has been proposed. The most famous example is KL-ONE3 which rst appeared in 1977 in R. J.1 Brachman's Ph.D. thesis. Other examples are KRYPTON2, NIKL12, and KRIS . All these systems can be used to represent common or individual knowledge about the world. Recently, terminological logics have been extended to allow the representation of the knowledge or the beliefs of multiple agents in one knowledge base4; 7. In this paper, we investigate such an extension which allows not only to represent either knowledge or beliefs of multiple agents but a huge variety of modal operators for multiple agents. We assume four disjoint alphabets, the primitive concepts C , the primitive roles R, the set M of modal operator names , and the individual objects O. In particular, there is a distinguished subset A of the individual objects, called the set of agents, containing the special agent all which is supposed to denote the union of all the agents in order to be able to express mutual belief. The tuple (O; A; M; C ; R) is called the signature, denoted by . The set of concept terms (or just concepts) and role terms (or just roles) is inductively de ned as follows. Every primitive concept is a concept term and every primitive role is a role term. Now assume that C , C1, and C2 are concepts, R, R1, and R2 are roles, m is a modal operator name, a is an agent's name. Then C1 u C2, :C , 9 R:C , and 3(m;a) C are concept terms, and R1 u R2, R?1 , R C , 2(m;a) R and 3(m;a) R are role terms. Thus we are now able to describe the sentences of our language Mod-ALC which are divided into terminological sentences and assertional sentences. If C1 and C2 are concepts and R1 and R2 are roles then C1 v C2, R1 v R2 are terminological sentences. If C is a concept, R is a role, and O, O1, and O2 are individual objects then

ABSTRACT

1 Introduction

2 Syntax and Semantics for Mod-ALC

O 2 C and (O1; O2) 2 R are assertional sentences. Moreover, if is a terminological (respectively assertional) sentence and if m is a modal operator name and a is an agent's name then 2(m;a) and 3(m;a) are terminological (respectively assertional) sentences. A set of terminological and assertional sentences is a knowledge base. So far the syntax of Mod-ALC has been described. Now we have to provide its semantics. De nition 1 ( -Structures) As usual we de ne a -structure as a pair (D; I ) which consists of a domain D and an interpretation function I which maps the individual objects to elements of D, primitive concepts to subsets of D and the primitive roles to subsets of D D. De nition 2 (Frames and Interpretations) By a frame F we understand any pair (W ; <) where W is a non-empty set (of worlds) and < = Um2M;a2A <a where m the <a 's are binary relation on W , the so-called accessibility relations between m worlds. By a -interpretation = based on F we understand any tuple (D; F; =loc; ) where D denotes the common domain of all -structures in the range of =loc, F is a frame, and =loc maps worlds to -structures with common domain D which interpret agents' names equally. De nition 3 (Interpretation of Terms) Let = = (D; F; =loc; ) be a -interpretation and let =loc( ) = (D; I ). We de ne the interpretation of terms inductively over their structure: =(C ) = I (C ) if C is a primitive concept =(R) = I (R) if R is a primitive role =(C1 u C2) = =(C1) \ =(C2) =(:C ) = D n =(C ) =(9 R:C ) = fd 2 D j e 2 =(C ) for some e with (d; e)a2 =(R)g =(3(m;a) C ) = fd 2 D j d 2 = ](C ) for some with <m( ; )g =(R1 1u R2) = =(R1) \ =(R2) =(R? ) = f(x; y) 2 D D j (y; x) 2 =(R)g =(R C ) = f(x; y) 2 =(R) j y 2 =(C )g =(2(m;a) R) = f(x; y) j (x; y) 2 = ](R) for all with <a (a; )g m =(3(m;a) R) = f(x; y) j (x; y) 2 = ](R) for some with <m( ; )g where = ] = (D; F; =loc; ). De nition 4 (Satis ability) Let = = (D; F; =loc; ) be a -interpretation. We de ne the satis ability relation j= inductively over the structure of Mod-ALC sentences: = j= C1 v C2 i =(C1) =(C2) = j= R1 v R2 i =(R1) =(R2) = j= x 2 C i I (x) 2 =(C ) = j= (x; y) 2 R i (I (x); I (y)) 2 =(R) = j= 2(m;a) i = ] j= for every with <a ( ; ) m = j= 3(m;a) i = ] j= for some with <a ( ; ) m

are models for then we call a theorem. Any sentence for which no model exists is called unsatis able. Thus, is a theorem i its negation is unsatis able. Let T be a set of Mod-ALC sentences. We say T entails , written T j= , i every model of T is a model of . So far we did not consider any special properties of the given modal operators. Typical axiom schemata which re ect such potential additional properties are listed below. Axiom Schema Property 2(m;a) ) 3(m;a) 8x9y <a (x; y) m 2(m;a) ) 8x <a (x; x) a m ) 2(m;a) 3(m;a) 8x;ay <a (x; y)a) <m(y; x)a m 2(m;a) ) 2(m;a) 2(m;a) 8x; y; z <m(x; y) ^ <m (y; z) ) <m (x; z) 3(m;a) ) 2(m;a) 3(m;a) 8x; y; z <a (x; y) ^ <a (x; z) ) <a (y; z) m m m Table 1: Properties of the accessibility relation Historically, these properties are called D, T , B , 4, and 5 respectively. If we consider modal operators for belief, i.e. 2(believe;a) and 3(believe;a) , then 4 and 5 are axioms of introspection. Intuitively, they say that the agent a has complete insight what his own beliefs are concerned. Property T is one of the major characteristics of modal operators for knowledge, i.e. 2(knows;a) and 3(knows;a), because it enables us to deduce a fact about the real world from an agent's knowledge about the world. De nition 6 Let R be a set of properties of the accessibility relation. An interpretation = is called a R-interpretation if the accessibility relation < of the underlying frame F satis es all properties in R. We say a set of Mod-ALC sentences T entails in all R-interpretations, written T j=R , if all R-interpretations which are models of T are also models of . What is remarkable for the properties from above is that they all are rst-order properties. Therefore it is not too surprising that a translation of modal terminological and modal assertional axioms into rst-order predicate logic can be done very easily.

De nition 5 Let = be an interpretation and let be a Mod-ALC sentence with = j= . Then we call satis able and we call = a model for . If all interpretations

3 Translating Mod-ALC into Classical Logic

There have been a lot of proposals for correct and complete calculi for nonclassical logics | temporal logics11, epistemic logics8, etc. | and terminological logics3; 5. Unfortunately, these calculi require implementations for their respective theorem proving system with hardly a chance to apply results and techniques of the traditional work on automated theorem proving. Therefore, we follow the approach of Ohlbach10 to eliminate modal operators in a way that we get standard rst-order predicate logic formulae that still represent the modal semantics.

However, if we take a closer look at the results of a straightforward translation of terminological and assertional sentences into rst-order logic we can see quite a big problem. Already simple knowledge bases result in rather huge clause sets where many of the clauses merely express certain informations about accessibilities and role correlations. But we can exploit a property of the language Mod-ALC which is typical for most modal and terminological logics, namely, each accessibility relation symbol or role symbol R occurs either in the form 9x R(: : : ; x) ^ (x) or in the form 8x R(: : : ; x) ) (x). First of all let us de ne what we mean by a functional simulator. De nition 7 (Functional Simulators) Let < be an n-ary relation. A set F< of functions is called a functional simulator for < if for any x1; : : :; xn <(x1; : : :; xn) i there exists a f 2 F< with f (x1; : : : ; xn?1) = xn In particular, if < is total, i.e. for any x1 : : : xn?1 there is a xn such that <(x1; : : : ; xn) then each function in F< is total, too. I.e. a functional simulator for some relation R is a set of functions which is able to take over the responsibilities of R. What a functional simulator is on the meta-level are the simulator axioms on the object level. De nition 8 (Simulator Axioms for Total Predicates) According to De nition 7 we call the two axioms SimR = 8ui; v R(: : : ; ui; : : : ; v) ) 9f : FR f (: : :; ui; : : :) = v 1 SimR = 8ui8f : FR R(: : : ; ui; : : : ; f (: : : ; ui; : : :)) 2 the simulator axioms for the total predicate R. Note that in the case of non-total predicates the de nition of SimR needs to be changed because in this case we have 2 to be able to deal with partial functions instead of total functions. The collection of all axioms SimR, respectively SimR, is called Sim1, respectively Sim2. 1 2 Thus, for any total (serial) accessibility relation or role we can introduce functional simulators. This allows the following approach for the translation of knowledge bases into rst-order predicate logic. First, we transform all concepts and roles which occur in a given knowledge base into negation normal form, i.e. in a form where all negation signs occur solely in front of the primitive concepts. Now we translate the terminological and assertional sentences into rst-order logic formulae using the function ]]. Axiom

2(m;a)M2 : : :Mn 3(m;a)M2 : : : Mn C1 v C2 ]]U R1 v R2 ]]U a 2 A ]]U (a; b) 2 P ]]U

Translation ]]U 8V : <a (U; V ) ) M2 : : : Mn ]]V m ]]U 9V : F<a M2 : : :Mn ]]V (U ) m 8 X : C1 ]]U;X ) C2 ]]U;X 8 X; Y : R1 ]]U;(X;Y ) ) R2 ]]U;(X;Y ) A ]]U;a P ]]U;(a;b)

where the translation of concepts and roles is de ned by:

Term Translation A1 ]]U;X A1(U; X ) :A1 ]]U;X :A1(U; X ) C1 u : : : u Ck ]]U;X C1 ]]U;X ^ : : : ^ Ck ]]U;X 9 R:C ]]U;X 9Y : FR C ]]U;Y (X ) 3(m;a) C ]]U;X 9V : F<a C ]]V (U );X m P ]]U;(X;Y ) P (U; X; Y ) R1 u : : : u Rl ]]U;(X;Y ) R1 ]]U;(X;Y ) ^ : : : ^ Rl ]]U;(X;Y ) R?1 ]]U;(X;Y ) R ]]U;(Y;X ) R C ]]U;(X;Y ) R ]]U;(X;Y ) ^ C ]]U;Y 2(m;a) R ]]U;(X;Y ) 8V : <a (U; V ) ) R ]]V;(X;Y ) m 3(m;a) R ]]U;(X;Y ) 9V : F<a R ]]V (U );(X;Y ) m Thus, given any Mod-ALC -formula , the result of the above translation, ]] is a rst-order predicate logic formula which can easily be transformed into clause normal form with the help of the well-known standard techniques. Note that the clause form of such a translation does not contain any positive occurrence of a role or accessibility relation symbol. This fact can be exploited in a very interesting manner. Since any role or accessibility relation symbol can only occur in the additional axioms we can examine these independently from the translated formula. Nonnengart9 presents extremely good simpli cations for various modal logics. So, for instance, the whole theory for the modal logic KD45 can be simpli ed to the almost trivial unit clause R(U; V (W )). In the following theorem we suppose that we have some simpli cation Sim which can be applied to a set R of formulae expressing the properties of the accessibility relation such that R fSim2g j= ]] i Sim(R) fSim2g j= ]] Theorem 3.1 Let be a Mod-ALC sentence and T a set of Mod-ALC sentences. Let R be a set of formulae which express the properties of the underlying accessibility relation. Then T j=R S i ]] Sim(R) fSim2g j= ]] 2T i ]] is provable from S 2T ]] Sim(R) fSim2g using some theorem prover which is correct and complete for rst-order logic with equality. We presented an approach which allows to reason within modal terminological logics by utilizing an appropriate translation technique into rst-order predicate logic. The main idea behind this method is the functional simulation of accessibility relations and roles by suitable sets of functions. This turns out to have two main advantages: it decreases the size and the number of clauses and it allows signi cant simpli cations on the set of theory clauses.

4 Conclusion and Further Work

Until now, we have only worked out the optimization for those modalities which have a simple possible world semantics. If the interaction of multiple modalities requires the more complex neighbourhood semantics, we have to rely on the straightforward translation which will result in a rather large number of clauses. Looking for optimizations for this case is part of future work. 1. F. Baader and B. Hollunder, KRIS : Knowledge Representation and Inference System | System Description |. Technical Memo DFKI-TM-90-03 (Deutsches Forschungszentrum fur Kunstliche Intelligenz, Saarbrucken, 1990). 2. R. J. Brachman, V. P. Gilbert, and H. J. Levesque, An Essential Hybrid Reasoning System: Knowledge and Symbol Level Accounts of krypton. In Proceedings of the Ninth IJCAI, pp. 532{539. 3. R. J. Brachman and J. G. Schmolze, An Overview of the klone Knowledge Representation System. Cognitive Science 9 2 (1985), pp. 171{216. 4. F. M. Donini, M. Lenzerini, D. Nardi, A. Schaerf, and W. Nutt, Adding Epistemic Operators to Concept Languages. In Proceedings of the KR'92, eds. B. Nebel, C. Rich, and W. Swartout (Morgan Kaufmann, 1992), pp. 342{353. 5. B. Hollunder and W. Nutt, Subsumption Algorithms for Concept Languages. Research Report DFKI-RR-90-04 (Deutsches Forschungszentrum fur Kunstliche Intelligenz, Saarbrucken, 1990). 6. U. Hustadt, A. Nonnengart, R. Schmidt, and J. Timm, MOTEL User Manual. Internal report MPI-I-92-236 (Max-Planck-Institute for Computer Science, Saarbrucken, 1992). 7. A. Kobsa, Towards Inferences in BGP-MS: Combining Modal Logic and Partition Hierarchies for User Modeling (Preliminary Report). In Proceedings of the Third International Workshop on User Modeling (1992). 8. R. C. Moore, Autoepistemic Logic. In Non-Standard Logics for Automated Reasoning, eds. Ph. Smets, E. H. Mamdani, D. Dubois, and H. Prade (Academic Press, London, 1988) 9. A. Nonnengart, First-Order Modal Logic Theorem Proving and Standard PROLOG. Internal report MPI-I-92-228 (Max-Planck-Institute for Computer Science, Saarbrucken, 1992). 10. H. J. Ohlbach, A Resolution Calculus for Modal Logics. PhD thesis (Universitat Kaiserslautern, 1988). 11. N. Rescher and A. Urquhart, Temporal Logic (Springer, Berlin, 1971). 12. J. G. Schmolze, The Language and Semantics of nikl. Technical Report 89{4 (Department of Computer Science, Tufts University, Medford, MA, 1989).

References


推荐相关:

...in Massively Parallel Knowledge Representation_....pdf

免费 Modalities in knowledge ... 暂无评价 6页 免费 Knowledge representation... 13页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,...

Multispectral image fusion method using perceptual ....pdf

by means of combining different spectral characteristics or image modalities. ...In this way no additional transformation is needed and direct representation ...

疼痛与本体感受.pdf

(i.e. other than free nerve endings) have the biggest representation in ...Comment on the different modalities they serve, and their location. Explain ...

A Virtual Reality Training System for Pediatric Son....pdf

modalities, such as noise, speckle, acoustic ...were described in a knowledge base, and linked ...Tiede. A new representation of knowledge concerning...

FAO and ChinaThree Decades of Collaboration.doc

In 1982, an FAO Representation Office opened in ...in the country through such project modalities as...FAO has bestowed specific knowledge and technologies...

A knowledge engineering approach for image classifi....pdf

ers based on information of different modalities (...representation of the domain, a belief network ...4. KNOWLEDGE ENGINEERING APPROACH In this section ...

Information fusion in biometrics.pdf

Attempting to improve the performance of individual matchers in such situati ...the integration of multiple biometric modalities at the representation level. ...

Dynamic Textures Synthesis as Nonlinear Manifold Le....pdf

Non-stationary dynamic textures contain different data modalities in their ...4 3.1 Globally-Coordinated Nonlinear Manifold Representation We characterize the...

Using Domain Theory to Bias Classification Processes in Ill-....pdf

A biasing technique using partial domain knowledge ...LINNEO+ also maintains the representation (Attribute...modalities in the case of qualitative attributes, ...

Modeling treatment process and outcomes.pdf

modalities in all three national evaluation studies...representation technique (called nodelink mapping) ...knowledge and psychosocial functioning.21-24 Each ...

Paragrab A comprehensive architecture for web image....pdf

lists put together in a compact representation. Clicking...To the best of our knowledge, PARAgrab is the...modalities namely (1) visual image search, (2...

EVALUATION OF SPOKEN LANGUAGE UNDERSTANDING AND DIA....pdf

The time of day can be expressed in a phrase ...For this purpose several modalities are defined, ...representation of all knowledge needed for ...

and Expert Systems] Office automation. General Term....pdf

knowledge extraction systems must gather evidence from...representation of both text feature space and ...erent modalities, which the algorithm exploits in ...

TMH-QPSR 2-31997 1.pdf

To integrate all knowledge sources Olga is ...interpretation and generation in these modalities. ...Table 1 provides a simplified representation of ...

Obstacle Detection in Smooth High Curvature Terrain.pdf

Although well understood, these modalities can fail due to variations in ...representation, 2) in the chosen representation, the two classes are truly ...

...cues for stiffness characterization in soft-tiss....pdf

to the surgeon, e.g., through graphical representation of haptic information...Several contact feedback modalities are compared in terms of their capability...

S.T-1.L-10 Reading Submodalities and Mapping Across.doc

Often people think that everyone knows the world in the same way but this...Submodalities You have learned that people use different representation systems...

Semantic mapping for mobile robotics tasks A survey.pdf

hand, emphasizing on human interaction, knowledge representation and planning. ...2. Antecedents Among the several modalities employed in robot navigation, ...

在搜索策略的系统管理和深玻耳兹曼机之间的协同效应对....pdf

The model can extract this representation even some modalities are absent by sampling from the conditional distribution over them and ?lling them in. Our ...

The Effects of the Interface on Navigation in Virtu....pdf

to acquire knowledge about, and form a mental representation of, a space....sensory modalities to create a single coherent sensation (Welch & Warren, ...

福彩号码查询 | 福彩号码查询
All rights reserved Powered by 福彩号码查询 福彩号码查询 www.edasl.tw
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。[email protected]