%0 Journal Article
%T Regular Disjunction-Free Default Theories
%A Xi-Shun Zhao
%A <br>Xi-ShunZhao
%J 计算机科学技术学报
%D 2004
%I 
%X 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 0(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.
%K regular disjunction-free default logic
%K extension
%K default reasoning
%K algorithm
%K complexity<br>默认推理
%K 复杂性
%K 规则自由分离
%K 系统设定逻辑
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=3F9608C598FE43BE915096D7CDFEA11B&yid=D0E58B75BFD8E51C&vid=2A8D03AD8076A2E3&iid=38B194292C032A66&sid=2B25C5E62F83A049&eid=2B25C5E62F83A049&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=20