Deductive inference for the interiors and exteriors of horn theories

Kazuhisa Makino; Hirotaka Ono

doi:10.1007/978-3-540-92182-0_36

Deductive inference for the interiors and exteriors of horn theories

Kazuhisa Makino, Hirotaka Ono

mathematics and information

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In 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 [11] 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.

Original language	English
Title of host publication	Algorithms and Computation - 19th International Symposium, ISAAC 2008, Proceedings
Pages	390-401
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-540-92182-0_36
Publication status	Published - 2008
Event	19th International Symposium on Algorithms and Computation, ISAAC 2008 - Gold Coast, QLD, Australia Duration: Dec 15 2008 → Dec 17 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5369 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	19th International Symposium on Algorithms and Computation, ISAAC 2008
Country/Territory	Australia
City	Gold Coast, QLD
Period	12/15/08 → 12/17/08

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-92182-0_36

Cite this

Makino, K., & Ono, H. (2008). Deductive inference for the interiors and exteriors of horn theories. In Algorithms and Computation - 19th International Symposium, ISAAC 2008, Proceedings (pp. 390-401). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5369 LNCS). https://doi.org/10.1007/978-3-540-92182-0_36

Deductive inference for the interiors and exteriors of horn theories. / Makino, Kazuhisa; Ono, Hirotaka.
Algorithms and Computation - 19th International Symposium, ISAAC 2008, Proceedings. 2008. p. 390-401 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5369 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Makino, K & Ono, H 2008, Deductive inference for the interiors and exteriors of horn theories. in Algorithms and Computation - 19th International Symposium, ISAAC 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5369 LNCS, pp. 390-401, 19th International Symposium on Algorithms and Computation, ISAAC 2008, Gold Coast, QLD, Australia, 12/15/08. https://doi.org/10.1007/978-3-540-92182-0_36

@inproceedings{2b282b654d6d4ab8a831baf099eff7d4,

title = "Deductive inference for the interiors and exteriors of horn theories",

abstract = "In 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 [11] 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.",

author = "Kazuhisa Makino and Hirotaka Ono",

note = "Funding Information: This work is supported in part by the Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan and by the Asahi glass foundation.; 19th International Symposium on Algorithms and Computation, ISAAC 2008 ; Conference date: 15-12-2008 Through 17-12-2008",

year = "2008",

doi = "10.1007/978-3-540-92182-0_36",

language = "English",

isbn = "3540921818",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "390--401",

booktitle = "Algorithms and Computation - 19th International Symposium, ISAAC 2008, Proceedings",

}

TY - GEN

T1 - Deductive inference for the interiors and exteriors of horn theories

AU - Makino, Kazuhisa

AU - Ono, Hirotaka

N1 - Funding Information: This work is supported in part by the Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan and by the Asahi glass foundation.

PY - 2008

Y1 - 2008

N2 - In 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 [11] 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.

AB - In 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 [11] 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.

UR - http://www.scopus.com/inward/record.url?scp=58549097721&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58549097721&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-92182-0_36

DO - 10.1007/978-3-540-92182-0_36

M3 - Conference contribution

AN - SCOPUS:58549097721

SN - 3540921818

SN - 9783540921813

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 390

EP - 401

BT - Algorithms and Computation - 19th International Symposium, ISAAC 2008, Proceedings

T2 - 19th International Symposium on Algorithms and Computation, ISAAC 2008

Y2 - 15 December 2008 through 17 December 2008

ER -

Deductive inference for the interiors and exteriors of horn theories

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this