Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

On the impact of stratification on the complexity of nonmonotonic reasoning

On the impact of stratification on the complexity of nonmonotonic reasoning This paper investigates the problem of finding subclasses of nonmonotonic reasoning which can be implemented efficiently. The ability to «define» propositions using default assumptions about the same propositions is identified as a major source of computational complexity in nonmonotonic reasoning. If such constructs are not allowed, i.e. stratified knowledge bases are considered, a significant computational advantage is obtained. This is demonstrated by developing an iterative algorithm for propositional stratified autoepistemic theories the complexity of which is dominated by required classical reasoning. Thus efficient subclasses of stratified nonmonotonic reasoning can be obtained by further restricting the form of sentences in a knowledge base. As an example quadratic and linear time algorithms for specific subclasses of stratified autoepistemic theories are derived. The results are shown to imply efficient reasoning methods for stratified cases of default logic, logic programs, truth maintenance systems, and nonmonotonic modal logics. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Applied Non-Classical Logics Taylor & Francis

On the impact of stratification on the complexity of nonmonotonic reasoning

Download PDF

On the impact of stratification on the complexity of nonmonotonic reasoning

Abstract

This paper investigates the problem of finding subclasses of nonmonotonic reasoning which can be implemented efficiently. The ability to «define» propositions using default assumptions about the same propositions is identified as a major source of computational complexity in nonmonotonic reasoning. If such constructs are not allowed, i.e. stratified knowledge bases are considered, a significant computational advantage is obtained. This is demonstrated by developing an iterative...
Loading next page...
 
/lp/taylor-francis/on-the-impact-of-stratification-on-the-complexity-of-nonmonotonic-Q0iBfWkc0U
Publisher
Taylor & Francis
Copyright
Copyright Taylor & Francis Group, LLC
ISSN
1958-5780
eISSN
1166-3081
DOI
10.1080/11663081.1994.10510830
Publisher site
See Article on Publisher Site

Abstract

This paper investigates the problem of finding subclasses of nonmonotonic reasoning which can be implemented efficiently. The ability to «define» propositions using default assumptions about the same propositions is identified as a major source of computational complexity in nonmonotonic reasoning. If such constructs are not allowed, i.e. stratified knowledge bases are considered, a significant computational advantage is obtained. This is demonstrated by developing an iterative algorithm for propositional stratified autoepistemic theories the complexity of which is dominated by required classical reasoning. Thus efficient subclasses of stratified nonmonotonic reasoning can be obtained by further restricting the form of sentences in a knowledge base. As an example quadratic and linear time algorithms for specific subclasses of stratified autoepistemic theories are derived. The results are shown to imply efficient reasoning methods for stratified cases of default logic, logic programs, truth maintenance systems, and nonmonotonic modal logics.

Journal

Journal of Applied Non-Classical Logics – Taylor & Francis

Published: Jan 1, 1994

Keywords: automated theorem proving; tractability; autoepistemic logic; default logic; nonmonotonic modal logics; logic programs; truth maintenance systems

There are no references for this article.