Brewka’s framework for default logic is extended such that this new framework is possessed of more powerful expressivity when reasoning by cases. Under this extended framework a characterization of extensions of a de...Brewka’s framework for default logic is extended such that this new framework is possessed of more powerful expressivity when reasoning by cases. Under this extended framework a characterization of extensions of a default theory is given. From this characterization the algorithms for main reasoning tasks in default logic with case reasoning are derived.展开更多
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 introdu...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 the evolution of hypotheses.An improved version of the limit the- orem 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 limit of a δ-partial increasing epistemic process of that theory,and vice versa.It Ls 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 G(?)rdenfors's theory of knowledge in flux.展开更多
As an important variant of Relier'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 enabl...As an important variant of Relier'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 result 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 question, raised by Mankinson and Gardenfors (1991), is also given about whether there is a counterpart contraction in nonmonotonic logic.展开更多
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 and th...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 and the transformed theory have the same extensions when restricted to old variables. Hence, regular default theories enjoy 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 more than O(1.45(n)), where n is the number of defaults. In case of regular prerequisite-free or semi-2CNF default theories, the credulous reasoning can be solved in polynomial time. However, credulous reasoning for semi-Horn default theories is shown to be NP-complete although it is tractable for Horn default theories. Moreover, skeptical reasoning for regular unary default theories is co-NP-complete.展开更多
文摘Brewka’s framework for default logic is extended such that this new framework is possessed of more powerful expressivity when reasoning by cases. Under this extended framework a characterization of extensions of a default theory is given. From this characterization the algorithms for main reasoning tasks in default logic with case reasoning are derived.
文摘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 the evolution of hypotheses.An improved version of the limit the- orem 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 limit of a δ-partial increasing epistemic process of that theory,and vice versa.It Ls 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 G(?)rdenfors's theory of knowledge in flux.
基金This work was supported by the National Natural Science Foundation of China (No.69785004) and the Science and Technology Fundin
文摘As an important variant of Relier'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 result 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 question, raised by Mankinson and Gardenfors (1991), is also given about whether there is a counterpart contraction in nonmonotonic logic.
文摘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 and the transformed theory have the same extensions when restricted to old variables. Hence, regular default theories enjoy 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 more than O(1.45(n)), where n is the number of defaults. In case of regular prerequisite-free or semi-2CNF default theories, the credulous reasoning can be solved in polynomial time. However, credulous reasoning for semi-Horn default theories is shown to be NP-complete although it is tractable for Horn default theories. Moreover, skeptical reasoning for regular unary default theories is co-NP-complete.