Deductive Inference for the Interiors and Exteriors of Horn Theories

Simple item page
dc.creatorMakino, Kazuhisa
dc.creatorOno, Hirotaka
dc.date2009-03-03
dc.date.accessioned2026-07-07T12:48:34Z
dc.date.available2026-07-07T12:48:34Z
dc.descriptionIn this paper, we investigate the deductive inference for the interiors and exteriors of Horn knowledge bases, where the interiors and exteriors were introduced by Makino and Ibaraki to study stability properties of knowledge bases. We present a linear time algorithm for the deduction for the interiors and show that it is co-NP-complete for the deduction for the exteriors. Under model-based representation, we show that the deduction problem for interiors is NP-complete while the one for exteriors is co-NP-complete. As for Horn envelopes of the exteriors, we show that it is linearly solvable under model-based representation, while it is co-NP-complete under formula-based representation. We also discuss the polynomially solvable cases for all the intractable problems.
dc.description20 pages, 1 figure, An extended abstract of this article was presented in Proceedings of Algorithms and Computation, 19th International Symposium (ISAAC 2008), Lecture Notes in Computer Science, Vol. 5369, pp. 390-401, Springer-Verlag Berlin Heidelberg, 2008
dc.identifierhttps://arxiv.org/abs/0903.0422
dc.identifierhttp://arxiv.org/abs/0903.0422
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/222099
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectData Structures and Algorithms
dc.subjectLogic in Computer Science
dc.titleDeductive Inference for the Interiors and Exteriors of Horn Theories
dc.typetext

Files

Collections

arXiv