Deductive inference for the interiors and exteriors of horn theories

Kazuhisa Makino, Hirotaka Ono

Research output: Contribution to journalArticlepeer-review


In this article, we investigate deductive inference for interiors and exteriors of Horn knowledge bases, where interiors and exteriors were introduced by Makino and Ibaraki [1996] to study stability properties of knowledge bases. We present a linear time algorithm for deduction for interiors and show that deduction is coNP-complete for exteriors. Under model-based representation, we show that the deduction problem for interiors is NP-complete while the one for exteriors is coNP-complete. As for Horn envelopes of exteriors, we show that it is linearly solvable under model-based representation, while it is coNP-complete under formula-based representation. We also discuss polynomially solvable cases for all the intractable problems.

Original languageEnglish
Article number23
JournalACM Transactions on Computational Logic
Issue number3
Publication statusPublished - Aug 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Logic
  • Computational Mathematics


Dive into the research topics of 'Deductive inference for the interiors and exteriors of horn theories'. Together they form a unique fingerprint.

Cite this