Regular disjunction-free default theories

In this paper, the class of regular disjunction-free default theories is introduced and investigated.A transformation from regular default theories to normal default theories is established. The initial theory andthe transformed theory have the same extensions when restricted to old variables. Hence, regular default theoriesenjoy some similar properties (e.g., existence of extensions, semi-monotonicity) as normal default theories. Then,a new algorithm for credulous reasoning of regular theories is developed. This algorithm runs in a time not morethan 0(1.45~n), where n is the number of defaults. In case of regular prerequisite-free or semi-2CNF defaulttheories, the credulous reasoning can be solved in polynomial time. However, credulous reasoning for semi-Horndefault theories is shown to be NP-complete although it is tractable for Horn default theories. Moreover, skepticalreasoning for regular unary default theories is co-NP-complete.     

A Comparative Study of Default Reasoning and Epistemic Processes

A comparative study between the theories of default reasoning and open logic is given.Some concepts of open logic,such as new premises,rejections by facts,reconstructions ,epistemic processes,and its limit are introduced to describe th evolution of hypotheses.An improved version of the limit theorem is given and proved.A model-theoretic interpretation of the closed normal defaults is given using the above concepts and the corresponding completeness is proved.Any extension of a closed normal default theory is proved to be the linit of a δ-partial increasing epistemic process of that theory,and vice versa.It is proved that there exist two distinct extensions of a closed normal default theory iff there is an δ-non-monotonic epistemic process of that theory.The completeness of Reiter‘s proof is also given and proved,in terms of the epistemic processes.Finally,the work is compared with Gaerdenfors‘s theory of knowledge in flux.     

Characterization of an auto-compatible default theory

In this paper,an equivalence condition for deciding whether a default theory is an auto-compatible default one is presented.Under the condition,the existence of extension of an auto-compatible default theory is a natural result.By introducing a well-ordering over the set D of default rules,the extensions of an auto-compatible default theory(D,W) can be computed directly.The condition represents clearly the characterization of an auto-compatible default theory,and some properties about auto-compatible default theory,such as semi-monotonicity,become natural corollaries.Based on the characterization,the revision of default beliefs is discussed to ensure the existence of extension of the default theory,and the methos is applied to investigate stable models of a general logic program.     

Some Results on Default Logic

In the previous paper,some important properties of extensions of general default theories were given.In order to further explore default logic,a characterization of extensions is presented.And a class of defaults,so-called Auto-compatible Default Theory,is also introduced.All these essentially develop the theories of Reiter and his followers.     

Fixed-parameter tractability of disjunction-free default reasoning

In this paper,the parameter which is the source of the complexity of disjunctionfree default reasoning is determined.It is shown that when the value of this parameter is fixed,the disjunction-free default reasoning can be solved time bounded by a polynomial whose degree does not depend on the parameter.Consequently,disjunction-free default reasoning is fixed parameter tractable.     

Relative properties of frame language

The paper discusses semantics of encodings in logical frameworks where equalities in object calculi are represented by families of types as the case in ELF.The notion of Leibniz equality in a category is introduced.Two morphisms in a categroy are Leibniz equal if they are seen so by an internal category.The usual categorical properties are then relativized to r-properties by requiring mediating morphisms to be unique up to some Leibniz equality.Using these terminologies,it is shown by an example,that the term model of the encoding of an adequately represented object calculus is r-isomorphic to the term model of the object language.     

A classification model based on SVM and rough set theory

This paper presents a novel classification approach based on rough set theory and supporter vector machine. Sometimes, there are many attributes for classification samples and it is difficult to carry out classification. In this paper, the attributes of data set are reduction by rough set theory firstly, and then the classification is carried out using support vector machine. Finally, the classification results are obtained through the proposed model. Moreover, the proposed classification model has higher prediction accuracy by comparing with the traditional algorithm Naive Bayes algorithm and reduces the cost of calculation.     

构造类型论与计算机程序设计

Recent years,in the area of computer programming language theories,automated deduction,and more generalized area of logic and computing,a lot of systems based on constructive type theory are used widely to design type system for computer programming languages,to do formal system develpment and verification,and to be used as foundation of mathematics and computing.constructive type theory provides computer scientists with a framework to combine logic and computer program design in an elegant and flexible way.In this paper,the evolvement of constructive type theory is first introduced.The several foundations of type theory are then discussed,together with analysis of the relationships between them.The relation between constructive type theory and computer programming is explored in-depth.In the last,Martin Lof‘‘‘‘s intuitionistic type theory is used as an example to demonstrate how to do program development and verification in the same formal system.     

Decentralized PD control for non-uniform motion of a Hamiltonian hybrid system

In this paper, a decentralized proportional-derivative （PD） controller design for non-uniform motion of a Hamiltonian hybrid system is considered. A Hamiltonian hybrid system with the capability of producing a non-uniform motion is developed. The structural properties of the system are investigated by means of the theory of Hamiltonian systems. A relationship between the parameters of the system and the parameters of the proposed decentralized PD controller is shown to ensure local stability and tracking performance. Simulation results are included to show the obtained non-uniform motion.     

Default reasoning and belief revision: A syntax-independent approach

As an important variant of Reiter‘s default logic.Poole(1988) developed a nonmonotonic reasoning framework in the classical first-order language,Brewka and Nebel extended Poole‘s approach in order to enable a representation of priorities between defaults.In this paper a general framework for default reasoning is presented,which can be viewed as a generalization of the three approaches above.It is proved that the syntax-independent default reasoning in this framework is identical to the general belief revision operation introduced by Zhang et al.(1997).This esult provides a solution to the problem whether there is a correspondence between belief revision and default logic for the infinite case .As a by-product,an answer to the the question,raised by Mankinson and Gaerdenfors(1991),is also given about whether there is a counterpart contraciton in nonmonotonic logic.     

Representation theory for default logic

Default logic can be regarded as a mechanism to represent families of belief sets of a reasoning agent. As such, it is inherently second-order. In this paper, we study the problem of representability of a family of theories as the set of extensions of a default theory. We give a complete solution to the problem of representability by means of default theories with finite set of defaults, and by means of normal default theories. We obtain partial results on representability by arbitrary (infinite, non-normal) default theories. We construct examples of denumerable families of non-including theories that are not representable. We also study the concept of equivalence between default theories. This revised version was published online in June 2006 with corrections to the Cover Date.     

Default logic and specification of nonmonotonic reasoning

In this paper constructions leading to the formation of belief sets by agents are studied. The focus is on the situation when possible belief sets are built incrementally in stages. An infinite sequence of theories that represents such a process is called a reasoning trace. A set of reasoning traces describing all possible reasoning scenarios for the agent is called a reasoning frame. Default logic by Reiter is not powerful enough to represent reasoning frames. In the paper a generalization of default logic of Reiter is introduced by allowing infinite sets of justifications. This formalism is called infinitary default logic. In the main result of the paper it is shown that every reasoning frame can be represented by an infinitary default theory. A similar representability result for antichains of theories (belief frames) is also presented.     

缺省理论的简化

缺省理论△=(D,W)中的缺省规则集D,是该理论的不确定因素.如果能去掉一些缺省规则而又不影响该理论的延伸,则就在一定程度上简化了该理论.本文证明了关于规范缺省理论的延伸的若干性质,利用这些性质,我们可以把某些规范缺省理论在一定条件下得以化简,有的甚至可以把它们化为一阶逻辑理论.     

Consequence finding and computing answers with defaults

Consequence finding has been recognized as an important technique in many intelligent systems involving inference. In previous work, propositional or first-order clausal theories have been considered for consequence finding. In this paper, we consider consequence finding from a default theory, which consists of a first-order clausal theory and a set of normal defaults. In an extension of a default theory, consequence finding can be done with the generating defaults for the extension. Alternatively, all extensions can be represented at once with the conditional answer format, which represents how a conclusion depends on which defaults. We also propose a procedure for consequence finding and query answering in a default theory using the first-order consequence-finding procedure SOL. In computing consequences from default theories efficiently, the notion of TCS-freeness is most important to prune a large number of irrational tableaux induced by the generating defaults for an extension. In order to simulate the TCS-freeness, the refined SOL calculus called SOL-S(Γ) is adopted using skip preference and complement checking. This research is supported in part by JSPS Grant-in-Aid for Scientific Research (No. 17300051)     

A Correct Logic Programming Computation of Default Logic Extensions

We present a method of representing some classes of default theories as normal logic programs. The main point is that the standart semantics (i.e., SLDNF-resolution) computes answer substitutions that correspond exactly to the extensions of the represented default theory. This means that we give a correct implementation of default logic. We explain the steps of constructing a logic program LogProg(P, D) from a given default theory (P, D), give some examples, and derive soundness and completeness results.     

可能性缺省逻辑及其应用

本文分析了Yager用可能性理论框架来表示缺省知识的形式化方法,并测试了三类不同的应用方案,得到的结果与Reiter的缺省逻辑得到的结果相比较,表明只在具有严格的约束的缺省逻辑下,Yager的形式化方法才与Reiter的缺省逻辑具有一定的相关性,我们指出了它们在一般缺省理论下的不匹配处,并给出了以不动点机制抽改进方来消除这
些不匹配。     

Seminormal stratified default theories

In this paper we study seminormal default theories. The notions of stratification and strong stratification are introduced. The properties of stratified and strongly stratified default theories are investigated. We show how to determine if a given seminormal default theory is strongly stratified and how to find the finest partition into strata. We present algorithms for computing extensions for stratified seminormal default theories and analyze their complexity.     

关于D.W.Etherington的扩充产生算法的一个注记

Ｄ．Ｗ．Ｅｔｈｅｒｉｎｇｔｏｎ提出了一类总是有扩充的缺省理论，即有限有序缺省理论，同时使用接连近似的方法给出产生这类缺省理论的所有扩充的算法，并证明该算法对有限有序网络缺省理论总是收敛到一扩充。本文首先举例说明Ｄ．Ｗ．Ｅｔｈｅｒｉｎｇｔｏｎｄ的算法对一般的有限有序缺省理论并非总是收敛，然后给出了该算法对
对一般的有限有序缺省理论收敛的一个充分条件。     

带值限制的本体描述语言研究

基于F-逻辑和O-逻辑,提出了一种带值限制的本体形式表示语言。一个本体包括类框架、槽框架、类槽框架以及个体框架。本体通过槽的框架来说明对该槽的一般值限制。本体中的一个类和一个槽对应着一个类槽;并且通过类槽的框架来说明用该槽来对这个类进行描述时的特定的值限制。在给出了本体的形式语法后,讨论了本体的继承机制;并且通过具体示例来对本体以及继承机制进行阐述。