Some Algorithms for Extension Computation of Nonmonotonic Rule Systems

Article type: Research Article

Authors: Zhao, Xishun | Ding, Decheng

Affiliations: Institute of Logics and Cognition, Zhongshan University, 510275 Guangzhou, P. R. China | Department of Mathematics, Nanjing University, 210093 Nanjing, P. R. China

Abstract: In this paper, we will place our emphasis on the problem of existence of extensions and on finding more efficient algorithms for computing extensions of nonmonotonic rule systems. First, in order to dedicate further research into nonmonotonic rule systems a new characterization and some new results are given. This characterization and these results lead to new algorithms for computing extensions. Second, a class of nonmonotonic rule systems, called regular nonmonotonic rule systems, is developed. The existence of extensions and semi-monotonicity of regular nonmonotonic rule systems are proved. Third, we prove that each regular nonmonotonic rule system has at most 1.47^n extensions, where n is the number of elements occurring in the system.

Keywords: Nonmonotonic rule system, Regular nonmonotonic rule system, Extension

Journal: Fundamenta Informaticae, vol. 48, no. 1, pp. 93-106, 2001